树的生成
中序序列可以与先序序列、后序序列、层序序列中的任意一个来构建唯一的二叉树。
先序+中序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
node* create(int preL, int preR, int inL, int inR){
if (preL > preR) {
return NULL;
}
node* root = new node;
root->data = pre[preL];
root->left = root->right = NULL;
int k;
for (k = inL; k <= inR; k++) {
if (root->data == in[k]) {
break;//找到根节点
}
}
int numLeft = k - inL;
root->left = create(preL + 1, preL + numLeft, inL, k - 1);
root->right = create(preL + numLeft, preR, k + 1, inR);
return root;
}
|
后序+中序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
node* create(int postL, int postR, int inL, int inR){
if (postL > postR) {
return NULL;
}
node* root = new node;
root->data = pre[postR];
root->left = root->right = NULL;
int k;
for (k = inL; k <= inR; k++) {
if (root->data == in[k]) {
break;//找到根节点
}
}
int numLeft = k - inL;
root->left = create(postL, postL + numLeft - 1, inL, k - 1);
root->right = create(postL + numLeft, postR - 1, k + 1, inR);
return root;
}
|
层次+中序：
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
|
node* create(vector<int>layer, int inL, int inR){
if(layer.size() == 0){
return NULL;
}
node* root = new node;
root->data = layer[0];
int k;
for (k = inL; k <= inR; k++) {
if (root->data == in[k]) {
break;//找到根结点
}
}
vector<int> leftLayer;
vector<int> rightLayer;
for (int i = 0; i < layer.size(); i++) {//先从layer里找，因为顺序决定谁是根节点
bool isLeft = false;
for (int j = inL; j < k; j++) {
if (layer[i] == in[j]) {//在中序的左边找到
isLeft = true;//是左子树上的点
}
}
if (isLeft) leftLayer.push_back(layer[i]);
else rightLayer.push_back(layer[i]);
}
root->left = create(leftLayer, inL, k - 1);
root->left = create(rightLayer, k + 1, inR);
return root;
}
|
近期评论