中序遍历和先序遍历/后序遍历构建二叉树
分类： 面试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
系列 数据结构与算法 二叉树 2012-07-25 15:02 2463人阅读 评论(0) 收藏 举报
目录(?)
HYPERLINK "http://blog.csdn.net/ssjhust123/article/details/7783935" \l "#" \o "展开" [+]
1. 问题
2. 理论分析
3. 构造思路
1. 根据先序遍历序列和中序遍历序列构建二叉树
2. 需要关注几个重要的点
3. 根据后序遍历和中序遍历构建二叉树
1、问题
给定二叉树的2个遍历序列（如先序+中序，先序+后序，中序+后序等），是否能够根据这2个遍历序列唯一确定二叉树？
2、理论分析
数据结构的基础知识中重要的一点就是能否根据两种不同遍历序列的组合（有三种：先序+中序，先序+后序，中序+后序），唯一的确定一棵二叉树。然后就是根据二叉树的不同遍历序列（先序、中序、后序），重构二叉树。显然，这三种组合并不是都能唯一确定二叉树的，其中先序+后序就不能唯一确定一棵二叉树，下面是关于该问题的证明与结论。
①给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。
证明：因为先序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（假设有L个元素）
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示左子树，若左边无元素，则说明左子树为空；右边（假设有R个元素）是右子树，若为空，则右子树为空。根据前序遍历中"根-左子树-右子树"的顺序，则由从先序序列的第二元素开始的L个结点序列和中序序列根左边的L个结点序列构造左子树，由先序序列最后R个元素序列与中序序列根右边的R个元素序列构造右子树。
②由中序序列和先序序列能唯一确定一棵二叉树，但是由先序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。
反例：任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。
如： 2 2
/ \
1 1
/ \
3 3
这两棵二叉树的先序遍历序列都为2-1-3，后序遍历序列都为3-1-2。但是显然它们是不同的二叉树，所以根据先序序列和后序序列并不能唯一确定二叉树。
③已经说明由二叉树的先序序列和中序序列可以确定一棵二叉树，现在来证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
证明：
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立，即结点数目为m-1时，中序序列和后序序列可以唯一确定二叉树。现证明当n=m时结论成立。
设中序序列为S1,S2,…,Sm,后序序列是P1,P2,…,Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1,S2,…,Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2,S3,…,Sm}和{P1,P2,…,Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m，则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1,S2,…,Sm-1}和{P1,P2,…,Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。pre数组为先序遍历序列，注意在递归过程中pre起始位置是变化的。n为结点数目，offset为子树开始位置。
10. struct node* buildInorderPreorder(int pre[],
11. int n, int offset)
12. {
13. if (n == 0) return NULL;
14. int rootVal = pre[0];
15. int i = mapIndex[rootVal] - offset;
16. struct node* root = newNode(rootVal);
17. root->left = buildInorderPreorder(pre+1,
18. i, offset);
19. root->right = buildInorderPreorder(pre+i+1,
20. n-i-1, offset+i+1);
21. return root;
22. }
23. //测试代码
24. void buildInorderPreorderTest()
25. {
26. int pre[] = {7, 10, 4, 3, 1, 2, 8, 11};
27. int in[] = {4, 10, 3, 1, 7, 11, 8, 2};
28. int n = sizeof(in) / sizeof(in[0]);
29. int offset = 0;
30. mapToIndices(in, n);
31. struct node* root = buildInorderPreorder(pre, n, offset);
32. traverse(root);
33. putchar('\n');
34. }
int mapIndex[256];
void mapToIndices(int inorder[], int n)
{
int i;
for (i=0; ileft = buildInorderPreorder(pre+1,
i, offset);
root->right = buildInorderPreorder(pre+i+1,
n-i-1, offset+i+1);
return root;
}
//测试代码
void buildInorderPreorderTest()
{
int pre[] = {7, 10, 4, 3, 1, 2, 8, 11};
int in[] = {4, 10, 3, 1, 7, 11, 8, 2};
int n = sizeof(in) / sizeof(in[0]);
int offset = 0;
mapToIndices(in, n);
struct node* root = buildInorderPreorder(pre, n, offset);
traverse(root);
putchar('\n');
}
2）根据后序遍历和中序遍历构建二叉树
跟前面原理类似，代码如下：
[cpp] view plain
HYPERLINK "http://blog.csdn.net/ssjhust123/article/details/7783935" \l "#" \o "copy" copy
HYPERLINK "http://blog.csdn.net/ssjhust123/article/details/7783935" \l "#" \o "print" print
HYPERLINK "http://blog.csdn.net/ssjhust123/article/details/7783935" \l "#" \o "?" ?
1. struct node *buildInorderPostorder(int post[], int n, int offset)
2. {
3. assert(n >= 0);
4. if (n == 0) return NULL;
5. int rootVal = post[n-1];
6. int i = mapIndex[rootVal]-offset; // the divider's index
7. struct node *root = newNode(rootVal);
8. root->left = buildInorderPostorder(post, i, offset);
9. root->right = buildInorderPostorder(post+i, n-i-1, offset+i+1);
10. return root;
11. }
struct node *buildInorderPostorder(int post[], int n, int offset)
{
assert(n >= 0);
if (n == 0) return NULL;
int rootVal = post[n-1];
int i = mapIndex[rootVal]-offset; // the divider's index
struct node *root = newNode(rootVal);
root->left = buildInorderPostorder(post, i, offset);
root->right = buildInorderPostorder(post+i, n-i-1, offset+i+1);
return root;
}
浙公网安备 33021202002483