这篇文章主要谈谈二叉树树这一数据结构，当然这都是一些基础知识。主要内容如下：
- 二叉树基本类
- 用数组去构建二叉树
- 先序遍历、中序遍历、后续遍历
- 层次遍历
- 非递归先序遍历、非递归中序遍历、非递归后续遍历
- 线索化二叉树
拒绝伪代码，我们要自己一个一个写然后运行，效果更佳！
二叉树基本类
我们先构建一个二叉树的类，它有左孩子结点、右孩子结点、数据域，数据域这里我们直接用 int 类型表示，如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class TreeNode{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
|
下面我们会在测试类中写一系列二叉树相关的方法，我们可以先把骨架搭出来，如下所示：
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
|
public class Demo1 {
public static void main(String[] args) {}
public static TreeNode toTree(int[] arr){}
public static void preOrder(TreeNode root){}
public static void midOrder(TreeNode root){}
public static void postOrder(TreeNode root){}
public static void levelOrder(TreeNode root){}
public static void preOrderWithStack(TreeNode root){}
public static void midOrderWithStack(TreeNode root){}
public static void postOrderWithStack(TreeNode root){}
}
|
用数组去构建二叉树
用数组去构建一个二叉树，最主要的就是找到二叉树的最后一个非叶子节点，进行相关设置即可，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static TreeNode toTree(int[] arr){
if (arr.length==0)
return null;
int len = arr.length;
int lastIndex = len/2-1;
ArrayList<TreeNode> list = new ArrayList<>();
for (int i = 0; i < len; i++) {
list.add(new TreeNode(arr[i]));
}
for (int i = 0; i < lastIndex; i++) {
TreeNode node = list.get(i);
node.left = list.get(2*i+1);
node.right = list.get(2*i+2);
}
TreeNode node = list.get(lastIndex);
node.left = list.get(lastIndex*2+1);
if(len%2!=0)
node.right = list.get(lastIndex*2+2);
return list.get(0);
}
|
我们可以在mian方法中使用这个方法，并用 debug 的形式看看我们的代码是否正确。
递归遍历
下面我们介绍三种常见的递归遍历方法：先序、中序、后序，很简单的。
先序遍历
1
2
3
4
5
6
7
8
|
public static void preOrder(TreeNode root){
if(root==null)
return;
System.out.print(root.data+"-->");
preOrder(root.left);
preOrder(root.right);
}
|
mian方法中进行测试：
1
2
3
4
5
6
7
| System.out.println("---根据数组构建一个二叉树---");
int[] arr = {1,2,3,4,5,6,7,8,9,10};
TreeNode root = toTree(arr);
System.out.println("-----先序遍历树----");
preOrder(root);
System.out.println();
|
结果如下：
中序遍历
1
2
3
4
5
6
7
8
|
public static void midOrder(TreeNode root){
if(root==null)
return;
midOrder(root.left);
System.out.print(root.data+"-->");
midOrder(root.right);
}
|
main方法后面添加下面代码再进行测试：
1
2
3
| System.out.println("-----中序遍历树----");
midOrder(root);
System.out.println();
|
结果如下：
后序遍历
1
2
3
4
5
6
7
8
|
public static void postOrder(TreeNode root){
if(root==null)
return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data+"-->");
}
|
main方法继续添加：
1
2
3
| System.out.println("-----后序遍历树----");
postOrder(root);
System.out.println();
|
结果如下：
层次遍历
层次遍历需要借助队列这个数据结构实现，具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static void levelOrder(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode temp = queue.poll();
System.out.print(temp.data+"-->");
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
}
}
|
main方法再添加测试：
1
2
3
| System.out.println("-----层次遍历树----");
levelOrder(root);
System.out.println();
|
结果如下：
非递归遍历
遍历二叉树，我们也可以不用递归的方式，用非递归进行，借助栈这一数据结构即可。
先序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public static void preOrderWithStack(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
TreeNode temp = root;
while(temp!=null || !stack.isEmpty()){
while (temp!=null){
System.out.print(temp.data+"-->");
stack.push(temp);
temp = temp.left;
}
if(!stack.isEmpty()){
temp = stack.pop();
temp = temp.right;
}
}
}
|
main方法添加测试：
1
2
3
| System.out.println("----非递归先序遍历----");
preOrderWithStack(root);
System.out.println();
|
结果如下：
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public static void midOrderWithStack(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
TreeNode temp = root;
while(temp!=null || !stack.isEmpty()){
while (temp!=null){
stack.push(temp);
temp = temp.left;
}
if(!stack.isEmpty()){
temp = stack.pop();
System.out.print(temp.data+"-->");
temp = temp.right;
}
}
}
|
main方法添加测试：
1
2
3
| System.out.println("----非递归中序遍历----");
midOrderWithStack(root);
System.out.println();
|
结果如下：
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static void postOrderWithStack(TreeNode root){
Stack<TreeNode> stack = new Stack<>();
TreeNode temp = root;
TreeNode lastVisit = null;
while(temp!=null || !stack.isEmpty()){
while (temp!=null){
stack.push(temp);
temp = temp.left;
}
temp = stack.peek();
if(temp.right==null || temp.right==lastVisit){
lastVisit = temp;
System.out.print(temp.data+"-->");
stack.pop();
temp = null;
}else {
temp = temp.right;
}
}
}
|
main方法添加测试：
1
2
3
| System.out.println("----非递归后序遍历----");
postOrderWithStack(root);
System.out.println();
|
结果如下：
线索化二叉树
在使用二叉链表的存储结构的过程中，会存在大量的空指针域，为了充分利用这些空指针域，引申出了“线索二叉树”。
我们可以通过充分利用二叉链表中的空指针域，存放节点在某种遍历方式下的前驱和后继节点的指针。 我们把这种指向前驱和后继的指针成为线索，加上线索的二叉链表成为线索链表，对应的二叉树就成为“线索二叉树(Threaded Binary Tree)” 。
用中序线索化二叉树为例，如果结点的左指针为空，那么把它指向其中序遍历之前的那个节点；如果结点的右指针为空，那么把它指向其中序遍历之后的那个节点；如下图所示：
对，那个二叉树基本类也要改一下，增加左右两个标识，若为0，表示指向其左右子树；若为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
26
27
28
29
| public class Demo {
public static void main(String[] args) {
System.out.println("---根据数组构建一个二叉树---");
int[] arr = {1,2,3,4,5,6,7,8,9,10};
TreeNode root = toTree(arr);
}
public static TreeNode toTree(int[] arr){}
public static TreeNode pre = null;
public static void midThreded(TreeNode node){}
public static void midThrededList(TreeNode node){}
public static void preThreded(TreeNode node){}
public static void preThrededList(TreeNode node){}
public static void postThreded(TreeNode node){}
}
class TreeNode{
}
|
二叉树基本类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /结点类
class TreeNode{
public int data;
public TreeNode left;
public TreeNode right;
public int leftType;
public int rightType;
public TreeNode(int data) {
this.data = data;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
'}';
}
}
|
中序线索化二叉树
构建线索化二叉树需要我们设置一个指向当前节点的前驱节点的指针，就是骨架中的 public static TreeNode pre = null; ，采用递归方式进行创建。具体如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public static void midThreded(TreeNode node){
if(node==null)
return;
midThreded(node.left);
if(node.left==null){
node.leftType = 1;
node.left = pre;
}
if(pre!=null && pre.right==null){
pre.right = node;
pre.rightType = 1;
}
pre = node;
midThreded(node.right);
}
|
详细解释请看注释，若想想要看是否构建成功，可以通过 debug 看构建的情况，或者等下面完成遍历方法时进行测试。
中序遍历线索化二叉树
借助线索二叉的特性，我们可以不用递归来完成中序遍历，但是代码并不是很简单，先找到最左边节点，然后通过while循环，判断其右节点类型完成，具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static void midThrededList(TreeNode node){
while (node!=null && node.leftType==0){
node = node.left;
}
while (node!=null){
System.out.print(node.data+"-->");
if(node.rightType==1){
node = node.right;
}else {
node = node.right;
while (node!=null && node.leftType==0){
node = node.left;
}
}
}
}
|
mian方法后面可以添加下面代码进行测试：
1
2
3
4
5
6
| System.out.println("---中序线索化二叉树---");
midThreded(root);
System.out.println("---中序遍历线索化二叉树---");
midThrededList(root);
System.out.println();
|
结果如下：
先序线索化二叉树
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 preThreded(TreeNode node){
if(node==null)
return;
if(node.left==null){
node.leftType = 1;
node.left = pre;
}
if(pre!=null && pre.right==null){
pre.right = node;
pre.rightType = 1;
}
pre = node;
if(node.leftType==0)
preThreded(node.left);
if(node.rightType==0)
preThreded(node.right);
}
|
先序遍历线索化二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public static void preThrededList(TreeNode node){
while (node!=null && node.leftType==0){
System.out.print(node.data+"-->");
node = node.left;
}
while (node!=null){
System.out.print(node.data+"-->");
if(node.rightType==1){
node = node.right;
}else {
node = node.right;
while (node!=null && node.leftType==0){
System.out.print(node.data+"-->");
node = node.left;
}
}
}
}
|
先序也要借助那个 pre 指针，所以下面我们进行测试的时候要把前面中序测试添加的代码删除掉，换成下面的：
1
2
3
4
5
6
| System.out.println("---先序线索化二叉树---");
preThreded(root);
System.out.println("---先序遍历线索化二叉树---");
preThrededList(root);
System.out.println();
|
结果如下：
后序线索化二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public static void postThreded(TreeNode node){
if(node==null)
return;
postThreded(node.left);
postThreded(node.right);
if(node.left==null){
node.leftType = 1;
node.left = pre;
}
if(pre!=null && pre.right==null){
pre.rightType = 1;
pre.right = node;
}
pre = node;
}
|
因为遍历后序线索化二叉树，需要回溯，那么要求二叉树基本类中多一个指向父节点的成员属性，就懒得写了，思想都差不多。