您好,登錄后才能下訂單哦!
如果我們把二叉樹看成一個(gè)圖,父子節(jié)點(diǎn)之間的連線看成是雙向的,我們姑且定義"距離"為兩節(jié)點(diǎn)之間邊的個(gè)數(shù)。寫一個(gè)程序求一棵二叉樹中相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的距離。
計(jì)算一個(gè)二叉樹的最大距離有兩個(gè)情況:
情況A: 路徑經(jīng)過左子樹的最深節(jié)點(diǎn),通過根節(jié)點(diǎn),再到右子樹的最深節(jié)點(diǎn)。
情況B: 路徑不穿過根節(jié)點(diǎn),而是左子樹或右子樹的最大距離路徑,取其大者。
思路:
1,后序遍歷每一節(jié)點(diǎn),找出該節(jié)點(diǎn)到最右邊的距離以及最左邊的距離;
2,找到之和最大的即可。
//需保存左子樹中最長距離、右子樹最長距離和當(dāng)前樹的深度。
//以下提供兩種方法。
#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; }
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。