m0_64018569 2021-11-18 15:19 采纳率: 78.6%
浏览 33
已结题

二叉树问题,写代码。

通过键盘输入的扩充二叉树的层次遍历序列, 建立二叉树(如:序列:2,5,6,0,0,10,11,0,0,0,0 )。(设二叉树结点的数据为int型,其中扩充结点用'0'号表示)。然后按中序和后序输出此二叉树,求该树的叶结点个数和度数为2的结点个数)。

  • 写回答

1条回答 默认 最新

  • 关注

    你题目的解答代码如下:

    #include "stdio.h"
    
    #include "malloc.h"
    
    typedef struct treenode
    
    {
        int data;
    
        struct treenode *lchild, *rchild;
    
    } TREENODE, *TREENODEPTR;
    
    #define N 50
    
    void creattree(TREENODEPTR *root)
    
    {
        int value, r1, r2;
    
        TREENODEPTR t, q[N];
    
        scanf("%d", &value);
    
        if (value)
    
        {
            *root = (TREENODEPTR)malloc(sizeof(TREENODEPTR));
    
            (*root)->data = value;
    
            r2 = r1 = 1;
    
            q[r1] = *root;
        }
    
        else
    
        {
            printf("input error\n");
            return;
        }
    
        while (r2 <= r1)
    
        {
            t = q[r2];
            r2++;
    
            scanf("%d", &value);
    
            if (value == 0)
    
                t->lchild = NULL;
    
            else
    
            {
                t->lchild = (TREENODEPTR)malloc(sizeof(TREENODEPTR));
    
                t->lchild->data = value;
    
                r1++;
                q[r1] = t->lchild;
            }
    
            scanf("%d", &value);
    
            if (value == 0)
    
                t->rchild = NULL;
    
            else
    
            {
                t->rchild = (TREENODEPTR)malloc(sizeof(TREENODEPTR));
    
                t->rchild->data = value;
    
                r1++;
                q[r1] = t->rchild;
            }
        }
    }
    
    /*非递归中序遍历二叉树*/
    
    void InOrder(TREENODEPTR root)
    
    {
    
        TREENODEPTR q[N];
    
        int top = 0;
    
        TREENODEPTR p;
    
        p = root;
    
        do
        {
    
            while (p != NULL)
    
            {
    
                if (top > N)
    
                    return;
    
                top = top + 1;
    
                q[top] = p;
    
                p = p->lchild;
            };
    
            if (top != 0)
    
            {
    
                p = q[top];
    
                top = top - 1;
    
                printf("%3d", p->data);
    
                p = p->rchild;
            }
    
        } while (p != NULL || top != 0);
    }
    
    /*非递归后序遍历二叉树*/
    
    void PostOrder(TREENODEPTR root)
    {
    
        TREENODEPTR p, r, q[N];
    
        int top = 0;
    
        r = NULL;
    
        p = root;
    
        while (p != NULL || top != 0)
    
        {
    
            while (p != NULL)
    
            {
                top++;
    
                if (top >= N)
    
                    return;
    
                q[top] = p;
                p = p->lchild;
            }
    
            if (top > 0)
    
            {
                p = q[top];
    
                if ((p->rchild == NULL) || (p->rchild == r))
                {
                    printf("%3d", p->data);
    
                    r = p;
    
                    top--;
    
                    p = NULL;
                }
    
                else
    
                    p = p->rchild;
            }
        }
    }
    
    main()
    
    {
        TREENODEPTR root;
    
        root = NULL;
    
        printf("输入的扩充二叉树的层次遍历序列为:\n");
    
        creattree(&root);
    
        printf("非递归中序遍历二叉树:\n");
    
        InOrder(root);
    
        printf("\n");
    
        printf("非递归后序遍历二叉树:\n");
    
        PostOrder(root);
    
        printf("\n");
    }
    
    
    

    如有帮助,望采纳!谢谢!

    参考

    img

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

报告相同问题?

问题事件

  • 系统已结题 11月26日
  • 已采纳回答 11月18日
  • 创建了问题 11月18日

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型