面试题目：输入两颗二叉树A，B，判断B是不是A的子结构；
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <iostream>
#include <stack>
using
namespace
std;
typedef
struct
BinaryTreeNode{
int
value;
BinaryTreeNode * lchild;
BinaryTreeNode *rchild;
}BinaryTreeNode;
typedef
BinaryTreeNode * BiTree;
void
CreateBiTreeByLevel(BiTree &t,
int
Array[],
int
i,
int
len)
{
if
(Array[i]==0||i > len)
return
;
t =
new
BinaryTreeNode;
t->value = Array[i];
t->lchild = NULL;
t->rchild = NULL;
CreateBiTreeByLevel(t->lchild,Array,2*i,len);
CreateBiTreeByLevel(t->rchild,Array,2*i+1,len);
}
void
display(BiTree *t)
//显示树形结构
{
if
(*t!=NULL)
{
cout<<(*t)->value;
if
((*t)->lchild!=NULL)
{
cout<<
'('
;
display(&(*t)->lchild);
}
if
((*t)->rchild!=NULL)
{
cout<<
','
;
display(&(*t)->rchild);
cout<<
')'
;
}
}
}
bool
ifTheSameTree(BiTree &t1,BiTree &t2)
{
if
(t2 == NULL)
return
true
;
//B树为空，肯定是相同的树
if
(t1 == NULL)
return
false
;
if
(t1->value!=t2->value)
return
false
;
//节点不同，不是
else
{
return
ifTheSameTree(t1->lchild,t2->lchild) & ifTheSameTree(t1->rchild,t2->rchild);
//左右均为true返回true
}
}
bool
isSubBinTree(BiTree &t1,BiTree &t2)
{
bool
result =
false
;
if
(t1 != NULL && t2 != NULL)
{
if
(t1->value == t2->value)
//根节点相同，就判断A，B树是否一样
{
result = ifTheSameTree(t1,t2);
}
if
(!result)result = isSubBinTree(t1->lchild,t2);
//判断左子树
if
(!result) result = isSubBinTree(t1->rchild,t2);
//判断右子树
}
return
result;
}
int
main()
{
BiTree A,B;
//InitBiTree(&T);
int
a[14] = {0,1,2,3,4,5,6,0,0,0,7,0,8,9};
//从下标1开始，0标识没有节点
int
b[4] = {0,6,8,9};
CreateBiTreeByLevel(A,a,1,13);
CreateBiTreeByLevel(B,b,1,2);
display(&A);
display(&B);
if
(isSubBinTree(A,B))cout<<
"B is A subTree"
;
else
cout<<
"B is Not A subTree"
;
system
(
"pause"
);
}
|
来源：http://blog.csdn.net/xiaobo620/article/details/7957539
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3361532.html，如需转载请自行联系原作者
