二叉树
1
2
3
4
5
| class Node<V>{
V value;
Node left;
Node right;
}
|
问题一
用递归和非递归两种方式实现二叉树的先序、中序、后序遍历
如何直观的打印一颗二叉树 ？
如何完成二叉树的宽度优先遍历 ？
左右节点(孩子)都为空的节点就叫做叶子节点
递归序
1 2 4 4 4（三次返回）2 5 5 5 2 （三次返回2）1 3 6 6 6 3 7 7 7 3 （三次返回7） 3 （三次返回3）1
在递归序的基础上，有三种遍历方式
- 先序：对于所有子树来说，都是先打印子树的头节点，在打印子树的左边节点，在打印子树的右边节点
1 2 4 5 3 6 7
第一次来到某个节点，就直接打印该节点，其他时候不打印
- 中序：对于每一颗子树，都是先打印左边节点，在打印头节点，在打印右边节点
4 2 5 1 6 3 7
第一次来到某个节点什么都不做，第二次来到某个节点打印该节点，第三次来到某个节点，什么都不做
- 后序：对于每一颗子树，都是先打印左边节点，在打印右边节点，在打印头节点
4 5 2 6 7 3 1
第一次来到某个节点什么都不做，第二次来到某个节点什么都不做，第三次来到某个节点，打印该节点
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
| public static void preOrderRecur(Node head){
if(head == null){
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
public static void inOrderRecur(Node head){
if(head == null){
return;
}
inOrderRecur(head.left);
System.out.print(head.left + " ");
inOrderRecur(head.right);
}
public static void postOrderRecur(Node head){
if(head == null){
return;
}
preOrderRecur(head.left);
preOrderRecur(head.right);
System.out.print(head.value + " ");
}
|
非递归实现先序遍历
- 先把头节点入栈
- 从栈中弹出一个节点记为cur
- 打印或者处理cur
- 把cur的孩子先右再左入栈(如果有的话)
- 重复以上步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public static void preOrderUnRecur(Node head){
System.out.print("pre-order: ");
if(head != null){
Stack<Node> stack = new Stack<>();
stack.add(head);
while (!stack.isEmpty()){
head = stack.pop();
System.out.print(head.value + " ");
if(head.right != null){
stack.push(head.right);
}
if(head.left != null){
stack.push(head.left);
}
}
}
System.out.println();
}
|
中序遍历
每棵子树整棵树的左边界进栈，依次弹出的过程中，打印，对于弹出节点的右树重复左边界入栈的操作
- 从头节点开始，每个节点的左边界（左边的全部节点，包括头节点）全部入栈
- 弹出一个节点cur，打印该节点
- 对于cur，把cur的右节点作为新的头节点，重复节点的左边界进栈
- 弹出一个节点cur，打印该节点(直到栈空)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static void inOrderUnRecur(Node head){
System.out.println("in-order: ");
if(head != null){
Stack<Node> stack = new Stack<>();
while (!stack.isEmpty() head != null){
if(head != null){
stack.push(head);
head = head.left;
}else {
head = stack.pop();
System.out.println(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
|
后序遍历（准备两个栈 s1 s2）
- 先把头节点入栈s1
- 从栈s1中弹出一个节点cur
- 把cur的子节点按照先左再右的顺序入栈s1
- 把cur放入栈s2
- 从栈s1中弹出一个节点cur（这一步开始重复知道s1为空）
- 按照出栈顺序打印s2栈中元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static void postOrderUnRecur(Node head){
System.out.println("pos-order: ");
if(head != null){
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
s1.push(head);
while (!s1.isEmpty()){
head = s1.pop();
if(head.left != null){
s1.push(head.left);
}
if(head.right != null){
s1.push(head.right);
}
}
while (!s2.isEmpty()){
System.out.println(s2.pop() + " ");
}
System.out.println();
}
}
|
对于二叉树来说
先序遍历就是二叉树的深度优先遍历
二叉树的宽度优先遍历
- 设置一个队列
- 头节点入队列
- 出队列设置为cur，并打印cur
- 对于cur，先放cur的左节点，再放cur的右节点
- 出队列设置为cur，并打印cur，对于cur， 先放左再放右(重复知道队列为空)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static void w(Node head){
if(head == null){
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()){
Node cur = queue.poll();
System.out.print(cur.value);
if(cur.left != null){
queue.add(cur.left);
}
if(cur.right != null){
queue.add(cur.right);
}
}
}
|
求一颗二叉树的最大宽度
- 定义一个HashMap用于记录每个节点在第几层
- 定义 curLevel 记录当前层数 curLevelNodes 记录当前层节点数 max 记录节点最多的层数
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
| public static void w(Node head){
if(head == null){
return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
HashMap<Node, Interger> levelMap = new HashMap<>();
levelMap.put(head, 1);
int curLevel = 1;
int curLevelNodes = 0;
int max = Interger.M
while(!queue.isEmpty()){
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if(curNodeLevel == curLevel){
curLevelNodes++;
}else{
max = Math.max(max, curLevelNodes);
curLevel++;
curLevelNodes = 1;
}
if(cur.left != null){
levelMap.put(cur.left, curNodeLevel+1);
queue.add(cur.left);
}
if(cur.right != null){
levelMap.put(cur.right, curNodeLevel+1);
queue.add(cur.right);
}
}
}
|
