第五章 树——二叉树最大路径长度和最大带权路径和

第五章 二叉树的最大路径长度和最大带权路径和

1、二叉树的最大路径长度：

给定一棵二叉树，在树中一定存在两个距离最远的叶子节点。这就是二叉树的最大路径长度。
路径A： 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
路径B:路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。

【路径A（最大路径6）如图所示:】

【路径B（最大路径4）如图所示:】

//求二叉树的带权路径长度
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MaxSize 100
//二叉树的链式存储结构
typedef struct BiTNode
{
    char data;
    int  weight;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
//创建二叉树
int CreateBiTree(BiTree &T)
{
    char ch;
    int x;
    cin >> ch;
    if(ch=='#')
    {
        T=NULL;
    }
    else
    {
        cin >> x;
        T=new BiTNode;
        T->data=ch;
        T->weight=x;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return 0;
}
//先序遍历（根左右）
void PreorderTraversal(BiTree T)
{
    if(T)
    {
        printf("%c",T->data);
        printf("(%d)",T->weight);
        PreorderTraversal(T->lchild);
        PreorderTraversal(T->rchild);
    }

}
//求二叉树最长路径长度
int MaxDistance(BiTree T,int *max)
{
    if(T->lchild==NULL&&T->rchild==NULL)
        return 0;
    int left_len=0,right_len=0;
    if(T->lchild !=NULL)
    {
        left_len=MaxDistance(T->lchild,max)+1;
    }
    if(T->rchild !=NULL)
    {
        right_len=MaxDistance(T->rchild,max)+1;
    }
    int sum=left_len+right_len;
    *max=(*max>sum)?*max:sum;
    return (left_len>right_len)?left_len:right_len;
}

int main()
{
    BiTree T;
    int max=0;
    int deep=0;
    cout<<"请输入先序遍历建立二叉树的节点"<<endl;
    CreateBiTree(T);
    printf("先序遍历打印二叉树\n");
    PreorderTraversal(T);
    cout<<endl;
    MaxDistance(T,&max);
    printf("从任意节点出发的二叉树的最大距离：");
    printf("%d\n", max);
    return 0;
}

情形一运行结果：

情形二运行结果：

2、二叉树的最大带权路径和：

//求二叉树的带权路径长度
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MaxSize 100
//二叉树的链式存储结构
typedef struct BiTNode
{
    char data;
    int  weight;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
//创建二叉树
int CreateBiTree(BiTree &T)
{
    char ch;
    int x;
    cin >> ch;
    if(ch=='#')
    {
        T=NULL;
    }
    else
    {
        cin >> x;
        T=new BiTNode;
        T->data=ch;
        T->weight=x;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    return 0;
}
//先序遍历（根左右）
void PreorderTraversal(BiTree T)
{
    if(T)
    {
        printf("%c",T->data);
        printf("(%d)",T->weight);
        PreorderTraversal(T->lchild);
        PreorderTraversal(T->rchild);
    }

}
//求二叉树最长路径长度和
int MaxPathSum(BiTree T,int *maxsum)
{
    int val=T->weight;
    if(T->lchild==NULL&&T->rchild==NULL)
        return val;
    int left=0,right=0;
    if(T->lchild !=NULL)
    {
        left=MaxPathSum(T->lchild,maxsum)+val;
    }
    if(T->rchild !=NULL)
    {
        right=MaxDistance(T->rchild,maxsum)+val;
    }
    int sum=left+right;
    *maxsum=(*maxsum>sum)?*maxsum:sum;
    return (left>right)?left:right;
}
int main()
{
    BiTree T;
    int maxsum=0;
    cout<<"请输入先序遍历建立二叉树的节点"<<endl;
    CreateBiTree(T);
    printf("先序遍历打印二叉树\n");
    PreorderTraversal(T);
    cout<<endl;
    MaxPathSum(T,&maxsum);
    printf("从任意节点出发的二叉树的最大带权路径和：");
    printf("%d\n", maxsum);
    return 0;
}