由遍历序列确定二叉树

发表于 分类于 ， Waline：
本文字数： 4.8k 阅读时长 ≈ 4 分钟
分别根据先序+中序、后序+中序、层序+中序序列确定二叉树

先序+中序

主要思路

先在先序序列中找树根，也就是第一个元素，然后在中序序列中找到这个元素，进而确定左右子树，也就是此元素左边和右边的。

例子

先序：A B D E C F G H

后序：D B E A C G F H

在先序中找到树根A，在后序中确定其左子树包含D B E，右子树包含C G F H，然后递归进行这个过程。

确定二叉树为：



graph TD
	A((A)) === B((B)) 
	A === C((C))
	B === D((D))
	B === E((E))
	C -.- t(( ))
	C === F((F))
	F === G((G))
	F === H((H))

注：C并没有左孩子结点，图中的虚线连接的结点只是用来占位的

代码

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
/// <summary>
/// 二叉树结点
/// </summary>
typedef struct BTNode{
    char data;
    BTNode* lchild;
    BTNode* rchild;
}BTNode;

/// <summary>
/// 数组查找
/// </summary>
/// <param name="arr">待查找数组</param>
/// <param name="L">数组开始下标</param>
/// <param name="R">数组结束下标</param>
/// <param name="target">目标元素</param>
/// <returns>数组下标</returns>
int Search(char arr[], int L, int R, char target)
{
    for (int i = L; i <= R; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

/// <summary>
/// 根据前序和中序遍历序列确定二叉树
/// </summary>
/// <param name="pre">前序遍历序列</param>
/// <param name="in">中序遍历序列</param>
/// <param name="L1">前序序列开始下标</param>
/// <param name="R1">前序序列结束下标</param>
/// <param name="L2">中序序列开始下标</param>
/// <param name="R2">中序序列结束下标</param>
/// <returns>二叉树根</returns>
BTNode* CreateBT1(char pre[], char in[], int L1, int R1, int L2, int R2)
{
    if (L1 > R1) {
        return nullptr;
    }
    BTNode* s = new BTNode();
    s->lchild = s->rchild = nullptr;
    s->data = pre[L1];  // 根
    int i = Search(in, L2, R2, pre[L1]); // 根在中序里的下标
    s->lchild = CreateBT1(pre, in, L1 + 1, L1 + i - L2, L2, i - 1); // 递归创建左子树
    s->rchild = CreateBT1(pre, in, L1 + i - L2 + 1, R1, i + 1, R2); // 递归创建右子树
    return s;
}

后序+中序

主要思路

先在后序序列中找树根，也就是最后一个元素，然后在中序序列中找到这个元素，进而确定左右子树，也就是此元素左边和右边的。

例子

后序：D E B G H F C A

中序：D B E A C G F H

在后序中找到树根A，在中序里确定其左子树包含D B E，右子树包含C G F H，之后递归进行这个过程。

确定二叉树为：



graph TD
	A((A)) === B((B)) 
	A === C((C))
	B === D((D))
	B === E((E))
	C -.- t(( ))
	C === F((F))
	F === G((G))
	F === H((H))

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/// <summary>
/// 根据后序和中序遍历序列确定二叉树
/// </summary>
/// <param name="last">后序遍历序列</param>
/// <param name="in">中序遍历序列</param>
/// <param name="L1">后序序列开始下标</param>
/// <param name="R1">后序序列结束下标</param>
/// <param name="L2">中序序列开始下标</param>
/// <param name="R2">中序序列结束下标</param>
/// <returns>二叉树根</returns>
BTNode* CreateBT2(char post[], char in[], int L1, int R1, int L2, int R2)
{
    if (L1 > R1) {
        return nullptr;
    }
    BTNode* s = new BTNode();
    s->lchild = s->rchild = nullptr;
    s->data = post[R1];  // 根
    int i = Search(in, L2, R2, post[R1]);  // 根在中序里的下标
    s->lchild = CreateBT2(post, in, L1, L1 + i - L2 - 1, L2, i - 1); // 递归创建左子树
    s->rchild = CreateBT2(post, in, L1 + i - L2, R1 - 1, i + 1, R2); // 递归创建右子树
    return s;
}

层序+中序

主要思路

先在层序序列中找到树根，也就是第一个，然后在中序序列中找到这个元素，然后可以确定在中序序列中的左右子树，也就是这个元素的左边和右边的。但是在层序中，这个元素的左右子树并不是连续分布的，准确来说，在层序中会穿插左子树和右子树的元素。

例子

层序：A B C D E F G H

中序：D B E A C G F H

在层序中找到树根A，在中序里确定其左子树包含D B E，右子树包含C G F H。但是在层序中，左子树的D B E里穿插了C，右子树的C G F H穿插了D和E，总之不能像之前一样设置数组的L和R就直接进入下一步递归。这里需要将左右子树对应层序中的元素分别提取出来，作为子层序序列，然后进入下一步递归。

代码

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
/// <summary>
/// 根据中序序列提取子层序序列
/// </summary>
/// <param name="subLevel">子层序序列</param>
/// <param name="level">原层序序列</param>
/// <param name="in">中序序列</param>
/// <param name="n">层序序列长</param>
/// <param name="L">中序序列开始下标</param>
/// <param name="R">中序序列结束下标</param>
void GetSubLevel(char subLevel[], char level[], char in[], int n, int L, int R)
{
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (Search(in, L, R, level[i]) != -1) {
            subLevel[k++] = level[i];
        }
    }
}

/// <summary>
/// 根据层序和中序遍历序列确定二叉树
/// </summary>
/// <param name="level">层序遍历序列</param>
/// <param name="in">中序遍历序列</param>
/// <param name="n">层序序列长度</param>
/// <param name="L">中序序列开始下标</param>
/// <param name="R">中序序列结束下标</param>
/// <returns></returns>
BTNode* CreateBT3(char level[], char in[], int n, int L, int R)
{
    if (L > R) {
        return nullptr;
    }
    BTNode* s = new BTNode();
    s->lchild = s->rchild = nullptr;
    s->data = level[0];  // 根
    int i = Search(in, L, R, level[0]);  // 根在中序里的下标
    int LN = i - L, RN = R - i;  // 左右子树元素个数
    char* LLevel = new char[LN]; // 左子树对应的子层序序列
    char* RLevel = new char[RN]; // 右子树对应的子层序序列
    GetSubLevel(LLevel, level, in, n, L, i - 1);
    GetSubLevel(RLevel, level, in, n, i + 1, R);
    s->lchild = CreateBT3(LLevel, in, LN, L, i - 1); // 递归创建左子树
    s->rchild = CreateBT3(RLevel, in, RN, i + 1, R); // 递归创建右子树
}
相关文章