二叉樹的遍歷分為深度優先遍歷(DFS)和廣度優先遍歷(BFS)

DFS遍歷主要有：

前序遍歷

中序遍歷

后序遍歷

一、遞歸實現DFS

Node.java:

public class Node {

private Object data;

Node richild;

Node lechild;

public Object getData() {

return data;

}

public void setData(Object data) {

this.data = data;

}

public Node getRichild() {

return richild;

}

public void setRichild(Node richild) {

this.richild = richild;

}

public Node getLechild() {

return lechild;

}

public void setLechild(Node lechild) {

this.lechild = lechild;

}

public Node(Object data, Node lechild, Node richild) {

super();

this.data = data;

this.richild = richild;

this.lechild = lechild;

}

public Node() {

super();

}

}

遞歸遍歷：

public class BTree {

private static Node root;

//構造樹

public static void init() {

Node node1 = new Node("A", null, null);

Node node2 = new Node("B", node1, null);

Node node3 = new Node("C", null, null);

Node node4 = new Node("D", node2, node3);

Node node5 = new Node("E", null, null);

Node node6 = new Node("F", null, node5);

Node node7 = new Node("G", node4, node6);

root = node7;

}

//訪問節點

public static void visited(Node n) {

System.out.print(n.getData() + " ");

}

//前序遍歷

public static void preOrder(Node n) {

if (n != null) {

visited(n);

preOrder(n.getLechild());

preOrder(n.getRichild());

}

}

//中序遍歷

public static void inOrder(Node n) {

if (n != null) {

inOrder(n.getLechild());

visited(n);

inOrder(n.getRichild());

}

}

//后序遍歷

public static void postOrder(Node n) {

if (n != null) {

postOrder(n.getLechild());

postOrder(n.getRichild());

visited(n);

}

}

public static void main(String[] args) {

init();

System.out.print("遞歸前序：");

preOrder(root);

System.out.println();

System.out.print("遞歸中序：");

inOrder(root);

System.out.println();

System.out.print("遞歸后序：");

postOrder(root);

System.out.println();

}

}

二、非遞歸實現DFS(依靠棧)

//前序遍歷

public static void preOrder(Node n) {

System.out.print("非遞歸前序：");

Stack stack = new Stack<>();

int index = 0;

while (n != null || index > 0) {

while (n != null) {

System.out.print(n.getData() + " ");

stack.push(n);

index++;

n = n.getLechild();

}

n = stack.pop();

index--;

n = n.getRichild();

}

}

//中序遍歷

public static void inOrder(Node n) {

System.out.print("非遞歸中序：");

Stack stack = new Stack<>();

int index = 0;

while (n != null || index > 0) {

while (n != null) {

stack.push(n);

index++;

n = n.getLechild();

}

n = stack.pop();

System.out.print(n.getData() + " ");

index--;

n = n.getRichild();

}

}

//后序遍歷

public static void postOrder(Node n) {

System.out.print("非遞歸后序：");

Stack stack = new Stack<>();

int index = 0;

Node lastVisited = null;

while (n != null || index > 0) {

while (n != null) {

stack.push(n);

index++;

n = n.getLechild();

}

n = stack.peek();

if (n.getRichild() == null || n.getRichild() == lastVisited) {

System.out.print(n.getData() + " ");

lastVisited = n;

index--;

stack.pop();

n = null;

} else {

n = n.getRichild();

}

}

}

三、實現層序遍歷(依靠隊列)

public static void LevenOrder(Node root) {

if (root == null) {

return;

}

Queue queue = new LinkedList<>();

queue.add(root);

Node temp = null;

while (!queue.isEmpty()) {

temp = queue.poll();

visited(temp);

if (temp.getLeChild() != null) {

queue.add(temp.getLeChild());

}

if (temp.getRChild() != null) {

queue.add(temp.getChild());

}

}

}