11 treedeep123.cpp

数据结构的必做编程题

#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>	
#define NULL 0
#define OVERFLOW 0
typedef struct BiTNode           //定义线性链表
{
	char data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;		
}*BiTree;

int i,j;		

void CreateBiTree(BiTree &T)	//先序扩展序列建立树的递归算法 
{  
	char ch;
	scanf("%c",&ch);
	if (ch=='@') 
	{
		T = NULL;		
	}
	else 
	{ 
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
		{
			exit(OVERFLOW);
		}
		T->data=ch;
		CreateBiTree(T->lchild); 
		CreateBiTree(T->rchild); 
	}  
} 

void LastOrder (BiTree T)	//后序遍历树的递归算法
{ 
	if (T)
    { 
		i++;
		LastOrder(T->lchild);
		if(i>j)j=i;		//j记录树曾达到的最大深度
		LastOrder(T->rchild);	
	}i--;
}

void main()
{   
	printf("请按先序扩展序列输入所对应的树，空用@表示:\n");
	int deep;
    i=0;j=0;
	BiTree a;
	CreateBiTree(a);
	LastOrder(a);	
	deep=j+1;
	printf("\n树的深度deep=%d",deep);
	printf("\n");
}