二叉树遍历

一、代码

package digui;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class shunxu {
    //递归遍历的方式与非递归遍历的方式:
    //一、递归的方式：
	//1、先序遍历：
	private static void preOrder1(Node root){
		if(root == null) return;
		System.out.print(root.value);
		preOrder1(root.left);
		preOrder1(root.right);
	}
	//2、中序遍历：
	private static void midOrder1(Node root){
		if(root == null) return;
		midOrder1(root.left);
		System.out.print(root.value);
		midOrder1(root.right);
	}
	//3、后序遍历：
	private static void postOrder1(Node root){
		if(root == null) return;
		postOrder1(root.left);
		postOrder1(root.right);
		System.out.print(root.value);
	}
    
    //二、非递归的方式：
	//1、先序遍历：
	private static void preOrder2(Node root){
		if(root == null) return;
		Stack<Node> stack = new Stack<>();//用栈来存储（先进后出）
		stack.push(root);
		while(!stack.isEmpty()){
			Node node = stack.pop();
			System.out.print(node.value);
			if(node.right != null) stack.push(node.right);
			if(node.left != null) stack.push(node.left);
		}
	}
	//2、中序遍历
	private static void midOrder2(Node root){
		if(root == null) return;
		Stack<Node> stack = new Stack<>();
		Node cur = root;//中序遍历需要时刻更新根节点
		while(!stack.isEmpty() || cur != null){
			while(cur != null){
				stack.push(cur);
				cur = cur.left;
			}
			Node node = stack.pop();
			System.out.print(node.value);
			if(node.right != null) cur= node.right;//中序遍历，左根右；更新最新的根节点指针，方便输出
		}
	}
	//3、后序遍历：
	/*和先序是逆的。可以在先序的基础上，把打印的节点单独拎出来放到另外一个栈中，之后弹出。
	直接改造先序遍历代码即可。*/
	private static void postOrder2(Node root){
		if(root == null) return;
		//两个栈
		Stack<Node> stack = new Stack<>();
		Stack<Node> stack2 = new Stack<>();
		stack.push(root);
		while(!stack.isEmpty()){
			Node node = stack.pop();
			stack2.push(node);//根节点拎出来单独放到另一个栈中
			if(node.left != null) stack.push(node.left);
			if(node.right != null) stack.push(node.right);
		}
		while(!stack2.isEmpty()){
			System.out.print(stack2.pop().value);//放有根节点的栈，倒序弹出节点
		}
	}
	
    //三、层序遍历
	/*层层打印，使用队列。*/
	private static void bfs(Node root){
		if(root == null) return;
		Queue<Node> queue = new LinkedList<>();//用队列来存储（先进先出）
		queue.add(root);
		while(!queue.isEmpty()){
			Node node = queue.poll();
			System.out.print(node.value);
			if(node.left != null) queue.add(node.left);
			if(node.right != null) queue.add(node.right);
		}
	}
	//按照一层一层打印，加层数
	private static List<List<String>> bfs2(Node root){
		List<List<String>> res = new ArrayList<>();//存储节点（List里面套List）
		Queue<Node> queue = new LinkedList<>();//用队列来存储（先进先出）
		queue.add(root);
		List<String> list;
		while(!queue.isEmpty()){
			int size = queue.size();//队列中的元素个数
			list = new ArrayList<>();//动态数组存结点元素
			while(size-- > 0){
				Node node = queue.poll();
				list.add(node.value);
				if(node.left != null) queue.add(node.left);
				if(node.right != null) queue.add(node.right);
			}
			res.add(list);//每次结束完将list加进去
		}
		System.out.print(res);
		return res;
	}
    
	public static void main(String[] args) {
		Node nodeA = new Node("A");
		Node nodeB = new Node("B");
		Node nodeC = new Node("C");
		Node nodeD = new Node("D");
		Node nodeE = new Node("E");
		Node nodeF = new Node("F");
		Node nodeG = new Node("G");
		
		//构建二叉树
		nodeA.left = nodeB;
		nodeA.right = nodeC;
		nodeB.left = nodeD;
		nodeB.right = nodeE;
		nodeC.right = nodeF;
		nodeE.left = nodeG;
		
		preOrder1(nodeA);
		System.out.println();
		midOrder1(nodeA);
		System.out.println();
		postOrder1(nodeA);
		System.out.println();
		preOrder2(nodeA);
		System.out.println();
		midOrder2(nodeA);
		System.out.println();
		postOrder2(nodeA);
		System.out.println();
		
		System.out.println("层序遍历：");
		bfs(nodeA);
		System.out.println();
		
        bfs2(nodeA);
	}
	
	public static class Node{ //节点
		public String value;
		public Node left;
		public Node right;
		
		public Node(String value){
			this.value = value;
		}
	}

}

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

代码视频讲解

[Queue的方法区别]

(https://blog.csdn.net/yemaozi1501/article/details/119761634)

二叉树的层次遍历和图的广度优先搜索的相同点和不同点：

相同点：两者都是从一个结点b出发一次访问其相邻结点，对于树来说，就是它的左右孩子结点，而图则是连通的结点。
不同点：对图来说，一个顶点的相邻结点有多个，而二叉树只有两个。另外，广度遍历图的时候，需要加上一个Visited[MAVX]数组，来记录已访问的结点，避免重复访问同个结点。比如:(a1,a2) (a1,a3)(a2,a3)访问a1后，广度遍历就会访问a2和a3，访问a2后，又会访问a3，这样就重复了。另外图还有不连通的情况，二叉树则没有。

List实现
作为一个Collection的子类型，Collection接口的所有方法在List接口里也适用。

因为List是一个接口，为了使用它，你必须实例化一个具体的实现，你可以在下列List的实现中选择：
java.util.ArrayList
java.util.LinkedList
java.util.Vector
java.util.Stack
在java.util.concurrent 包中，同样也有List 的实现，但是在本教程中，我将不考虑并发程序。

下面是创建List实例的一些例子
List listA = new ArrayList();
List listB = new LinkedList();
List listC = new Vector();
List listD = new Stack();

List 和 ArrayList的区别（转载）