华师一附中OI组

标题: NOIP2001普及组 求先序遍历 [打印本页]

---

作者: diggersun    时间: 2016-2-18 15:30
标题: NOIP2001普及组 求先序遍历
题目描述：

描述 Description         

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。

输入格式 Input Format      

      第一行为二叉树的中序序列

    第二行为二叉树的后序序列

输出格式 Output Format     

      一行，为二叉树的先序序列

样例输入 Sample Input      

      BADC BDCA

样例输出 Sample Output     

      ABCD

---

作者: diggersun    时间: 2016-2-18 15:31
题目分析：

已知中序和前序排列，或者已知中序和后序序列，都能够构造一棵二叉树，此题考查后者。

前序遍历的规律是：输出根结点，输出左子树，输出右子树；  

中序遍历的规律是：输出左子树，输出根结点，输出右子树；

后序遍历的规律是：输出左子树，输出右子树，输出根结点；

根据中序和后序序列的规律，我们可以知道构造二叉树的过程是一个递归的过程，根据给定的 中序和后序序列，建立二叉树的根结点，并将中序序列划分为左子树序列和右子树序列，然后分别把左子树序列和右子树序列递归的构造左子树和右子树。

具体的算法是分别用数组mid[lm..rm]和post[tp..rp]存储给定的中序和后序序列。易知post[rp]为根结点，创建二叉树的根结点t，设t->data = post[rp]；遍历mid，寻找根结点post[rp]的下标pos，则mid[lm..pos-1]为左子树序列，mid[pos+1..rm]为右子树序列；左子树序列的长度lenL= pos - lm，右子树序列的长度lenR= rm - pos。

很明显，若pos == lm，则lenL = 0，说明根结点无左子树；若pos == rm，则lenR = 0，说明根结点无右子树；  

根据后序序列的规律，可以知道根结点t的左子树的后序排列为post[lp..lp+lenL-1];

根结点t的右子树的后序排列为post[lp+lenL..rp-1]。

采用同样的方法递归构造根结点t的左右子树。

以样例输入为例：

中序序列：BADC

后序序列：BDCA   

1.得到根结点t->data = 'A';

2.遍历中序序列mid，得到mid[pos] = 'A'，lenL = 1；

3.得到根结点t的左子树的中序序列为mid[lm..pos-1] = "B",右子树的中序序列为mid[pos+1..rm] = "DC";根结点t的左子树的后序序列为post[lp..lp+lenL-1] = "B",右子树的后序序列为post[lp+lenL..rp-1] = "DC";

4.递归构造根结点t的左子树t->lc，设t= t->lc：

           1.得到根结点t->data = 'B';

           2.遍历中序序列mid，得到mid[pos] = 'B'，lenL = 0；

           3.得到根结点t的左右子树均为空，返回调用函数。

5. 递归构造根结点t的右子树t->rc，设t= t->rc：

           1.得到根结点t->data = 'C';

           2.遍历中序序列mid，得到mid[pos] = 'C'，lenL = 1；

           3.得到根结点t的左子树的中序序列为"D"，后序序列为"D"；右子树为空，

           4.递归构造根结点t的左子树t->lc；

6.最后得到整棵二叉树，前序遍历二叉树，得到前序序列：ABCD。



说明：

算法思想：递归和分治。

数据结构：数组，二叉树。

时间复杂度：O(N);

空间复杂度：O(N);

程序语言：分别用c++和pascal实现。



附注：

若题目改为已知中序和前序序列，输出后序序列，因为先序序列pre[lp..rp]中根结点是第一个元素，所以只需将函数中的根结点数据由t->data = post[rp] 改为t->data = pre[lp]； 然后在递归构造左右子树时注意左子树中序序列为mid[lm+1..pos-1]，右子树中序序列为mid[pos+1..rm]，左子树先序序列为pre[lp+1..lp+lenL]，右子树先序序列为pre[lp+lenL+1..rp]，

最后后序遍历二叉树就行了。  

---

作者: diggersun    时间: 2016-2-18 15:32

1. #include<iostream>
   
2. 
   
3. #include<string>
   
4. 
   
5. 
   
6. 
   
7. using namespace std;
   
8. 
   
9. 
   
10. 
    
11. typedef struct BTNode{
    
12. 
    
13.       char data;
    
14. 
    
15.       struct BTNode *lc, *rc;//左，右孩子指针
    
16. 
    
17. } *BTree;
    
18. 
    
19. 
    
20. 
    
21. void PostBtree(BTree & t, string mid, string post, int lm, int rm, int lp, int rp);
    
22. 
    
23. void Preorder(BTree p);
    
24. 
    
25. 
    
26. 
    
27. int main(int argc, char* argv[])
    
28. 
    
29. {
    
30. 
    
31.     string mid, post;
    
32. 
    
33.     BTree root;
    
34. 
    
35.    
    
36. 
    
37.     cin >> mid;
    
38. 
    
39.     cin >> post;
    
40. 
    
41.     PostBtree(root, mid, post, 0, mid.size()-1, 0, post.size()-1);
    
42. 
    
43.     Preorder(root);
    
44. 
    
45.    
    
46. 
    
47.     system("pause");
    
48. 
    
49.     return 0;
    
50. 
    
51. }
    
52. 
    
53. 
    
54. 
    
55. /*
    
56. 
    
57. 函数名称：PostBtree
    
58. 
    
59. 函数功能：给出一棵二叉树的中序与后序序列，构造这棵二叉树。
    
60. 
    
61. 输入参数: BTree & t：二叉树的结点t
    
62. 
    
63.           string mid：存储了二叉树的中序序列的字符串
    
64. 
    
65.           string post：存储了二叉树的后序序列的字符串
    
66. 
    
67.           int lm, int rm：二叉树的中序序列在数组mid中的左右边界
    
68. 
    
69.           int lp, int rp：二叉树的后序序列在数组post中的左右边界
    
70. 
    
71. */
    
72. 
    
73. void PostBtree(BTree & t, string mid, string post, int lm, int rm, int lp, int rp)
    
74. 
    
75. {
    
76. 
    
77.     t = new BTNode; //构造二叉树根结点
    
78. 
    
79.     t->data = post[rp];
    
80. 
    
81.     t->lc = t->rc = NULL;
    
82. 
    
83.    
    
84. 
    
85.     int pos = lm;
    
86. 
    
87.     while (mid[pos] != post[rp])
    
88. 
    
89.         pos++;
    
90. 
    
91.     int lenL = pos - lm;
    
92. 
    
93.     if (pos > lm)//有左孩子，递归构造左子树
    
94. 
    
95.         PostBtree(t->lc, mid, post, lm, pos-1, lp, lp+lenL-1);
    
96. 
    
97.     if (pos < rm)//有右孩子，递归构造右子树
    
98. 
    
99.         PostBtree(t->rc, mid, post, pos+1, rm, lp+lenL, rp-1);
    
100. 
     
101. }
     
102. 
     
103. //先序遍历
     
104. 
     
105. void Preorder(BTree p)
     
106. 
     
107. {
     
108. 
     
109.        if(p != NULL)
     
110. 
     
111.        {
     
112. 
     
113.               cout << p->data; //输出该结点
     
114. 
     
115.               Preorder(p->lc); //遍历左子树
     
116. 
     
117.               Preorder(p->rc); //遍历右子树
     
118. 
     
119.        }
     
120. 
     
121. }
     

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2