用二叉链表创建一棵二叉树并利用递归算法求它的高度
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; }
如果对你有帮助,可以点击我这个回答右上方的【采纳】按钮,给我个采纳吗,谢谢
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决评论 打赏 举报无用 2
悬赏问题
- ¥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语言#的问题:广义加行模型拟合曲线后如何求拐点