数据结构
网络
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 次浏览
广告