二叉树的先序遍历（preorder），中序遍历（inorder），后序遍历（postorder）

二叉树的基础定义可自行百度。

二叉树的遍历方法，根据数据节点的先后顺序，可分成3种方式，假设一个节点的，左孩子为L，根节点为D，右孩子为R，那么访问顺序有3中。DLR先序，LDR中序，LRD后序（左和右是并列的。所以不需要有DRL之类的顺序）。

此处以DRL为例。

算法描述如下：

首先访问根结点。

然后如果有左孩子，则对于左孩子也采用DRL的遍历规则。没有就忽略。

然后如果有右孩子,则对右孩子也采用DRL的遍历规则。没有就忽略。

因此可以看到，是可以通过递归算法实现遍历的。

LDR和LRD的遍历也类似。

二叉树的构成可以采用数组或者链表方式。各有优缺点，此处采用链表方式，更为灵活。

下例代码中，采用链表的方式，分别构建了2个不同的树，并且对其进行遍历。程序代码和结果如下。

字母树

数字树

1. using System;  
2. using System.Collections.Generic;  
3. using System.Linq;  
4. using System.Text;  
5.  
6. namespace binarytree  
7. {  
8.     #region 节点的定义  
9.     class node  
10.     {  
11.         public string nodevalue;  
12.         public node leftchild, rightchild;  
13.  
14.         public node()  
15.         { }  
16.         public node(string value)  
17.         {  
18.             nodevalue = value;  
19.         }  
20.  
21.         public void assignchild(node left, node right)//设定左右孩子  
22.         {  
23.             this.leftchild = left;  
24.             this.rightchild = right;  
25.         }  
26.  
27.         public bool hasleftchild//是否有左孩子  
28.         {  
29.             get 
30.             {  
31.                 return (leftchild != null);  
32.             }  
33.         }  
34.  
35.         public bool hasrightchild//是否有右孩子  
36.         {  
37.             get 
38.             {  
39.                 return (rightchild != null);  
40.             }  
41.         }  
42.     }  
43.     #endregion  
44.  
45.     #region 主程序  
46.     class Program  
47.     {  
48.         static void Main(string[] args)  
49.         {  
50.             node node_a = new node("a");  
51.             node node_b = new node("b");  
52.             node node_c = new node("c");  
53.             node node_d = new node("d");  
54.             node node_e = new node("e");  
55.             node node_f = new node("f");  
56.             node node_g = new node("g");  
57.             node node_h = new node("h");  
58.             node node_i = new node("i");  
59.             //构造一棵二叉树  
60.             node_a.assignchild(node_b, node_c);  
61.             node_b.assignchild(node_d, node_e);  
62.             node_c.assignchild(node_f, node_g);  
63.             node_e.assignchild(node_h, node_i);  
64.  
65.             preorder_visit(node_a);//先序  
66.             Console.WriteLine();  
67.             inorder_visit(node_a);//中序  
68.             Console.WriteLine();  
69.             postorder_visit(node_a);//后序  
70.             Console.WriteLine();  
71.               
72.               
73.               
74.             node node_1 = new node("1");  
75.             node node_2 = new node("2");  
76.             node node_3 = new node("3");  
77.             node node_4 = new node("4");  
78.             node node_5 = new node("5");  
79.             node node_6 = new node("6");  
80.             node node_7 = new node("7");  
81.             node node_8 = new node("8");  
82.  
83.             //构造一棵二叉树  
84.             node_1.assignchild(node_2, node_3);  
85.             node_2.assignchild(node_4, node_5);  
86.             node_3.assignchild(null, node_7);  
87.             node_5.assignchild(node_6, null);  
88.             node_7.assignchild(node_8, null);  
89.  
90.             preorder_visit(node_1);//先序  
91.             Console.WriteLine();  
92.             inorder_visit(node_1);//中序  
93.             Console.WriteLine();  
94.             postorder_visit(node_1);//后序  
95.             Console.WriteLine();  
96.         }  
97.  
98.         //先序遍历 //DLR  
99.         static void preorder_visit(node Anode)  
100.         {  
101.             Console.Write(Anode.nodevalue);  
102.  
103.             if (Anode.hasleftchild)  
104.             {  
105.                 preorder_visit(Anode.leftchild);  
106.             }  
107.  
108.             if (Anode.hasrightchild)  
109.             {  
110.                 preorder_visit(Anode.rightchild);  
111.             }  
112.         }  
113.         //中序遍历-LDR  
114.         static void inorder_visit(node Anode)  
115.         {  
116.             if (Anode.hasleftchild)  
117.             {  
118.                 inorder_visit(Anode.leftchild);  
119.             }  
120.  
121.             Console.Write(Anode.nodevalue);  
122.  
123.             if (Anode.hasrightchild)  
124.             {  
125.                 inorder_visit(Anode.rightchild);  
126.             }  
127.         }  
128.         //后续遍历-LRD  
129.         static void postorder_visit(node Anode)  
130.         {  
131.             if (Anode.hasleftchild)  
132.             {  
133.                 postorder_visit(Anode.leftchild);  
134.             }  
135.  
136.             if (Anode.hasrightchild)  
137.             {  
138.                 postorder_visit(Anode.rightchild);  
139.             }  
140.  
141.             Console.Write(Anode.nodevalue);  
142.  
143.         }  
144.  
145.     }  
146.     #endregion  
147. }  

运行结果如下：

本文转自cnn23711151CTO博客，原文链接：http://blog.51cto.com/cnn237111/841507 ，如需转载请自行联系原作者