数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究使用 C++ 检查二叉树是否为另一二叉树的子树
假设我们有两个二叉树。我们必须检查较小的树是否为另一棵二叉树的子树。考虑给定的这棵二叉树。
共有两棵树。第二棵树是第一棵树的子树。为了检查这个属性，我们将以后序的方式遍历这棵树，然后如果以这个节点为根的子树与第二棵树相同，那么它就是子树。
示例
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node *left, *right;
};
bool areTwoTreeSame(node * t1, node *t2) {
if (t1 == NULL && t2 == NULL)
return true;
if (t1 == NULL || t2 == NULL)
return false;
return (t1->data == t2->data && areTwoTreeSame(t1->left, t2->left) && areTwoTreeSame(t1->right, t2->right) );
}
bool isSubtree(node *tree, node *sub_tree) {
if (sub_tree == NULL)
return true;
if (tree == NULL)
return false;
if (areTwoTreeSame(tree, sub_tree))
return true;
return isSubtree(tree->left, sub_tree) || isSubtree(tree->right, sub_tree);
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
int main() {
node *real_tree = getNode(26);
real_tree->right = getNode(3);
real_tree->right->right = getNode(3);
real_tree->left = getNode(10);
real_tree->left->left = getNode(4);
real_tree->left->left->right = getNode(30);
real_tree->left->right = getNode(6);
node *sub_tree = getNode(10);
sub_tree->right = getNode(6);
sub_tree->left = getNode(4);
sub_tree->left->right = getNode(30);
if (isSubtree(real_tree, sub_tree))
cout << "Second tree is subtree of the first tree";
else
cout << "Second tree is not a subtree of the first tree";
}输出
Second tree is subtree of the first tree
更新于：22-Oct-2019
705 次浏览
广告