记录生活中的点点滴滴

0%

二叉树的基本操作

这篇文章主要谈谈二叉树树这一数据结构,当然这都是一些基础知识。主要内容如下:

  • 二叉树基本类
  • 用数组去构建二叉树
  • 先序遍历、中序遍历、后续遍历
  • 层次遍历
  • 非递归先序遍历、非递归中序遍历、非递归后续遍历
  • 线索化二叉树

拒绝伪代码,我们要自己一个一个写然后运行,效果更佳!

二叉树基本类

我们先构建一个二叉树的类,它有左孩子结点、右孩子结点、数据域,数据域这里我们直接用 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 {
//main方法
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;//右指针
//1.如果leftType==0表示指向的是左子树,如果1则表示指向前驱结点
// 2.如果rightType==0表示指向是右子树,如果1表示指向后继结点
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;
//1.先线索化左子树
midThreded(node.left);
//2.线索化当前节点
//2.1先处理左边节点为空的情况
if(node.left==null){
node.leftType = 1;//设置leftType为1,表示指向前驱节点
node.left = pre;
}
//2.2再处理右节点为空的情况,但是不能明着用node.right去,而是用pre去解决
//前驱节点不为空且前驱节点的右指针为空
if(pre!=null && pre.right==null){
pre.right = node;//让前驱结点的右指针指向当前结点
pre.rightType = 1;
}
//2.3最后要让当前节点是下一个节点的前驱节点
pre = node;
//3.线索化右子树
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;
//1.线索化当前节点
//1.1先处理左边节点为空的情况
if(node.left==null){
node.leftType = 1;//设置leftType为1,表示指向前驱节点
node.left = pre;
}
//1.2再处理右节点为空的情况,但是不能明着用node.right去,而是用pre去解决
//前驱节点不为空且前驱节点的右指针为空
if(pre!=null && pre.right==null){
pre.right = node;//让前驱结点的右指针指向当前结点
pre.rightType = 1;
}
//1.3最后要让当前节点是下一个节点的前驱节点
pre = node;
//2.先线索化左子树
if(node.leftType==0)
preThreded(node.left);
//3.线索化右子树
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;
}

因为遍历后序线索化二叉树,需要回溯,那么要求二叉树基本类中多一个指向父节点的成员属性,就懒得写了,思想都差不多。