二叉树的遍历是指通过一定顺序访问二叉树的所有结点。遍历方法一般有四种：先序遍历、中序遍历、后序遍历及层次遍历。
一、先序遍历
对先序遍历来说，总是先访问根结点 root，然后才去访问左子树和右子树，因此先序遍历的遍历顺序是根结点 -> 左子树 -> 右子树。代码如下：
1 // 先序遍历 2 void preorder(node* root) { 3 if(root == NULL) { 4 return; // 空树，递归边界 5 } 6 printf("%d ", root->data); // 访问该结点 7 preorder(root->lchild); // 访问左子树 8 preorder(root->rchild); // 访问右子树 9 }
对一棵二叉树的先序遍历序列，序列的第一个一定是根结点。
二、中序遍历
对中序遍历来说，总是先访问左子树，再访问根结点，最后访问右子树，因此中序遍历的遍历顺序是左子树 -> 根结点 -> 右子树。代码如下：
1 // 中序遍历 2 void inorder(node* root) { 3 if(root == NULL) { 4 return; // 空树，递归边界 5 } 6 inorder(root->lchild); // 访问左子树 7 printf("%d ", root->data); // 访问该结点 8 inorder(root->rchild); // 访问右子树 9 }
由于中序遍历总是把根结点放在左子树和右子树之间，因此只要知道根结点，就可以通过根结点在中序遍历序列中的位置区分出左子树和右子树。
三、后序遍历
对后序遍历来说，总是先访问左子树，再访问右子树，最后才访问根结点，因此后序遍历的遍历顺序是左子树 -> 右子树 -> 根结点。代码如下：
1 // 后序遍历 2 void postorder(node* root) { 3 if(root == NULL) { 4 return; // 空树，递归边界 5 } 6 postorder(root->lchild); // 访问左子树 7 postorder(root->rchild); // 访问右子树 8 printf("%d ", root->data); // 访问该结点 9 }
四、一个重要问题
给定一棵二叉树的先序遍历序列和中序遍历序列，重建这棵二叉树。
假设在递归过程中，当前先序序列的区间为 [preL, preR] ，中序序列的区间为 [inL, inR] ，且 ink = pre1 ，那么左子树的结点个数为 numLeft = k - inL。这样左子树的先序序列区间就是 [preL+1, pre+numLeft]，左子树的中序序列区间是 [inL, k-1]；右子树的先序序列区间是 [preL+numLeft+1, preR]，右子树的中序序列区间是 [k+1, inR]。
当先序序列的长度小于等于 0 时，当前二叉树就不存在了，这个条件可以作为递归边界。代码如下：
1 int pre[maxn]={1, 2, 4, 5, 3, 6}, in[maxn]={4, 2, 5, 1, 3, 6}; // 储存先序、中序序列 2 // 当前先序序列 [preL, preR]，中序序列 [inL, inR]，返回根结点地址 3 node* create1(int preL, int preR, int inL, int inR) { 4 if(preL > preR) { 5 return NULL; // 先序序列长度小于等于0，递归边界 6 } 7 node* root = (node*)malloc(sizeof(node)); 8 root->data = pre[preL]; // 新结点的数据域为根结点的值 9 int k; 10 for(k=inL; k<=inR; ++k) { 11 if(in[k] == pre[preL]) { // 在中序序列中找到根结点 12 break; 13 } 14 } 15 int numLeft = k - inL; // 左子树结点个数 16 17 // 左子树的先序序列区间是 [preL+1, pre+numLeft]，中序序列区间是 [inL, k-1] 18 root->lchild = create1(preL+1, preL+numLeft, inL, k-1); 19 // 右子树的先序序列区间是 [preL+numLeft+1, preR]，中序序列区间是 [k+1, inR] 20 root->rchild = create1(preL+numLeft+1, preR, k+1, inR); 21 22 return root; 23 }
完整 C 代码如下：
1 /* 2 二叉树 3 */ 4 5 #include <stdio.h> 6 #include <string.h> 7 #include <math.h> 8 #include <stdlib.h> 9 #include <time.h> 10 #include <stdbool.h> 11 12 #define typename int 13 #define maxn 20 14 // 二叉树结构定义 15 typedef struct _node { 16 typename data; // 数据域 17 struct _node* lchild; // 指向左子树的根结点 18 struct _node* rchild; // 指向右子树的根结点 19 } node; 20 21 // 生成一个新节点，v为数据 22 node* newNode(typename v) { 23 node* Node = (node*)malloc(sizeof(node)); 24 Node->data = v; 25 // 初始状态下没有左右子树 26 Node->lchild = Node->rchild = NULL; 27 return Node; 28 } 29 30 // 在根结点为root的二叉树查找所有数据域为x的结点并修改为newdata 31 void search(node* root, typename x, typename newdata) { 32 if(root == NULL) { 33 return; // 空树 34 } 35 if(root->data == x) { // 查到 x 36 root->data = newdata; // 修改 37 } 38 search(root->lchild, x, newdata); // 遍历左子树 39 search(root->rchild, x, newdata); // 遍历右子树 40 } 41 42 // 在以*root为根结点的二叉树插入一个新节点 43 void insert(node** root, typename x) { 44 if((*root) == NULL) { // 找到插入位置 45 (*root) = newNode(x); 46 return; 47 } 48 if(x < (*root)->data) { // 往左子树插入 49 insert(&((*root)->lchild), x); 50 } else { // 往右子树插入 51 insert(&((*root)->rchild), x); 52 } 53 } 54 55 // 二叉树的建立 56 node* create(typename data[], int n) { 57 node* root = NULL; // 新建空根结点 root 58 int i; 59 for(i=0; i<n; ++i) { // 将 data 中的数据插入二叉树 60 insert(&root, data[i]); 61 } 62 return root; // 返回根结点 63 } 64 65 // 先序遍历 66 void preorder(node* root) { 67 if(root == NULL) { 68 return; // 空树，递归边界 69 } 70 printf("%d ", root->data); // 访问该结点 71 preorder(root->lchild); // 访问左子树 72 preorder(root->rchild); // 访问右子树 73 } 74 75 // 中序遍历 76 void inorder(node* root) { 77 if(root == NULL) { 78 return; // 空树，递归边界 79 } 80 inorder(root->lchild); // 访问左子树 81 printf("%d ", root->data); // 访问该结点 82 inorder(root->rchild); // 访问右子树 83 } 84 85 // 后序遍历 86 void postorder(node* root) { 87 if(root == NULL) { 88 return; // 空树，递归边界 89 } 90 postorder(root->lchild); // 访问左子树 91 postorder(root->rchild); // 访问右子树 92 printf("%d ", root->data); // 访问该结点 93 } 94 95 int pre[maxn]={1, 2, 4, 5, 3, 6}, in[maxn]={4, 2, 5, 1, 3, 6}; // 储存先序、中序序列 96 // 当前先序序列 [preL, preR]，中序序列 [inL, inR]，返回根结点地址 97 node* create1(int preL, int preR, int inL, int inR) { 98 if(preL > preR) { 99 return NULL; // 先序序列长度小于等于0，递归边界 100 } 101 node* root = (node*)malloc(sizeof(node)); 102 root->data = pre[preL]; // 新结点的数据域为根结点的值 103 int k; 104 for(k=inL; k<=inR; ++k) { 105 if(in[k] == pre[preL]) { // 在中序序列中找到根结点 106 break; 107 } 108 } 109 int numLeft = k - inL; // 左子树结点个数 110 111 // 左子树的先序序列区间是 [preL+1, pre+numLeft]，中序序列区间是 [inL, k-1] 112 root->lchild = create1(preL+1, preL+numLeft, inL, k-1); 113 // 右子树的先序序列区间是 [preL+numLeft+1, preR]，中序序列区间是 [k+1, inR] 114 root->rchild = create1(preL+numLeft+1, preR, k+1, inR); 115 116 return root; 117 } 118 119 /*// 输出二叉树，先序 120 void print(node* root) { 121 if(root == NULL) { 122 return; 123 } 124 printf("%d ", root->data); 125 print(root->lchild); 126 print(root->rchild); 127 }*/ 128 129 int main() { 130 /*int data[5] = {1, 2, 3, 4, 5}; 131 node* tree = create(data, 5); // 创建二叉树 132 print(tree); // 输出二叉树 */ 133 134 node* tree = create1(0, 5, 0, 5); 135 postorder(tree); 136 137 return 0; 138 }