depth.cpp

后序遍历求二叉树深度。

//求二叉树的深度（后序遍历）

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"

typedef struct BiTNode{      //自定义二叉树的存储结构
	char data;               //数据
	struct BiTNode *lchild , *rchild;    //左右孩子指针
}BiTNode,*BiTree;

//先序建立二叉树函数
void CreatBiTree(BiTree &T){    
	char ch;
	scanf("%c",&ch);
		if(ch==' ')T=NULL; //若输入空格符则表示空树
		else{
			T=(BiTNode *)malloc(sizeof(BiTNode)) ;  //动态分配存储单元
			T->data=ch;
			//printf("%c",T->data);
			CreatBiTree(T->lchild);
			CreatBiTree(T->rchild);
		}
}

//求二叉树深度函数
int Depth (BiTree &T) {    // 返回二叉树的深度
   int dep,ldep,rdep;
   if ( !T )              //空树返回0
	   dep = 0;
   else
   {                               //遍历
	   ldep=Depth( T->lchild );
       rdep=Depth( T->rchild );
       if(ldep>rdep)               //取左子树和右子树中最大值加1即为深度
		 dep=ldep+1;               
	   else
		 dep=rdep+1;
	 }
	  return dep;                 //返回深度
}

void main()
{
	BiTree t;
//	char n;
	int m;
	printf("请先建立二叉树！\n");
	CreatBiTree(t);
	printf("二叉树已经建立！其深度为：\n");
	  m=Depth(t);
	  printf("%d\n",m);                //输出深度
}