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

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

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

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

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

 

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

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

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

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

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

参考代码如下：

1 #include 
     
       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
      
       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 
     
       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处理之后，把普通树转成二叉树，为的是减少空内存，提高查找效率。

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

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