cpp1.cpp

Recognizing its importance is only the fist step to advocate invetion or innovation

#include<stdio.h>
#include<stdlib.h>

typedef struct BitNode
{
	char data;
	BitNode *lchild,*rchild;
}BitNode,*BiTree;// 树的结构，
typedef struct Path
{
	int path[10];
	int Ln;
}Path;//记录路径，Ln表示树的高度，path为0表示取左子树，1表示取右子树

bool CreateBiTree(BiTree &T)
{
	//根据前序创树，‘ * ’表示子树为空
	char ch;
	scanf("%c",&ch);
	if(ch=='*') 
		T=NULL;
	else {
		if(!(T=(BitNode *)malloc(sizeof(BitNode)))) exit(0);
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return true;
}

void LngstPth(BiTree T,Path pth,Path &Lpth)
{
	//求树T的最高的一条路径（深度）
	//pth 记录当前的节点的位置
	//Lpth记录已经遍历过的路径中，最高的路径
	int t;
	if(T==NULL)
	{
		if(Lpth.Ln<pth.Ln)
		{
			for(int i=0;i<pth.Ln-1;i++)
				Lpth.path[i]=pth.path[i];
			Lpth.Ln=pth.Ln;
		}
	}
	else
	{
		t=pth.Ln;
		pth.path[pth.Ln]=0;
		pth.Ln+=1;
		LngstPth(T->lchild,pth,Lpth);
		pth.Ln=t;
		pth.path[pth.Ln]=1;
		pth.Ln+=1;
		LngstPth(T->rchild,pth,Lpth);
	}
}
int Lngst(BiTree T)
{//求T的深度
	int a,b;
	if(T==NULL)
		return 0;
	a=Lngst(T->lchild)+1;
	b=Lngst(T->rchild)+1;
	return a>b?a:b;
}
void Prntp(BiTree T,Path Lp)
{
	//根据路径Lp输出T的节点的值
	BiTree s;
	if(Lp.Ln>0)
	{
		printf("\n %c",T->data);
		s=T;
		for(int i=0;i<Lp.Ln-1;i++)
		{
			if(Lp.path[i]==1)
			{
				s=s->rchild;
				printf("  %c",s->data);
			}
			else
			{
				s=s->lchild;
				printf("  %c",s->data);
			}
		}
	}
	else
	{
		printf("\n Null Tree!\n");
	}
}
void main()
{
	//abc**de*g**f*** 
	BiTree T;
	Path Lp,p;
	CreateBiTree(T);
	Lp.Ln=p.Ln=0;
	LngstPth(T,p,Lp);
	printf("\n");
	Prntp(T,Lp);
	printf("\n");
	//printf("%d",Lngst(T));
}