主要思想
对于二叉树，有深度优先遍历和广度优先遍历，深度优先遍历有先序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历。
四种主要的遍历思想为：
先序遍历：根结点 —> 左子树 —> 右子树
中序遍历：左子树—> 根结点 —> 右子树
后序遍历：左子树 —> 右子树 —> 根结点
层次遍历：只需按层次遍历即可
Java代码实现
import java
.util
.LinkedList
;
public class TestSix {
static class Node {
private int data
;
private Node left
;
private Node right
;
public int getData(){
return data
;
}
public void setData(int data
){
this.data
= data
;
}
public Node
getLeft(){
return left
;
}
public Node
getRight(){
return right
;
}
public void setLeft(Node left
){
this.left
= left
;
}
public void setRight(Node right
){
this.right
= right
;
}
}
public static Node
createTree(int[] arr
,int index
){
Node node
= null
;
if(index
<arr
.length
) {
node
= new Node();
node
.data
= arr
[index
];
node
.left
= createTree(arr
,2*index
+1);
node
.right
= createTree(arr
,2*index
+2);
}
return node
;
}
public static void preorderTraversal(Node node
){
if(node
!=null
) {
System
.out
.print(node
.data
+" ");
preorderTraversal(node
.left
);
preorderTraversal(node
.right
);
}
}
public static void inorderTraversal(Node node
){
if(node
!=null
) {
inorderTraversal(node
.left
);
System
.out
.print(node
.data
+" ");
inorderTraversal(node
.right
);
}
}
public static void postorderTraversal(Node node
){
if(node
!=null
) {
postorderTraversal(node
.left
);
postorderTraversal(node
.right
);
System
.out
.print(node
.data
+" ");
}
}
public static void levelTraverse(Node root
) {
if (root
== null
) {
return;
}
LinkedList
<Node> queue
= new LinkedList<>();
queue
.offer(root
);
while (!queue
.isEmpty()) {
Node node
= queue
.poll();
System
.out
.print(node
.data
+" ");
if (node
.left
!= null
) {
queue
.offer(node
.left
);
}
if (node
.right
!= null
) {
queue
.offer(node
.right
);
}
}
}
public static void main(String
[] args
) {
int[] arr
= new int[] {1,2,3,4,5,6,7,8,9};
Node root
= createTree(arr
,0);
System
.out
.println("先序遍历：");
preorderTraversal(root
);
System
.out
.println("\n中序遍历：");
inorderTraversal(root
);
System
.out
.println("\n后序遍历：");
postorderTraversal(root
);
System
.out
.println("\n层次遍历：");
levelTraverse(root
);
}
}
输出结果：
