编辑代码

/****************   算法6.9 （135页）**********
		            求二叉树的深度
	先序输入法创建二叉树，后序遍历方式求取二叉树深度
************************************************************/
#include <stdlib.h>
#include <stdio.h>
#define maxsize  100
typedef char datatype;

//二叉树的二叉链表存储表示
typedef struct node {
	datatype data;						//结点数据域
	struct node *lchild, *rchild;	//左右孩子指针
} bitree;

//用先序遍历的顺序建立二叉链表
bitree *CreateBiTree( ) {
//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	bitree *T = NULL;
	char ch;
	ch = getchar( );
	if (ch != '@') {
		T = (bitree *)malloc(sizeof(bitree));
		T->data = ch;					//生成根结点
		T->lchild = CreateBiTree();	//递归创建左子树
		T->rchild = CreateBiTree();	//递归创建右子树
	} else {
		T = NULL;			//递归结束，建空树
	}
	return T;
}



int Depth(bitree *T) {
	int depL, depR;
	if (T != NULL) {
		depL = Depth(T->lchild);
		depR = Depth(T->rchild);
		printf("%c", T->data);
		if (depL >= depR)
			return (depL + 1); //二叉树的深度为左、右子树深度较大者加1
		else
			return (depR + 1);
	}
	return 0;
}

int main() {
	bitree *p;
	printf("建立树，按先序遍历序列输入结点\n");
	printf("空结点为@，结束按回车\n");
	p = CreateBiTree( );

	printf("后序遍历输出为\n");
	int deep = Depth(p);
	printf("\n");
	printf("二叉树的深度为:%d\n ", deep);

	return 0;
}

//测试样例1 (教材第131页图6.10中的二叉树，先序遍历输入结点)
// 输入结点  ABD@@E@G@@C@FH@@@

//测试样例2 (教材第134页图6.11，先序遍历输入结点))
// 输入结点  ABH@@FD@@@E@CK@@G@@