用于检查输入的二叉树是否为二叉树的子树的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 50多岁生日简短祝福语
13 安徽疫情祝福语简短英语
14 农民朋友发财祝福语简短
15 对生活祝福语简短精辟
16 搬家词简短祝福语朋友
17 女神结婚快乐祝福语简短
18 文学短句祝福语大全简短