深度优先遍历二叉树。


1. 中序遍历的递归算法：


若二叉树为空，则算法结束；否则：


    中序遍历根结点的左子树；


    访问根结点；


    中序遍历根结点的右子树。


2. 前序遍历的递归算法：


若二叉树为空，则算法结束，否则：


    访问根结点；


    前序遍历根结点的左子树；


    前序遍历根结点的右子树。


3. 后序遍历的递归算法：


若二叉树为空，则算法结束，否则：


    后序遍历根结点的左子树；


    后序遍历根结点的右子树；


    访问根结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
package  com.test6;
 
/**
  * 二叉树
  * 
  * 描述： 1、二叉树的构建 2、前序递归遍历，中序递归遍历，后续递归遍历 3、测试
  * 
  * @author sdc
  *
  * @param <E>
  */
public  class  BinaryTree<E> {
 
     /**
      * 二叉树的根节点
      */
     TreeNode root;
 
     /**
      * 树的大小
      */
     private  int  size;
 
     /**
      * 指定某个元素为根节点
      * 
      * @param data
      */
     public  BinaryTree(E data) {
         this .root =  new  TreeNode(( int ) data);
     }
 
     /**
      * 返回树的大小
      * 
      * @return
      */
     public  int  getSize() {
         return  this .size;
     }
 
     /**
      * 构建二叉树
      * 
      * @param node
      * @param data
      */
     public  void  buildBinaryTree(TreeNode node,  int  data) {
         if  (root ==  null ) {  // 判断根根节点是否为空
             root =  new  TreeNode(data);
         }  else  {  // 已经有根节点，创建二叉树
             if  (data < node.data) {
                 if  (node.left ==  null ) {
                     node.left =  new  TreeNode(data);
                 }  else  {
                     buildBinaryTree(node.left, data);
                 }
             }  else  {
                 if  (node.right ==  null ) {  // 如果右子树没有，要把此节点当成右节点，创建
                     node.right =  new  TreeNode(data);
                 }  else  {
                     buildBinaryTree(node.right, data);
                 }
             }
         }
     }
 
     /**
      * 先序遍历，前序递归遍历
      * 
      * 描述：遍历到该节点后，首先输出该节点的值，并继续遍历左右子树，顺序：（根->左->右）
      * 
      * @param node
      */
     public  void  preOrder(TreeNode node) {
         if  (node ==  null ) {
             return ;
         }
 
         System.out.print(node.data +  "->" );
         preOrder(node.left);
         preOrder(node.right);
     }
 
     /**
      * 中序节点递归遍历
      * 
      * 描述：遍历到该节点后，首先将节点暂存，遍历完左子树后再输出该节点的值，并继续遍历根节点右子树，顺序：（左->根->右）
      * 
      * @param node
      */
     public  void  midOrder(TreeNode node) {
         if  (node ==  null ) {
             return ;
         }
         midOrder(node.left);
         System.out.print(node.data +  "->" );
         midOrder(node.right);
     }
 
     /**
      * 后序节点递归遍历
      * 
      * 描述：遍历到该节点后，首先将节点暂存，遍历完左子树后并继续遍历根节点右子树，最后输出顺序。顺序：（左->右->跟）
      * 
      * @param node
      */
     public  void  postOrder(TreeNode node) {
         if  (node ==  null ) {
             return ;
         }
         postOrder(node.left);
         postOrder(node.right);
         System.out.print(node.data +  "->" );
     }
 
     /**
      * 查找一个节点的值
      * 
      * @param data
      * @return
      */
     public  boolean  search( int  data) {
         boolean  isFlag =  false ;
         TreeNode node = root;
 
         while  ( true ) {
             if  (data == node.data) {
                 isFlag =  true ;
                 break ;
             }  else  if  (data > node.data) {
                 node = node.right;
                 if  (node ==  null ) {
                     break ;
                 }
             }  else  {
                 node = node.left;
                 if  (node ==  null ) {
                     break ;
                 }
             }
         }
         return  isFlag;
     }
 
     public  static  void  main(String[] args) {
         int [] array = {  12 ,  9 ,  20 ,  5 ,  11 ,  39 ,  3  };
         BinaryTree<Integer> bt =  new  BinaryTree<Integer>(array[ 0 ]);
 
         for  ( int  i =  0 ; i < array.length; i++) {
             bt.buildBinaryTree(bt.root, array[i]);
         }
 
         // 三种遍历
         bt.preOrder(bt.root);
         System.out.println();
         bt.midOrder(bt.root);
         System.out.println();
         bt.postOrder(bt.root);
 
     }
 
     /**
      * 二叉树结构
      * 
      * @author sdc
      *
      */
     class  TreeNode {
         int  data;
 
         TreeNode left;
 
         TreeNode right;
 
         public  TreeNode( int  data) {
             this .data = data;
             this .left =  null ;
             this .right =  null ;
         }
 
     }
}