房产中介网站开发模板,南通企业网站排名优化,中山网站制作服务,自己做网站需要什么技术问题定义如果我们把二叉树看成一个图#xff0c;父子节点之间的连线看成是双向的#xff0c;我们姑且定义距离为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。计算一个二叉树的最大距离有两个情况:情况A: 路径经过左子树的最深节… 问题定义如果我们把二叉树看成一个图父子节点之间的连线看成是双向的我们姑且定义距离为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。计算一个二叉树的最大距离有两个情况:情况A: 路径经过左子树的最深节点通过根节点再到右子树的最深节点。情况B: 路径不穿过根节点而是左子树或右子树的最大距离路径取其大者。思路1后序遍历每一节点找出该节点到最右边的距离以及最左边的距离2找到之和最大的即可。//需保存左子树中最长距离、右子树最长距离和当前树的深度。//以下提供两种方法。#includeiostream
#includestack
using namespace std;
int max(int l,int r)
{return lr?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 sizearr[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(_rootNULL){return 0;}int maxDistance0;_Distance(_root,maxDistance);return maxDistance;}*/int MaxTwoNodeDistance(){if(_rootNULL)return 0;int maxLeft0;int maxRight0;return _Distance(_root,maxLeft,maxRight);}int Height(){return _Height(_root);}void PreOrder_Non(){if (_root NULL)return;BinaryTreeNode* cur _root;stackBinaryTreeNode* 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(rootNULL){left0;right0;return 0;}int mll,mlr,mrl,mrr,dl,dr;if(root-leftNULL){left0;dl0;}else{dl_Distance(root-left,mll,mlr);leftmax(mll,mlr)1;}if(root-rightNULL){right0;dr0;}else{dr_Distance(root-right,mrl,mrr);rightmax(mrl,mrr)1;}return max(max(dl,dr),leftright);}/*int _Distance(BinaryTreeNode* root,int max){if(rootNULL)return 0;int maxLeft0;int maxRight0;if(root-left){maxLeft_Distance(root-left,max);if(maxLeftmax)maxmaxLeft;}if(root-right){maxRight_Distance(root-right,max);if(maxRightmax)maxmaxRight;}if(maxLeftmaxRightmax)maxmaxLeftmaxRight;return maxLeftmaxRight?maxLeft1:maxRight1; }*/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();coutt1.MaxTwoNodeDistance()endl;BinaryTree t2(arr2,sizeof(arr2)/sizeof(arr2[0]));t2.PreOrder_Non();coutt2.MaxTwoNodeDistance()endl;
} 转载于:https://blog.51cto.com/10541556/1835793
