資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用C++構建二叉樹中兩個節點能夠形成的最大長度環
給定一棵二叉樹，目標是找到這棵樹中的最大長度環。我們將透過找到從根節點開始的左子樹和右子樹的最大高度，並將這些最大長度路徑連線起來以獲得最長環來做到這一點。
對於上面的樹，最大長度環是1-2-3-4-7-6或1-6-7-4-3-2-1。長度是6。
輸入 - 樹
輸出 - 最大長度環是 - 5
解釋 - 左子樹的最大高度是3，右子樹的最大高度是1。環的長度變為3+1+1=5。環是1-2-3-4-6或1-6-4-3-2
輸入 - 樹
輸出 - 最大長度環是 - 7
解釋 - 左子樹的最大高度是3，右子樹的最大高度是3。環的長度變為3+3+1=7。環是5-4-2-1-8-7-6或5-6-7-8-1-2-4-5
下面程式中使用的方法如下
建立一個treenode類，它具有公共資料成員- int data表示節點的權重，left和right treenode指標指向其他此類節點。
函式newNode(int data)將資料作為引數，並建立一個左、右指標為NULL的節點。
透過呼叫newnode()函式建立一棵樹。
函式maxheight(treenode* root)接受樹的根並返回以root為根的樹的最大高度。
此函式檢查根是否為NULL，這意味著高度為0，返回0。
lheight和rheight分別透過遞迴呼叫maxheight(root->left);和maxheight(root->right);計算節點root的左子樹和右子樹的高度。
返回透過比較lheight和rheight獲得的最大值。
在main函式內部，我們儲存樹節點的左子樹和右子樹的最大高度值。
現在，最大長度環是兩個最大高度maxlheight + maxrheight + 1的總和，其中1是包括根節點本身。
列印環的長度作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
//class for tree
class treenode{
public:
int data;
treenode* left;
treenode* right;
};
//find maximum height between left and right subtree of current root
int maxheight(treenode* root){
if (root == NULL)
return 0;
else{
int lheight = maxheight(root->left);
int rheight = maxheight(root->right);
//find maximum height
if (lheight > rheight)
return(lheight + 1);
else
return(rheight + 1);
}
}
//creating a node of tree
treenode* newNode(int data){
treenode* Node = new treenode();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main(){
treenode *root = newNode(6);
root->left = newNode(8);
root->right = newNode(9);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->right = newNode(7);
root->left->right->right->left = newNode(2);
int maxlheight=maxheight(root->left);
int maxrheight=maxheight(root->right);
int maxlheight=maxDepth(root->left);
int maxrheight=maxDepth(root->right);
cout << "Maximum length cycle: " << maxlheight+maxrheight+1;
return 0;
}輸出
Maximum length cycle: 6
更新於：2020年8月3日
194 次瀏覽
廣告