Fork me on GitHub

算法之美-二叉树的遍历

前序?后序?层序?递归?一问看尽二叉树应该怎么遍历。

二叉树的定义:

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
/**
* @Author: WuFan
* @Date: 2018/3/6 22:07
*/

package offer;


//二叉树节点
public class BinaryTreeNode {
private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;

public BinaryTreeNode() {}

public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
super();
this.data = data;
this.left = left;
this.right = right;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public BinaryTreeNode getLeft() {
return left;
}

public void setLeft(BinaryTreeNode left) {
this.left = left;
}

public BinaryTreeNode getRight() {
return right;
}

public void setRight(BinaryTreeNode right) {
this.right = right;
}
}

二叉树的遍历:

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
/**
* @Author: WuFan
* @Date: 2018/3/6 22:19
*/

package offer;


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

public class BinaryTree {
//前序遍历递归的方式
public void preOrder(BinaryTreeNode root){
if(null!=root){
System.out.print(root.getData()+"\t");
preOrder(root.getLeft());
preOrder(root.getRight());
}
}

//前序遍历非递归的方式
public void preOrderNonRecursive(BinaryTreeNode root){
Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
while(true){
while(root!=null){
System.out.print(root.getData()+"\t");
stack.push(root);
root=root.getLeft();
}
if(stack.isEmpty()) break;
root=stack.pop();
root=root.getRight();
}
}

//中序遍历采用递归的方式
public void inOrder(BinaryTreeNode root){
if(null!=root){
inOrder(root.getLeft());
System.out.print(root.getData()+"\t");
inOrder(root.getRight());
}
}

//中序遍历采用非递归的方式
public void inOrderNonRecursive(BinaryTreeNode root){
Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
while(true){
while(root!=null){
stack.push(root);
root=root.getLeft();
}
if(stack.isEmpty())break;
root=stack.pop();
System.out.print(root.getData()+"\t");
root=root.getRight();
}
}

//后序遍历采用递归的方式
public void postOrder(BinaryTreeNode root){
if(root!=null){
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.print(root.getData()+"\t");
}
}

//后序遍历采用非递归的方式
public void postOrderNonRecursive(BinaryTreeNode root){
Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
while(true){
if(root!=null){
stack.push(root);
root=root.getLeft();
}else{
if(stack.isEmpty()) return;

if(null==stack.lastElement().getRight()){
root=stack.pop();
System.out.print(root.getData()+"\t");
while(root==stack.lastElement().getRight()){
System.out.print(stack.lastElement().getData()+"\t");
root=stack.pop();
if(stack.isEmpty()){
break;
}
}
}

if(!stack.isEmpty())
root=stack.lastElement().getRight();
else
root=null;
}
}
}

//层序遍历
public void levelOrder(BinaryTreeNode root){
BinaryTreeNode temp;
Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
temp=queue.poll();
System.out.print(temp.getData()+"\t");
if(null!=temp.getLeft())
queue.offer(temp.getLeft());
if(null!=temp.getRight()){
queue.offer(temp.getRight());
}
}
}

public static void main(String[] args) {
BinaryTreeNode node10=new BinaryTreeNode(10,null,null);
BinaryTreeNode node8=new BinaryTreeNode(8,null,null);
BinaryTreeNode node9=new BinaryTreeNode(9,null,node10);
BinaryTreeNode node4=new BinaryTreeNode(4,null,null);
BinaryTreeNode node5=new BinaryTreeNode(5,node8,node9);
BinaryTreeNode node6=new BinaryTreeNode(6,null,null);
BinaryTreeNode node7=new BinaryTreeNode(7,null,null);
BinaryTreeNode node2=new BinaryTreeNode(2,node4,node5);
BinaryTreeNode node3=new BinaryTreeNode(3,node6,node7);
BinaryTreeNode node1=new BinaryTreeNode(1,node2,node3);

BinaryTree tree=new BinaryTree();
//采用递归的方式进行遍历
System.out.println("-----前序遍历------");
tree.preOrder(node1);
System.out.println();
//采用非递归的方式遍历
tree.preOrderNonRecursive(node1);
System.out.println();


//采用递归的方式进行遍历
System.out.println("-----中序遍历------");
tree.inOrder(node1);
System.out.println();
//采用非递归的方式遍历
tree.inOrderNonRecursive(node1);
System.out.println();

//采用递归的方式进行遍历
System.out.println("-----后序遍历------");
tree.postOrder(node1);
System.out.println();
//采用非递归的方式遍历
tree.postOrderNonRecursive(node1);
System.out.println();

//采用递归的方式进行遍历
System.out.println("-----层序遍历------");
tree.levelOrder(node1);
System.out.println();
}
}
-------------本文结束感谢阅读-------------