資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學在 C++ 中查詢二叉樹中根到給定結點的距離
考慮一下，我們有一個具有少量結點的二叉樹。我們必須查詢根與另一個結點 u 之間的距離。假設樹如下所示
現在 (root, 6) 之間的距離 = 2，路徑長度為 2，(root, 8) 之間的距離 = 3 等。
為了解決這個問題，我們將使用遞迴方法在左子樹和右子樹中搜索結點，並且還將更新每個級別的長度。
範例
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int getDistance(Node *root, int x) {
if (root == NULL)
return -1;
int dist = -1;
if ((root->data == x) || (dist = getDistance(root->left, x)) >= 0 || (dist = getDistance(root->right, x)) >= 0)
return dist + 1;
return dist;
}
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->right->left = getNode(6);
root->right->right = getNode(7);
root->right->left->right = getNode(8);
cout <<"Distance from root to node 6 is: " << getDistance(root,6);
cout << "\nDistance from root to node 8 is: " << getDistance(root,8);
}輸出
Distance from root to node 6 is: 2 Distance from root to node 8 is: 3
更新於: 19-Dec-2019
312 瀏覽
廣告