怎么计算二叉树高度？

计算二叉树的高度可以采用几种不同的算法。算法一：采用后序遍历二叉树，结点最大栈长即为二叉树的高度；算法二：层次遍历二叉树，最大层次即为二叉树的高度；算法三：采用递归算法，求二叉树的高度。/法1：后序遍历，结点最大栈长即为树的高度//法2：层次遍历，层次即为高度//法3：递归求树高//调试程序输入二叉树：-a##*b##-c##d##/e##f##//程序输出该二叉树的高度：5#include#include#includeusingnamespacestd;typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidCreateTree(BiTree&T){charch;cin>>ch;if(ch=='#')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(!T)coutdata=ch;CreateTree(T->lchild);CreateTree(T->rchild);}}//法1：后序遍历，结点最大栈长即为树的高度intBT_high(BiTreeT){BiTreep=T,r=NULL;intmax=0;//树高stacks;while(p||!s.empty()){if(p!=NULL){s.push(p);p=p->lchild;}else{p=s.top();if(p->rchild!=NULL&&p->rchild!=r)p=p->rchild;else{if(s.size()>max)max=s.size();//最大层次即为高度r=p;s.pop();p=NULL;}}}returnmax;}//法2：层次遍历，层次即为高度intBT_level_depth(BiTreeT){if(!T)return0;BiTreep=T,Q[100];intfront=-1,rear=-1,last=0,level=0;Q[rear]=p;while(frontlchild)Q[rear]=p->lchild;if(p->rchild)Q[rear]=p->rchild;if(front==last){last=rear;level;//层次1}}returnlevel;}//法3：递归求树高1intmax1=0;//树高intBT_depth1(BiTreeT,intdepth){if(T){if(T->lchild)BT_depth1(T->lchild,depth1);if(T->rchild)BT_depth1(T->rchild,depth1);}if(depth>max1)max1=depth;returndepth;}//法3：递归求树高2intHeight(BiTreeT){if(T==NULL)return0;else{intm=Height(T->lchild);intn=Height(T->rchild);return(m>n)?(m1):(n1);}}intmain(){BiTreeT=NULL;CreateTree(T);cout<<"后序遍历求树高："<

渔阳君 2022-01-19 17:28:34