问题：这两种操作都用到了递归，别人说递归好理解，我真的不觉得递归好理解，只是递归的代码看起来简单。
下面代码是求高度的另一种方法。递归计算高度是从底向上计算的，因此叶子节点高度为0；
方法真的很巧妙。。。
比如getTreeHigh(a->lchild)返回的就是a的左子树的高度，getTreeHigh(a->lchild)返回的就是a的右子树的高度。
int getTreeHigh(BinTree btree)
{
int depth;
if(btree==NULL)
depth=0;
else
{
depthleft=getTreeHigh(btree->lchild);
depthright=getTreeHigh(btree->rchild);
depth=1+max(depthleft,depthright);
}
return depth;
}
代码：
#include <iostream>
#include <cstdlib>
#include <stack>
using namespace std;
static int num=0;
typedef struct btree
{
char data;
struct btree *lchild;
struct btree *rchild;
}*BinTree;
void CreateBinTree(BinTree &btree)
{
char c;
cin>>c;
if(c=='#')
btree=NULL;
else
{
btree=(BinTree)malloc(sizeof(struct btree));
btree->data=c;
CreateBinTree(btree->lchild);
CreateBinTree(btree->rchild);
}
}
void showBTree(BinTree btree)
{
if(btree)
{
cout<<btree->data<<" ";
showBTree(btree->lchild);
showBTree(btree->rchild);
}
}
int getTreeHigh(BinTree btree)
{
if(btree==NULL)
return 0;
if(btree->lchild&&btree->rchild)
return max(getTreeHigh(btree->lchild)+1,getTreeHigh(btree->rchild)+1);
if(btree->lchild)
return getTreeHigh(btree->lchild)+1;
if(btree->rchild)
return getTreeHigh(btree->rchild)+1;
return 1;
}
int getNumOfleaves(BinTree btree)
{
if(btree)
{
if(btree->lchild==NULL&&btree->rchild==NULL)
num++;
else
{
getNumOfleaves(btree->lchild);
getNumOfleaves(btree->rchild);
}
}
return num;
}
int main()
{
BinTree bt;
int count;
int h=0;
cout<<"create bintree:"<<endl;
CreateBinTree(bt);
cout<<"output the bintree:"<<endl;
showBTree(bt);
cout<<endl;
count=getNumOfleaves(bt);
cout<<"叶子节点数为: "<<count<<endl;
h=getTreeHigh(bt);
cout<<"二叉树的高度为: "<<h<<endl;
return 0;
}
运行结果：
