資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告