用于检查输入的二叉树是否为二叉树的子树的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 好听的元旦简短祝福语