二叉树最长路径.cpp

本程序实现求二叉树的最长路径

#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
	ElemType data;
	struct node *lchild;
	struct node *rchild;
}*BTNode;
void CreateBTNode(BTNode &b,char *str)
{
	BTNode St[MaxSize],p=NULL;
	int top=-1,k,j=0;
	char ch;
	b=NULL;
	ch=str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		    case'(':top++;St[top]=p;k=1;break;
		    case')':top--;break;
            case',':k=2;break;
			default:p=(BTNode)malloc(sizeof(node));
			    p->data=ch;
				p->lchild=p->rchild=NULL;
				if(b==NULL)
					b=p;
				else
				{
					switch(k)
					{
					     case 1:St[top]->lchild=p;break;
					     case 2:St[top]->rchild=p;break;
					}
				}

		}
		j++;
		ch=str[j];
	}
}

void DispBTNode(BTNode b)
{
	if(b!=NULL)
	{
		printf("%c",b->data);
		if(b->lchild!=NULL||b->rchild!=NULL)
		{
			printf("(");
			DispBTNode(b->lchild);
			if(b->rchild !=NULL)
				printf(",");
			DispBTNode(b->rchild);
			printf(")");
		}
	}
}

/*void AllPath1(BTNode b,ElemType path[],int pathlen)
{
	int i;
	if(b!=NULL)
	{
		if(b->lchild==NULL&&b->rchild==NULL)
		{
			printf(" %c到根节点路径： %c",b->data,b->data);
			for(i=pathlen-1;i>=0;i--)
				printf("%c",path[i]);
			printf("\n");
		}
		else
		{
			path[pathlen]=b->data;
			pathlen++;
			AllPath1(b->lchild,path,pathlen);
            AllPath1(b->rchild,path,pathlen);
			pathlen--;
		}
	}
}*/
void LongPath(BTNode b,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen)
{
	int i;
	if(b==NULL)
	{
		if(pathlen>longpathlen)
		{
			for(i=pathlen-1;i>=0;i--)
				longpath[i]=path[i];
			longpathlen=pathlen;
		}
	}
	else
	{
		path[pathlen]=b->data;
		pathlen++;
		LongPath(b->lchild,path,pathlen,longpath,longpathlen);
        LongPath(b->rchild,path,pathlen,longpath,longpathlen);
		pathlen--;
	}
}
void main()
{
	BTNode b;
	ElemType path[MaxSize],longpath[MaxSize];
	int i,longpathlen=0;
	CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
	printf("(1)输出二叉树：");
	DispBTNode(b);
    printf("\n");
	//printf("AllPath1: \n");
    //AllPath1(b,path,0);
	printf("\n");
	LongPath(b,path,0,longpath,longpathlen);
    printf("第一条最长路径长度：%d\n",longpathlen);
	printf("第一条最长路径： ");
	for(i=longpathlen-1;i>=0;i--)
		printf("%c",longpath[i]);
	printf("\n");

    
}