chr100606056 2021-06-23 11:40 采纳率: 100%
浏览 142
已采纳

用二叉链表创建一棵二叉树并利用递归算法求它的高度

用二叉链表创建一棵二叉树并利用递归算法求它的高度

  • 写回答

1条回答 默认 最新

  • CSDN专家-黄老师 2021-06-23 11:49
    关注
    #include<bits/stdc++.h>
    using namespace std;
    
    typedef struct BNode{
        char data;
        struct BNode *lchild;
        struct BNode *rchild;
    }BNode;
    
    const int N = 100;
    char str[N]; //存储先序遍历序列
    int i; //标记处理到哪一个字符了
    BNode *BulidTree(){
        if(str[i] == '#'){
            i++; //处理下一个字符
            return NULL;
        }else{
            //新建一个结点
            BNode *p = (BNode *)malloc(sizeof(BNode));
            p->data = str[i];
            p->lchild = NULL;
            p->rchild = NULL;
            i++;
            p->lchild = BulidTree();
            p->rchild = BulidTree();
            return p;
        }
    }
    
    //非递归算法
    int Depth(BNode *root){
        int level = 0; //level为层数
        BNode *last = root;//last为下一层的最右结点
        if(root == NULL){ //树空,则高度为0
            return 0;
        }
        queue<BNode *> treenode; //申请一个队列
        treenode.push(root); //根结点入队
        while(!treenode.empty()){ //队不空时循环
            BNode *p = treenode.front(); //队首
            treenode.pop(); //根结点出队
            if(p->lchild != NULL){ //如果存在左子树,则左子树根结点入队
                treenode.push(p->lchild);
            }
            if(p->rchild != NULL){ //如果存在右子树,则右子树根结点入队
                treenode.push(p->rchild);
            }
            if(p == last){ //如果刚才出队的是该层最右结点
                level++; //层数加1
                last = treenode.back(); //last指向下层
            }
        }
        return level;
    }
    
    //递归算法
    // int Depth2(BNode *root){
    //     if(root == NULL){ //空树,高度为0
    //         return 0;
    //     }
    //     int left = Depth2(root->lchild); //左子树高度
    //     int right = Depth2(root->rchild); //右子树高度
    //     return (left>right? left+1 : right+1); //树的高度为最大子树的高度加上根结点
    // }
    
    int main(){
        scanf("%s",str);
        i = 0;
        BNode *root = BulidTree();
        int level = Depth(root);
        printf("%d\n",level);
        return 0;
    }
    

    如果对你有帮助,可以点击我这个回答右上方的【采纳】按钮,给我个采纳吗,谢谢
     

    展开全部

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

报告相同问题?

悬赏问题

  • ¥15 matlab中频率调制法代码的解读
  • ¥15 ceph的对象、块、文件相关问题求解答
  • ¥50 如果使用python进行ERA5 10米风场预报检验
  • ¥15 navicat解析mysql密码
  • ¥15 SDAPI(关键词-table)
  • ¥15 unity安卓打包出现问题
  • ¥20 安装catkin时遇到了如下问题请问该如何解决呢
  • ¥15 VAE模型如何输出结果
  • ¥15 编译python程序为pyd文件报错:{"source code string cannot contain null bytes"
  • ¥20 关于#r语言#的问题:广义加行模型拟合曲线后如何求拐点
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部