数据结构——二叉树的最长路径问题

傷城~ 2022-12-24 04:58 197阅读 0赞

#### 题目： ####

求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。  
描述  
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写算法求出该二叉树中第一条最长的路径。

输入  
一行数据，为二叉树的先序序列（序列中元素为‘\#’时，表示该结点为空）。  
输出  
第一行为二叉树的最长路径长度，第二行为此路径上从根到叶结点的各结点的值。  
思路：（递归）

1.  函数longest\_path(BiTree T,int \*path,int &len,int \*longestpath,int &longest\_len)  
    **//char path\[\] 每次循环得到的路径  
    //char longestpath\[\]最长路径  
    //int &longest\_len最长路径的大小  
    //int &len每次循环得到的路径的大小**
2.  代码运行时：*遇到的不是叶子结点，该条路径继续  
    path\[len++\]T->data;再递归调用该函数，这个节点的左子树，右子树；*
3.  *遇到的时叶子结点时，该条路径结束，与之前的最长路径比较，更新最长路径（可能会）；*

求最长路径算法（核心代码）

void longest_path(BiTree T,int *path,int &len,int *longestpath,int &longest_len)
    {
        
    	if(T!=NULL)
    	{
        
    		if(T->lchild==NULL&&T->rchild==NULL)//当遇到叶子结点时，该条路径完毕 
    		{
        
    			path[len]=T->data;
    			if(len>longest_len)//如果长于longest_len就替换 
    			{
        
    				for(int j=0;j<=len;j++)
    				{
        
    					longestpath[j]=path[j];
    				}
    				longest_len=len;//longest_len更新 
    			}
    		}
    		else//当遇到的不是叶子结点时，该条路径继续 
    		{
        
    			path[len++]=T->data;
    			longest_path(T->lchild ,path,len,longestpath,longest_len);
    			longest_path(T->rchild ,path,len,longestpath,longest_len);
    			len--;
    		}
    	}
    }

全部可执行代码

#include<stdio.h>
    #include<bits/stdc++.h> 
    #define MAX  200
    typedef char TElemType;
    typedef int status; 
    typedef struct BiNode
    {
        
    	TElemType data;
    	struct BiNode *lchild;
    	struct BiNode *rchild;
    }BiNode,*BiTree;
    void CreateBiTree(BiTree &T)//二叉树的先序创建 
    {
        
    	TElemType ch;
    	scanf("%c",&ch);
    	if(ch=='#')
    		T=NULL;
    	else 
    	{
        
    		T=(BiNode*)malloc(sizeof(BiNode));
    		if(!T)
    			exit(-1);
    		T->data=ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    void longest_path(BiTree T,int *path,int &len,int *longestpath,int &longest_len)
    {
        
    	if(T!=NULL)
    	{
        
    		if(T->lchild==NULL&&T->rchild==NULL)//当遇到叶子结点时，该条路径完毕 
    		{
        
    			path[len]=T->data;
    			if(len>longest_len)//如果长于longest_len就替换 
    			{
        
    				for(int j=0;j<=len;j++)
    				{
        
    					longestpath[j]=path[j];
    				}
    				longest_len=len;//longest_len更新 
    			}
    		}
    		else//当遇到的不是叶子结点时，该条路径继续 
    		{
        
    			path[len++]=T->data;
    			longest_path(T->lchild ,path,len,longestpath,longest_len);
    			longest_path(T->rchild ,path,len,longestpath,longest_len);
    			len--;
    		}
    	}
    }
    int main()
    {
        
    	BiTree T;
    	printf("创建树输入树T的先序序列(其中使用#代表空节点)\n");
    	CreateBiTree(T);
    	int path[MAX]={
        0};
    	int longestpath[MAX]={
        0};
    	int len=0;
    	int longest_len=0;
    	longest_path(T,path,len,longestpath,longest_len);
    	printf("第一条最长的路径长度为：%d\n",longest_len);
    	printf("路径为："); 
    	for(int i=0;i<=longest_len;i++)
    	{
        
    		
    		printf("%c ->",longestpath[i]);
    	}
    	printf("NULL");
    	
    }

![在这里插入图片描述][2020112621015542.png_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]

[2020112621015542.png_pic_center]: /images/20221120/2f349e37468a4e4998ab615af4114251.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6b3de6e45c294f359cf15203ff95b442.png