A-A+

求二叉树中两个节点的最远距离

2016年08月10日 Linux 教程 暂无评论 阅读 519 次

问题定义
如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
计算一个二叉树的最大距离有两个情况:

情况A: 路径经过左子树的最深节点,通过根节点,再到右子树的最深节点。

情况B: 路径不穿过根节点,而是左子树或右子树的最大距离路径,取其大者。

思路:
1,后序遍历每一节点,找出该节点到最右边的距离以及最左边的距离;
2,找到之和最大的即可。
//需保存左子树中最长距离、右子树最长距离和当前树的深度。
//以下提供两种方法。

#include<iostream>
#include<stack>
using namespace std;
int max(int l,int r)
{
    return l>r?l:r;
}
struct BinaryTreeNode
{
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int x)
        :data(x)
        , left(NULL)
        , right(NULL)
    {}
};
class BinaryTree
{
protected:
    BinaryTreeNode* _root;
    BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
    {
        BinaryTreeNode* root = NULL;
        if (index < size&&arr[index] != '#')
        {
            root = new BinaryTreeNode(arr[index]);
            root->left = _CreateBinaryTree(arr, ++index, size);
            root->right = _CreateBinaryTree(arr, ++index, size);
        }
        return root;
    }
     
public:
    BinaryTree()
        :_root(NULL)
    {}
    BinaryTree(int *arr, int size)
    {
        int index = 0;
        _root = _CreateBinaryTree(arr, index, size);
    }
    /*int MaxTwoNodeDistance()
    {
        if(_root==NULL)
        {
            return 0;
        }
        int maxDistance=0;
        _Distance(_root,maxDistance);
        return maxDistance;
    }*/
    int MaxTwoNodeDistance()
    {
        if(_root==NULL)
            return 0;
        int maxLeft=0;
        int maxRight=0;
        return _Distance(_root,maxLeft,maxRight);
    }
    int Height()
    {
        return _Height(_root);
    }
    void PreOrder_Non()
    {
        if (_root == NULL)
            return;
        BinaryTreeNode* cur = _root;
        stack<BinaryTreeNode*> s;
        s.push(_root);
        while (!s.empty())
        {
            cur = s.top();
            printf("%d ", cur->data);
            s.pop();
            if (cur->right)
                s.push(cur->right);
            if (cur->left)
                s.push(cur->left);
        }
        cout << endl;
    }
protected:
    int _Distance(BinaryTreeNode* root,int& left,int &right)
    {
        if(root==NULL)
        {
            left=0;
            right=0;
            return 0;
        }
        int mll,mlr,mrl,mrr,dl,dr;
        if(root->left==NULL)
        {
            left=0;
            dl=0;
        }
        else
        {
            dl=_Distance(root->left,mll,mlr);
            left=max(mll,mlr)+1;
        }
         
        if(root->right==NULL)
        {
            right=0;
            dr=0;
        }
        else
        {
            dr=_Distance(root->right,mrl,mrr);
            right=max(mrl,mrr)+1;
        }
        return max(max(dl,dr),left+right);
    }
    /*int _Distance(BinaryTreeNode* root,int& max)
    {
        if(root==NULL)
            return 0;
        int maxLeft=0;
        int maxRight=0;
        if(root->left)
        {
            maxLeft=_Distance(root->left,max);
            if(maxLeft>max)
                max=maxLeft;
        }
        if(root->right)
        {
            maxRight=_Distance(root->right,max);
            if(maxRight>max)
                max=maxRight;
        }
        if(maxLeft+maxRight>max)
            max=maxLeft+maxRight;
        return maxLeft>maxRight?maxLeft+1:maxRight+1;   
    }*/
    int _Height(BinaryTreeNode* root)
    {
        if (root == NULL)
            return 0;
        int left = _Height(root->left);
        int right = _Height(root->right);
        return left > right ? left + 1 : right + 1;
    }
   
};
int main()
{
    int arr1[]={1,2,4,5,'#','#','#',7,'#','#',3,'#',6};
    int arr2[]={1,2,3,4,'#','#','#',5,'#',6};
    BinaryTree t1(arr1,sizeof(arr1)/sizeof(arr1[0]));
    t1.PreOrder_Non();
    cout<<t1.MaxTwoNodeDistance()<<endl;
    BinaryTree t2(arr2,sizeof(arr2)/sizeof(arr2[0]));
    t2.PreOrder_Non();
    cout<<t2.MaxTwoNodeDistance()<<endl;
}

标签:

给我留言

Copyright © SEARU.ORG 保留所有权利.   Theme  Ality 网站地图 360网站安全检测平台

用户登录

分享到: