資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究查詢葉節點在 C++ 中連線的特殊二叉樹高度
假設我們有一棵特殊的二叉樹，其葉節點連線形成圓形雙向連結串列。我們必須找到它的高度。因此，最左側的葉的左指標將作為圓形雙向連結串列的前一個指標，其右指標將作為連結串列的下一個指標。
在這種情況下，高度查詢策略類似於普通的二叉搜尋樹。我們遞迴地計算節點的左子樹和右子樹的高度，並將高度分配給節點，為兩個子節點的最大值 + 1。但在這裡，葉是圓形雙向連結串列中的元素。因此，對於一個節點成為葉節點，我們檢查節點左側的右側是否指向該節點，以及其右側的左側是否指向節點自身。
示例
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
bool isLeafNode(Node* node) {
return node->left && node->left->right == node && node->right && node->right->left == node;
}
int findHeight(Node* node) {
if (node == NULL)
return 0;
if (isLeafNode(node))
return 1;
return 1 + max(findHeight(node->left), findHeight(node->right));
}
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->left->left->left = getNode(6);
Node *L1 = root->left->left->left;
Node *L2 = root->left->right;
Node *L3 = root->right;
L1->right = L2, L2->right = L3, L3->right = L1;
L3->left = L2, L2->left = L1, L1->left = L3;
cout << "Height of tree is: " << findHeight(root);
}輸出
Height of tree is: 4
更新日期： 2019 年 12 月 17 日
166 次瀏覽
廣告