10.cpp

用递归求出二叉树的深度

/*求二叉树的深度(后序遍历)*/ 
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define null 0
typedef struct node
{ char data;
  struct node *lchild;
  struct node *rchild;
}* bitree;


int CreateBiTree(bitree &t)  //按先序次序构造二叉树
{char ch=' ';
 scanf("%c",&ch);
 if(ch==' ')t=null;
 else{
	 if(!(t=(node *)malloc(sizeof(node))))return 0;
	 t->data=ch;          //建立根节点
	 CreateBiTree(t->lchild);//建立左子树
	 CreateBiTree(t->rchild);//建立右子树
 }
 return 1;
}


int depth(bitree t)
{
	int dep,dep1,dep2;		//分别为：根，左，右子树的深度

	if(!t)					//如果树空
	{
		dep=0;				//b的深度就是0
	}
	else
	{
		dep1=depth(t->lchild);
		dep2=depth(t->rchild);
		dep=1+(dep1>dep2?dep1:dep2);
	}
	return dep;
}


void main()
{bitree t=null;
 int deep;
 printf("输入二叉树中结点的值:");
 CreateBiTree(t);
 deep=depth(t);
 printf("二叉树深度为:");
 printf("%d",deep);
 printf("\n");
}