lptLPTlptLPT 2015-12-17 07:25 采纳率: 50%
浏览 1898
已采纳

数据结构 二叉树的建立与相关运算

二叉树的建立与相关运算
以广义表的形式输入二叉树,建立二叉链表,完成如下功能:
三种递归遍历
计算并输出单分支节点,双分支结点,叶子结点及其个数。
把任一种递归算法改为非递归算法。

  • 写回答

1条回答 默认 最新

  • 山楂奶酪黄连蒜 2015-12-17 09:40
    关注

    #include
    #include

    #define N 20

    typedef struct tree
    {
    char data;
    struct tree *pa;
    struct tree *lc;
    struct tree *rc;
    }sTre,*pTre;

    void output(pTre p);
    void create_tree(pTre root,char arr[N]);
    int pre_create_tree(pTre p,char arr[N],int i);
    void init_node(pTre *p);
    void create_memory(pTre *p);
    void pre(pTre p);
    void mid(pTre p);
    void last(pTre p);
    void free_memory(pTre *p);
    void delete_node(pTre p);
    void unload(pTre p);

    int main()
    {
    pTre root=NULL;
    init_node(&root);
    char arr[N];
    printf("please input pre tree:\n");
    gets(arr);
    create_tree(root,arr);
    output(root);
    unload(root);
    return 0;
    }

    void create_tree(pTre root,char arr[N])
    {
    if(arr[0]=='\0')
    {
    printf("input error!\n");
    return;
    }
    root->data=arr[0];
    pre_create_tree(root,arr,1);
    }

    int pre_create_tree(pTre p,char arr[N],int i)
    {
    pTre pnew=NULL;
    if(arr[i]=='\0')
    {
    return i;
    }
    if(arr[i]!=' ')
    {
    init_node(&pnew);
    pnew->data=arr[i];
    p->lc=pnew;
    pnew->pa=p;
    i=pre_create_tree(pnew,arr,i+1);
    if(arr[i]=='\0')
    {
    return i;
    }
    }
    i++;
    if(arr[i]=='\0')
    {
    return i;
    }
    if(arr[i]!=' ')
    {
    init_node(&pnew);
    pnew->data=arr[i];
    p->rc=pnew;
    pnew->pa=p;
    i=pre_create_tree(pnew,arr,i+1);
    }
    return i;
    }

    void init_node(pTre *p)
    {
    create_memory(p);
    (*p)->pa=NULL;
    (*p)->lc=NULL;
    (*p)->rc=NULL;
    }

    void create_memory(pTre *p)
    {
    *p=malloc(sizeof(sTre));
    if(NULL==*p)
    {
    printf("create memory error!\n");
    exit(-1);
    }
    }

    void pre(pTre p)
    {
    if(p!=NULL)
    {
    printf("%c ",p->data);
    pre(p->lc);
    pre(p->rc);
    }
    }
    void mid(pTre p)
    {
    if(p!=NULL)
    {
    mid(p->lc);
    printf("%c ",p->data);
    mid(p->rc);
    }
    }
    void last(pTre p)
    {
    if(p!=NULL)
    {
    last(p->lc);
    last(p->rc);
    printf("%c ",p->data);
    }
    }

    void unload(pTre p)
    {
    if(p!=NULL)
    {
    unload(p->lc);
    unload(p->rc);
    delete_node(p);
    }
    }

    void delete_node(pTre p)
    {
    p->pa=NULL;
    free_memory(&p);
    }

    void free_memory(pTre *p)
    {
    if(*p!=NULL)
    {
    free(*p);
    *p=NULL;
    }
    }

    void output(pTre p)
    {
    printf("pre:");
    pre(p);
    printf("\nmid:");
    mid(p);
    printf("\nlast:");
    last(p);
    printf("\n");
    }

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 BP神经网络控制倒立摆
  • ¥20 要这个数学建模编程的代码 并且能完整允许出来结果 完整的过程和数据的结果
  • ¥15 html5+css和javascript有人可以帮吗?图片要怎么插入代码里面啊
  • ¥30 Unity接入微信SDK 无法开启摄像头
  • ¥20 有偿 写代码 要用特定的软件anaconda 里的jvpyter 用python3写
  • ¥20 cad图纸,chx-3六轴码垛机器人
  • ¥15 移动摄像头专网需要解vlan
  • ¥20 access多表提取相同字段数据并合并
  • ¥20 基于MSP430f5529的MPU6050驱动,求出欧拉角
  • ¥20 Java-Oj-桌布的计算