用于检查输入的二叉树是否为二叉树的子树的C ++程序
二叉树是一种树数据结构，其中每个节点最多具有两个子节点，这两个子节点被定义为左子节点和右子节点。
算法
Begin
function identical():
Take two nodes r1 and r2 as parameter.
If r1 and r2 is NULL then
Return true.
If r1 or r2 is NULL then
Return false.
Return (r1->d is equal to r2->d and
Call function Identical(r1->l, r2->l) and
Call functions Identical(r1->r, r2->r) );
function Subtree(node *T, node *S) :
if (S == NULL) then
return true;
if (T == NULL) then
return false;
if (call function Identical(T, S))
return true;
return Subtree(T->l, S) or Subtree(T->r, S);
End.范例程式码
#include <iostream>
using namespace std;
struct n {
int d;
struct n* l;
struct n* r;
};
bool Identical(struct n * r1, struct n *r2) {
if (r1 == NULL && r2 == NULL)
return true;
if (r1 == NULL || r2 == NULL)
return false;
return (r1->d == r2->d && Identical(r1->l, r2->l) && Identical(r1->r, r2->r) );
}
bool Subtree(struct n *T, struct n *S) {
if (S == NULL)
return true;
if (T == NULL)
return false;
if (Identical(T, S))
return true;
return Subtree(T->l, S) || Subtree(T->r, S);
}
struct n* newN(int d) {
struct n* nod =
(struct n*)malloc(sizeof(struct n));
nod->d = d;
nod->l = NULL;
nod->r = NULL;
return(nod);
}
int main() {
struct n *T = newN(24);
T->r = newN(2);
T->r->r = newN(5);
T->l = newN(7);
T->l->l = newN(3);
T->l->l->r = newN(40);
T->l->r = newN(6);
struct n *S = newN(20);
S->r = newN(5);
S->l = newN(3);
S->l->r = newN(50);
if (Subtree(T, S))
cout<<"given tree is subtree of Binary tree"<<"\n";
else
cout<<"given tree is not subtree of Binary tree"<<"\n";
struct n *T1 = newN(30);
T1->r = newN(20);
T1->r->r = newN(19);
T1->l = newN(17);
T1->l->l = newN(4);
T1->l->l->r = newN(40);
T1->l->r = newN(15);
struct n *S1 = newN(17);
S1->r = newN(15);
S1->l = newN(4);
S1->l->r = newN(40);
if (Subtree(T1, S1))
cout<<"given tree is subtree of Binary tree";
else
cout<<"given tree is not subtree of Binary tree";
getchar();
return 0;
}输出结果
given tree is not subtree of Binary tree given tree is subtree of Binary tree
热门推荐
10 六十岁大寿祝福语简短
11 圣诞饭店祝福语大全简短
12 女生成年祝福语简短
13 恭喜朋友买车祝福语简短
14 老爸生日暴富祝福语简短
15 祝福语怎么写大全简短
16 明信片祝福语简短句子
17 送蛇的祝福语简短
18 分别祝福语简短情侣短句