二叉树：编写一个函数int Depth(BiTNode *T)。函数功能：计算二叉树的深度。
#include <>
#include <>
typedef struct BiTNode
{
int data; //关键字项
struct BiTNode *lchild,*rchild; //左右孩子指针
} BiTNode;
BiTNode *CreateBST(int A[],int n);
void DispBST(BiTNode *bt);
int InsertBST(BiTNode *&p,int k);
int Depth(BiTNode *T)//计算二叉树的深度
{
int d1,d2;
if(T==NULL){
return 0;
}else{
d1=Depth(T->lchild);
d2=Depth(T->rchild);
return d1>d2?d1+1:d2+1;
}
}
int main()
{
BiTNode *bt,*p;
int n=12,x=46;
int a[]= {25,18,46,2,53,39,32,4,74,67,60,11};
int depth;
bt=CreateBST(a,n);
DispBST(bt);
printf("\n");
depth=Depth(bt);
printf("树的深度为：%d\n",depth);
return 0;
}
void DispBST(BiTNode *bt)//输出一棵排序二叉树
{
if (bt!=NULL)
{
printf("%d",bt->data);
if (bt->lchild!=NULL || bt->rchild!=NULL)
{
printf("("); //有孩子结点时才输出(
DispBST(bt->lchild); //递归处理左子树
if (bt->rchild!=NULL) printf(","); //有右孩子结点时才输出,
DispBST(bt->rchild); //递归处理右子树
printf(")"); //有孩子结点时才输出)
}
}
}
int InsertBST(BiTNode *&p,int k)//递归算法，在p所指向的二叉排序树中，插入值为k的节点
{
if (p==NULL) //原树为空, 新插入的记录为根结点
{
p=(BiTNode *)malloc(sizeof(BiTNode));
p->data=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->data) //树中存在相同关键字的结点,返回0
return 0;
else if (k<p->data)
return InsertBST(p->lchild,k); //插入到*p的左子树中
else
return InsertBST(p->rchild,k); //插入到*p的右子树中
}
BiTNode *CreateBST(int A[],int n) //由有n个元素的数组A，创建一个二叉排序树。返回BST树根结点指针
{
BiTNode *bt=NULL; //初始时bt为空树
int i=0;
while (i<n)
{
InsertBST(bt,A[i]); //将关键字A[i]插入二叉排序树T中
i++;
}
return bt; //返回建立的二叉排序树的根指针
}