【数据结构·考研】二叉树的高度（深度）

二叉树的高度（深度）

二叉树的高度和深度其实是相同的东西。自下向上称作计算高度，由上到下称为计算深度。求二叉树的深度也有递归和非递归的方法。递归的方法就是一直递归到树的最边缘，通过比较当前左右子树的高度，取大的一方+1继续向上累积，直到比较到根节点的左右子树高度，然后取大的一棵+1就是最后树高。而非递归的方式是利用到树的层次遍历，每遍历一层+1，直到遍历完整棵树。

代码如下：

#include
#include
using namespace std;typedef struct node{char val;struct node* left;struct node* right;
}TreeNode,*Tree;//递归
/*递归走到树的最底层，再通过比较左右子树的高度，取较高一棵+1，一直累加到树根。*/  
int Height(Tree& t){if(t == NULL) return 0; //当前结点为空，返回0//由下至上比较左右子树高度得到最终高度 return Height(t->left) > Height(t->right) ? Height(t->left) + 1 : Height(t->right) + 1;
} //非递归 
/*改编自层次遍历，由根向下每遍历一层，深度+1*/ 
int Depth(Tree& t) {if(t == NULL) return 0;int depth = 0; //树的深度 queue q;q.push(t);while(!q.empty()){int n = q.size();for(int i = 0;ileft) q.push(s->left);if(s->right) q.push(s->right);}depth += 1; //深度+1 } return depth;
}void CreateTree(Tree& t){char x;cin>>x;if(x == '#') t = NULL; else{t = new TreeNode; t->val = x;  CreateTree(t->left); CreateTree(t->right); }
} int main(){Tree t;CreateTree(t);/*a b d # # e # # c f # # #*/cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！