二叉树构建与遍历——前序和中序或中序和后序确定二叉树

二叉树测试用例:

二叉树

preOrder: ABDGCEFH
inOrder: DGBAECHF
postOrder: GDBEHFCA

  1. 已知二叉树前序遍历序列和中序遍历序列可以确定一颗二叉树。
  2. 已知二叉树中序遍历序列和后序遍历序列可以确定一颗二叉树。
  3. 已知二叉树前序遍历序列和后序遍历序列不能确定一颗二叉树。

已知二叉树前序和中序遍历序列,构造二叉树,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
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>
#include<cstring>
using namespace std;

//二叉树结点定义
struct node {
char value;
node *lchild;
node *rchild;
node(char ch) {
value = ch;
lchild = NULL;
rchild = NULL;
}
};

//递归 二叉树前序遍历
void preOrder(node *root)
{
if (root)
{
cout << root->value;
preOrder(root->lchild);
preOrder(root->rchild);
}
}

//递归 二叉树中序遍历
void inOrder(node *root)
{
if (root)
{
inOrder(root->lchild);
cout << root->value;
inOrder(root->rchild);
}
}

//递归 二叉树后序遍历
void postOrder(node *root)
{
if (root)
{
postOrder(root->lchild);
postOrder(root->rchild);
cout << root->value;
}
}

node *buildBitree(string pre, string in)
{
int len = pre.length();
if (len <= 0)
{
return NULL;
}
node *root = new node(pre[0]);
int n = in.find(pre[0]);
root->lchild = buildBitree(pre.substr(1, n), in.substr(0, n));
root->rchild = buildBitree(pre.substr(n + 1, len - n - 1), in.substr(n + 1, len - n - 1));
return root;
}

int main()
{
char pre[100], in[100];
while (cin >> pre >> in)
{
node *root = buildBitree(pre, in);
postOrder(root);
cout << endl;
//inOrder(root);
//cout << endl;
//preOrder(root);
//cout << endl;
}
return 0;
}

已知二叉树中序和后序遍历序列,构造二叉树,C++实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
node *buildBitree(string post, string in)
{
int len = post.length();
if (len <= 0)
{
return NULL;
}
node *root = new node(post[len - 1]);
int n = in.find(post[len - 1]);
root->lchild = buildBitree(post.substr(0, n), in.substr(0, n));
root->rchild = buildBitree(post.substr(n, len - n - 1), in.substr(n + 1, len - n - 1));
return root;
}

Notes:

  str.length()、str.size()均用来求取字符串的长度。

Author: wnxy
Link: https://wnxy.github.io/2020/03/25/Bitree-construction-and-traversal/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.