0%

重建二叉树

问题描述

用先序序列和中序序列构建二叉树,采用二叉链表存储。编写递归算法,交换二叉树的左右子树,
输出新二叉树按先序遍历得到的结果。

提交格式:实现void solve(int n, int *preOrder, int *inOrder, int *outOrder)函数。
函数参数为序列长度n、先序序列preOrder、中序序列inOrder和输出序列outOrder。1<=n<=1000000,树的深度<=2000。请不要printf输出任何内容。

实现思路
测试主函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
int N;
scanf_s("%d", &N);
int* pre = (int*)malloc(N * sizeof(int));
if (pre == NULL) return 0;
int* in = (int*)malloc(N * sizeof(int));
if (in == NULL) return 0;
int* out = (int*)malloc(N * sizeof(int));
if (out == NULL) return 0;
for (int i = 0; i < N; i++)
{
scanf_s("%d", &pre[i]);
}
for (int j = 0; j < N; j++)
{
scanf_s("%d", &in[j]);
}
solve(N, pre, in, out);
printf("\n");
return 0;
}
solve函数
1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(int n, int* preOrder, int* inOrder, int* outOrder)
{
PBiTNode root=NULL;
if (n <= 0 || preOrder==NULL|| inOrder==NULL|| outOrder==NULL)
{
return;
}
else
{
CreatepostBiTree(preOrder, inOrder, 0, n - 1, 0, n - 1, root);
PreOrder(root, outOrder);
}
}
CreatepostBiTree函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t) 
{
/* 先序序列中从i到j,中序序列从k到h,建立一棵二叉树放在t中*/
int m;
t = (BiTNode*)malloc(sizeof(BiTNode));
if (t == NULL) return ;
t->data = preord[i]; /*二叉树的根*/
m = k;
while (inord[m] != preord[i]) m++; /*在中序序列中定位树的根*/
/*递归调用建立左子树*/
if (m == k) t->lchild = NULL; /*左子树空*/
else CreatepostBiTree(preord, inord, i + 1, i + m - k, k, m - 1, (t->lchild));
/*递归调用建立右子树*/
if (m == h) t->rchild = NULL; /*右子树空*/
else CreatepostBiTree(preord, inord, i + m - k + 1, j, m + 1, h, (t->rchild));
}
PreOrder函数
1
2
3
4
5
6
7
8
9
void PreOrder(PBiTNode bt, int* out1)
{
if (bt != NULL) { /* 如果bt为空,结束*/
out1[s++] = bt->data; /*访问根结点*/
printf("%d ", bt->data);
PreOrder(bt->rchild, out1); /*先序遍历左子树(递归调用)*/
PreOrder(bt->lchild, out1); /*先序遍历右子树(递归调用)*/
}
}
初步实现
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
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node* lchild;
struct Node* rchild;
}BiTNode, * PBiTNode;
int s = 0;
void PreOrder(PBiTNode bt, int* out1);
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t);
void solve(int n, int* preOrder, int* inOrder, int* outOrder)
{
PBiTNode root=NULL;
if (n <= 0 || preOrder==NULL|| inOrder==NULL|| outOrder==NULL)
{
return;
}
else
{
CreatepostBiTree(preOrder, inOrder, 0, n - 1, 0, n - 1, root);
PreOrder(root, outOrder);
}
}
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t)
{
/* 先序序列中从i到j,中序序列从k到h,建立一棵二叉树放在t中*/
int m;
t = (BiTNode*)malloc(sizeof(BiTNode));
if (t == NULL) return ;
t->data = preord[i]; /*二叉树的根*/
m = k;
while (inord[m] != preord[i]) m++; /*在中序序列中定位树的根*/
/*递归调用建立左子树*/
if (m == k) t->lchild = NULL; /*左子树空*/
else CreatepostBiTree(preord, inord, i + 1, i + m - k, k, m - 1, (t->lchild));
/*递归调用建立右子树*/
if (m == h) t->rchild = NULL; /*右子树空*/
else CreatepostBiTree(preord, inord, i + m - k + 1, j, m + 1, h, (t->rchild));
}
void PreOrder(PBiTNode bt, int* out1)
{
if (bt != NULL) { /* 如果bt为空,结束*/
out1[s++] = bt->data; /*访问根结点*/
printf("%d ", bt->data);
PreOrder(bt->rchild, out1); /*先序遍历左子树(递归调用)*/
PreOrder(bt->lchild, out1); /*先序遍历右子树(递归调用)*/
}
}
int main()
{
int N;
scanf_s("%d", &N);
int* pre = (int*)malloc(N * sizeof(int));
if (pre == NULL) return 0;
int* in = (int*)malloc(N * sizeof(int));
if (in == NULL) return 0;
int* out = (int*)malloc(N * sizeof(int));
if (out == NULL) return 0;
for (int i = 0; i < N; i++)
{
scanf_s("%d", &pre[i]);
}
for (int j = 0; j < N; j++)
{
scanf_s("%d", &in[j]);
}
solve(N, pre, in, out);
printf("\n");
return 0;
}
实现要点

1.函数嵌套使用时,参数值的传递。如:

1
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t)

若把t之前的&去掉,则无法完成双向传递,CreatepostBiTree函数执行完后root的值并未修改,运行出错。

2.malloc动态分配内存之后,注意判断是否分配成功

3.solve函数调用CreatepostBiTree函数时,注意根据序列preord和inord的实际情况传入i,j,k,h的实参

1
CreatepostBiTree(preOrder, inOrder, 0, n - 1, 0, n - 1, root);
测试
样例测试

输入样例:
n=5,preOrder={1,2,3,4,5},inOrder={3,2,4,1,5}
输出样例:
outOrder={1,5,2,4,3}

提交测试

进一步思考

怎么办呢。。怎么办呢。。算了,明天又想,上床睡觉。

我闭上眼,横竖睡不着,翻来覆去地想,脑中浮现着代码,最后从一行行代码间看出了满屏写满了两个大字——哈希!

我惊坐而起,爬下床去,慌忙翻开电脑,把中序遍历的序号进行了Hash👨‍💻

1
2
3
int inordindex[100000000];
for (int i = 0; i < n; i++)
inordindex[inOrder[i]] = i;
最终实现
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
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node* lchild;
struct Node* rchild;
}BiTNode, * PBiTNode;
int s = 0;
int inordindex[100000000];
void PreOrder(PBiTNode bt, int* out1);
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t);
void solve(int n, int* preOrder, int* inOrder, int* outOrder)
{
PBiTNode root=NULL;
if (n <= 0 || preOrder==NULL|| inOrder==NULL|| outOrder==NULL)
{
return;
}
else
{
for (int i = 0; i < n; i++)
inordindex[inOrder[i]] = i;
CreatepostBiTree(preOrder, inOrder, 0, n - 1, 0, n - 1, root);
PreOrder(root, outOrder);
}
}
void CreatepostBiTree(int preord[], int inord[], int i, int j, int k, int h, PBiTNode &t)
{
/* 先序序列中从i到j,中序序列从k到h,建立一棵二叉树放在t中*/
int m;
t = (BiTNode*)malloc(sizeof(BiTNode));
if (t == NULL) return ;
t->data = preord[i]; /*二叉树的根*/
m = inordindex[preord[i]]; /*在中序序列中定位树的根*/
/*递归调用建立左子树*/
if (m == k) t->lchild = NULL; /*左子树空*/
else CreatepostBiTree(preord, inord, i + 1, i + m - k, k, m - 1, (t->lchild));
/*递归调用建立右子树*/
if (m == h) t->rchild = NULL; /*右子树空*/
else CreatepostBiTree(preord, inord, i + m - k + 1, j, m + 1, h, (t->rchild));
}
void PreOrder(PBiTNode bt, int* out1)
{
if (bt != NULL) { /* 如果bt为空,结束*/
out1[s++] = bt->data; /*访问根结点*/
printf("%d ", bt->data);
PreOrder(bt->rchild, out1); /*先序遍历左子树(递归调用)*/
PreOrder(bt->lchild, out1); /*先序遍历右子树(递归调用)*/
}
}
int main()
{
int N;
scanf_s("%d", &N);
int* pre = (int*)malloc(N * sizeof(int));
if (pre == NULL) return 0;
int* in = (int*)malloc(N * sizeof(int));
if (in == NULL) return 0;
int* out = (int*)malloc(N * sizeof(int));
if (out == NULL) return 0;
for (int i = 0; i < N; i++)
{
scanf_s("%d", &pre[i]);
}
for (int j = 0; j < N; j++)
{
scanf_s("%d", &in[j]);
}
solve(N, pre, in, out);
printf("\n");
return 0;
}

舒服了😃

-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道