C language is used to determine whether a binary tree is a substructure of another
- 2020-04-02 03:14:41
- OfStack
1. Problem description:
How do you tell if a binary tree is a substructure of another?
Such as:
2
/
\
9
8
/ \
/
2
3
5
/
6
There are substructures that are
9
/ \
2
3
2. Analysis of problems:
The algorithm problem of binary tree can be solved by recursion. So to write a correct recursive program, you must first analyze the conditions for the correct end of the recursion.
In this case, when does the recurrence end?
< 1 > When root2 of the second binary tree is empty, it means that root2 is a substructure of root1 of the first binary tree, and returns true.
< 2 > When root1 is empty and root2 is not empty, it means that root2 is not a substructure of root1 and returns false.
< 3 > Here are two ideas for recursion:
Method 1: now find the node whose value is the same as that of root2 in root1, and if so, determine whether root2 is a substructure at the beginning of this node. So, first IsSubTree() judgment.
Method two: is the direct judgment, the same recursively determine the root2 around the subtree is also the corresponding substructure. If the values are different, recurse to the left and right subtrees of root1, respectively. Pay particular attention to the logic of the recursion in the last two sentences.
3. Examples of exercises
Title description:
Input two binary trees A and B to determine whether B is A substructure of A.
Input:
The input may contain multiple test samples, ending with EOF.
For each test case, the first line of input is an integer n,m(1)
<
= n
<
= 1000, 1
<
= m.
<
=1000) : n represents the number of nodes of the binary tree A to be input (the node counts from 1), and m represents the number of nodes of the binary tree B to be input (the node counts from 1). The next row has n Numbers, each number represents the value of the ith element in the A tree, followed by n rows, the first number Ki represents the number of children of the ith node, followed by Ki trees representing the number of children of node I. The next m+1 line is the same as tree A.
Output:
For each test case,
If B is A subtree of A, output "YES" (without quotes). Otherwise, output "NO" (without quotes).
Sample input:
July 3
8, 8, 7, 9, 2, 4, 7
2, 2, 3,
2, 4, 5
0
0
2 June 7
0
0
8 and 9 2
2, 2, 3,
0
0
implementation
The first step is to find the same value as the root node of B in tree A, which is actually the preorder traversal of the tree. It is recommended to recurse, which is convenient.
int judgeChildTree(struct btree *ahead, int numa, struct btree *bhead, int numb)
{
int flag = 0;
if (numa != -1 && numb != -1) {
if (ahead[numa].value == bhead[numb].value)
flag = doesTree1HasTree2(ahead, numa, bhead, numb);
if (! flag && ahead[numa].lchild != -1)
flag = judgeChildTree(ahead, ahead[numa].lchild, bhead, numb);
if (! flag && ahead[numa].rchild != -1)
flag = judgeChildTree(ahead, ahead[numa].rchild, bhead, numb);
}
return flag;
}
The second step is to further determine whether the subtree with R as the root node in A has the same node as the B tree
int doesTree1HasTree2(struct btree *ahead, int numa, struct btree *bhead, int numb)
{
if (numb == -1)
return 1;
if (numa == -1)
return 0;
if (ahead[numa].value != bhead[numb].value)
return 0;
return (doesTree1HasTree2(ahead, ahead[numa].lchild, bhead, bhead[numb].lchild) &&
doesTree1HasTree2(ahead, ahead[numa].rchild, bhead, bhead[numb].rchild));
}
The complete code
#include <stdio.h>
#include <stdlib.h>
//Binary tree node definition
struct btree
{
int value;
int lchild, rchild;
};
//The maximum number of nodes of A and B trees
int n, m;
int doesTree1HasTree2(struct btree *ahead, int numa, struct btree *bhead, int numb)
{
if (numb == -1)
return 1;
if (numa == -1)
return 0;
if (ahead[numa].value != bhead[numb].value)
return 0;
return (doesTree1HasTree2(ahead, ahead[numa].lchild, bhead, bhead[numb].lchild) &&
doesTree1HasTree2(ahead, ahead[numa].rchild, bhead, bhead[numb].rchild));
}
int judgeChildTree(struct btree *ahead, int numa, struct btree *bhead, int numb)
{
int flag = 0;
if (numa != -1 && numb != -1) {
if (ahead[numa].value == bhead[numb].value)
flag = doesTree1HasTree2(ahead, numa, bhead, numb);
if (! flag && ahead[numa].lchild != -1)
flag = judgeChildTree(ahead, ahead[numa].lchild, bhead, numb);
if (! flag && ahead[numa].rchild != -1)
flag = judgeChildTree(ahead, ahead[numa].rchild, bhead, numb);
}
return flag;
}
int main(void)
{
int i, data, count, left, right, flag;
struct btree *ahead, *bhead;
while (scanf("%d %d", &n, &m) != EOF) {
//Gets the node value of the A tree
ahead = (struct btree *)malloc(sizeof(struct btree) * n);
for (i = 0; i < n; i ++) {
scanf("%d", &data);
ahead[i].value = data;
ahead[i].lchild = ahead[i].rchild = -1;
}
for (i = 0; i < n; i ++) {
scanf("%d", &count);
if (count == 0) {
continue;
} else {
if (count == 1) {
scanf("%d", &left);
ahead[i].lchild = left - 1;
} else {
scanf("%d %d", &left, &right);
ahead[i].lchild = left - 1;
ahead[i].rchild = right - 1;
}
}
}
//Gets the node value of the B tree
bhead = (struct btree *)malloc(sizeof(struct btree) * m);
for (i = 0; i < m; i ++) {
scanf("%d", &data);
bhead[i].value = data;
bhead[i].lchild = bhead[i].rchild = -1;
}
for (i = 0; i < m; i ++) {
scanf("%d", &count);
if (count == 0) {
continue;
} else {
if (count == 1) {
scanf("%d", &left);
bhead[i].lchild = left - 1;
} else {
scanf("%d %d", &left, &right);
bhead[i].lchild = left - 1;
bhead[i].rchild = right - 1;
}
}
}
//Determine if the B tree is A subtree of A
if (n == 0 || m == 0) {
printf("NOn");
continue;
}
flag = judgeChildTree(ahead, 0, bhead, 0);
if (flag)
printf("YESn");
else
printf("NOn");
free(ahead);
free(bhead);
}
return 0;
}