資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
設計學
法學列印 C++ 中兩個二叉搜尋樹中的常見節點
在這個問題中，我們得到了兩棵二叉搜尋樹，我們必須找到那些相同的節點。
二叉樹是一個特殊樹，它的每個節點最多有兩個子節點。因此，每個節點要麼是葉子節點，要麼有一個或兩個子節點。
例如，
在這裡，我們有兩棵二叉樹，我們必須打印出兩棵樹都相同的節點。
讓我們建立一個使用輔助堆疊來查詢此問題的解決方案的程式。它的工作原理是在出現兩個相同值時彈出元素。
示例
#include<iostream>
#include<stack>
using namespace std;
struct Node{
int key;
struct Node *left, *right;
};
Node *newNode(int ele){
Node *temp = new Node;
temp->key = ele;
temp->left = temp->right = NULL;
return temp;
}
void printCommon(Node *tree1, Node *tree2){
stack<Node *> stack1, s1, s2;
while (1){
if (tree1){
s1.push(tree1);
tree1 = tree1->left;
}
else if (tree2){
s2.push(tree2);
tree2 = tree2->left;
}
else if (!s1.empty() && !s2.empty()){
tree1 = s1.top();
tree2 = s2.top();
if (tree1->key == tree2->key){
cout << tree1->key << " ";
s1.pop();
s2.pop();
tree1 = tree1->right;
tree2 = tree2->right;
}
else if (tree1->key < tree2->key){
s1.pop();
tree1 = tree1->right;
tree2 = NULL;
}
else if (tree1->key > tree2->key){
s2.pop();
tree2 = tree2->right;
tree1 = NULL;
}
}
else break;
}
}
void inorderTraversal(struct Node *root){
if (root){
inorderTraversal(root->left);
cout<<root->key<<" ";
inorderTraversal(root->right);
}
}
struct Node* insertNode(struct Node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}
int main(){
Node *tree1 = NULL;
tree1=insertNode(tree1, 45);
tree1=insertNode(tree1, 87);
tree1=insertNode(tree1, 12);
tree1=insertNode(tree1, 54);
tree1=insertNode(tree1, 89);
tree1=insertNode(tree1, 19);
tree1=insertNode(tree1, 72);
cout<<"Binary Tree 1 : ";
inorderTraversal(tree1);
cout<<endl;
Node *tree2=NULL;
tree2=insertNode(tree2, 72);
tree2=insertNode(tree2, 23);
tree2=insertNode(tree2, 13);
tree2=insertNode(tree2, 1);
tree2=insertNode(tree2, 19);
cout<<"Binary Tree 2 : ";
inorderTraversal(tree2);
cout<<endl;
cout<<"Common Nodes between the two trees : ";
printCommon(tree1, tree2);
return 0;
}輸出
Binary Tree 1 : 12 19 45 54 72 87 89 Binary Tree 2 : 1 13 19 23 72 Common Nodes between the two trees : 19 72
更新於： 03-Jan-2020
181 次瀏覽
廣告