資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 程式設計中列印二叉樹中任意兩個節點之間的路徑。
我們給定一個具有不同節點的二叉樹，以及二叉樹的兩個節點，我們希望列印這兩個節點在二叉樹中的路徑。
例如 - 我們希望列印從節點 140 到 211 的路徑，因此其輸出應類似於 -
Output: 140->3->10->211
這個想法是從根節點找到到這兩個節點的路徑，並將它們儲存在兩個單獨的向量或陣列中，例如 path1 和 path2。
現在，出現了兩種不同的情況 -
- 如果兩個節點位於根節點的不同子樹中 - 當兩個節點位於不同的子樹中，例如一個在左邊，另一個在右邊。在這種情況下，很明顯，根節點將位於從節點 1 到節點 2 的路徑之間。因此，以相反的順序列印 path1，然後列印 path2。
如果節點位於同一子樹中 - 當兩個節點都位於同一子樹中時，這可以是左子樹或右子樹。在這種情況下，您需要觀察從根節點到這兩個節點的路徑將在某個交點之前是兩個節點從根節點的公共路徑。我們必須找到交點並像上面那樣列印從該點開始的節點。
演算法
START STEP 1-> DEFINE A struct Node WITH int data AND Node *left, *right; STEP 2-> DEFINE A TREE STRUCTURE struct Node* tree(int data)FUNCTION bool path(Node* root, vector& arr, int x) STEP 1-> IF root IS NULL RETURN false END IF STEP 2-> arr.push_back(root->data) IF root->data == x THEN RETURN true END IF STEP 3-> IF path(root->left, arr, x) || path(root->right, arr, x) THEN, RETURN true STEP 4-> arr.pop_back() return false END FUNCTION FUNCTION void printPath(Node* root, int n1, int n2) STEP 1-> DEFINE A vector<int> path1 STEP 2-> DEFINE A vector<int> path2 STEP 3-> CALL FUNCTION path(root, path1, n1) STEP 4-> CALL FUNCTION path(root, path2, n2) STEP 5-> DEFINE AND SET intersection = -1, i = 0, j = 0 STEP 6-> LOOP WHILE i != path1.size() || j != path2.size() IF i == j && path1[i] == path2[j] INCREMENT i BY 1 INCREMENT j BY 1 ELSE SET intersection = j - 1 BREAK; END IF END WHILE STEP 7-> LOOP FOR i = path1.size() – 1 AND i > intersection AND i--PRINT path1[i] END FOR STEP 8-> LOOP FOR i = intersection AND i < path2.size() AND i++ PRINT path2[i] END FOR
示例
#include <bits/stdc++.h>
using namespace std;
// structure of a node of binary tree
struct Node {
int data;
Node *left, *right;
};
struct Node* tree(int data){
struct Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
bool path(Node* root, vector<int>& arr, int x){
if (!root)
return false;
// push the node's value in 'arr'
arr.push_back(root->data);
// if it is the required node
// return true
if (root->data == x)
return true;
if (path(root->left, arr, x) || path(root->right, arr, x))
return true;
arr.pop_back();
return false;
}
// Function to print the path between
// any two nodes in a binary tree
void printPath(Node* root, int n1, int n2){
// vector to store the path
vector<int> path1;
vector<int> path2;
path(root, path1, n1);
path(root, path2, n2);
int intersection = -1;
int i = 0, j = 0;
while (i != path1.size() || j != path2.size()) {
if (i == j && path1[i] == path2[j]) {
i++;
j++;
} else {
intersection = j - 1;
break;
}
}
// Print the required path
for (int i = path1.size() - 1; i > intersection; i--)
cout << path1[i] << " ";
for (int i = intersection; i < path2.size(); i++)
cout << path2[i] << " ";
}
int main(){
// binary tree formation
struct Node* root = tree(1);
root->left = tree(2);
root->left->left = tree(4);
root->left->left->left = tree(6);
root->left->right = tree(5);
root->left->right->left = tree(7);
root->left->right->right = tree(8);
root->right = tree(3);
root->right->left = tree(9);
root->right->right = tree(10);
int node1 = 5;
int node2 = 9;
printPath(root, node1, node2);
return 0;
}輸出
此程式將列印輸出 -
5 2 1 3 9
更新於: 2019-09-04
389 次瀏覽
廣告