树的遍历 TJUACM 3988 Password

树的遍历是数据结构最基本的问题之一。

前序遍历：先遍历根节点 -> 左孩子 -> 右孩子 (根左右)

中序遍历：左孩子 -> 遍历根节点 -> 右孩子 (左根右)

后序遍历：左孩子 -> 右孩子 -> 最后遍历根节点 (左右根)

递归的每一步都是一个子问题，即树是由根与其左子树，右子树构成的，叶子节点没有左右子树。

天津大学ACM 3988 Password要求解的问题是：

给定某棵树的前序遍历和中序遍历，求该树的后序遍历。

解法：可以根据前序遍历先遍历根确定根在中序遍历序列中的位置，从而确定根结点的左右子树。

根据中序遍历序列中左右子树的长度，可以确定左右子树在前序遍历序列中的位置。

而左子树和右子树又分别是一棵树，现已获取这两颗树的前序和中序遍历序列，就可以递归地完成这个问题。

参考代码如下：

 1 #include <stdio.h>
 2 #define size 27
 3 int N, T;
 4 char pre[size];
 5 char ino[size];
 6 
 7 struct node{
 8     node* left;
 9     node* right;
10     char data;
11     node(int info) :data(info), left(NULL), right(NULL){};
12 };
13 
14 void partition(char s1[], char s2[], int len, node *rootNode){
15     char root = rootNode->data;
16     int left, right;
17     char left1[size], left2[size];
18     if (len > 0){
19         for (left = 0; left<len; left++){
20             if (s2[left] == root)    break;
21             left2[left] = s2[left];
22         }
23         if (left>0){
24             for (int i = 1; i <= left; i++)
25                 left1[i - 1] = s1[i];
26             node *Left = new node(left1[0]);
27             rootNode->left = Left;
28             partition(left1, left2, left, Left);
29         }
30         right = len - left - 1;
31         char right1[size], right2[size];
32         if (right > 0){
33             for (int i = left + 1; i < len; i++){
34                 right1[i - left - 1] = s1[i];
35                 right2[i - left - 1] = s2[i];
36             }
37             node *Right = new node(right1[0]);
38             rootNode->right = Right;
39             partition(right1, right2, right, Right);
40         }
41     }
42 }
43 
44 void postrav(node *rootNode){
45     if (rootNode->left != NULL)
46         postrav(rootNode->left);
47     if (rootNode->right != NULL)
48         postrav(rootNode->right);
49     printf("%c", rootNode->data);
50 }
51 
52 int main(void){
53     freopen("input.txt", "r", stdin);
54     while (scanf("%s\n%s\n", &pre, &ino) != EOF){
55         for (N = 0; N < size; N++)
56         if (pre[N] == '\0') break;
57         node *Root = new node(pre[0]);
58         partition(pre, ino, N, Root);
59         postrav(Root);
60         printf("\n");
61     }
62     return 0;
63 }

这道题也可以不建树直接通过递归输出结果。

 1 #include <stdio.h>
 2 char preOrder[27], inOrder[27], postOrder[27];
 3 void getPostOrder(int preIndex, int inIndex, int length){
 4     if (length <= 0)return;
 5     if (length == 1){
 6         printf("%c", preOrder[preIndex]);
 7         return;
 8     }
 9     int i = 0;
10     while (preOrder[preIndex] != inOrder[inIndex + i])i++;
11     getPostOrder(preIndex + 1, inIndex, i);
12     getPostOrder(preIndex + i + 1, inIndex + i + 1, length - i - 1);
13     printf("%c", preOrder[preIndex]);
14 }
15 int getlen(char *Order){
16     int i = 0;
17     while (Order[i] != '\0')i++;
18     return i;
19 }
20 int main(){
21     while (scanf("%s%s", &preOrder, &inOrder) != EOF){
22         getPostOrder(0, 0, getlen(preOrder));
23         printf("\n");
24     }
25     return 0;
26 }

通过以上练习可以较为深入理解二叉树的遍历。但在实际使用中，不同类型的树可以实现多种多样的功能，还可以互相转换。

结点的信息可能发生变化，但是遍历的思想是不会变的。

例如分支无限制的有根树，有些情况要转成二叉树，结点信息就变成了兄弟结点，第一个孩子结点。

这时候在遍历其中的K结点及其子树的时候，先遍历K结点，然后从K的第一个孩子开始前序遍历。因为K结点的兄弟结点是K的父亲的孩子结点，不应该被遍历，

但是从K的第一个孩子开始，它的兄弟也应该被遍历到，直到叶子结点。

这个的实例可以看Filesystem Implementation真题，在 ‘真题解析’ 分类下。

将结点关键信息进行Hash处理之后，把普通树转成二叉树，为的是减少空内存，提高查找效率。

实际上可以理解成把每个结点的孩子用链表的方式存储。

文件感染是非常推荐的一道扩展题目，树的数据增删改查都有练习。

树的遍历 TJUACM 3988 Password

推荐阅读