一、简介

二叉排序树亦称二叉查找树,是树形数据结构的一种,在一般情况下,二叉排序树的查找效率要高于普通链表,它要么是一棵空树,要么具有以下性质:

  • 若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值
  • 它的左、右子树分别为二叉排序树
  • 下面是一棵标准的二叉排序树

image-20210205180344323

二、二叉排序树的生成与节点插入

2.1、生成

1、创建Node类和Tree类

创建一个Node类作为二叉排序树的节点类,这里省略getter、setter和toString方法

1
2
3
4
5
6
7
8
public class Node {
// 节点的值
int data;
// 当前节点的左子节点
Node left;
// 当前节点的右子节点
Node right;
}

创建一个Tree类,这个类包含一个Node类型的root属性。

1
2
3
4
public class Tree {
// 当前树的根节点
Node root;
}

2、生成思路

既可以在创建二叉树对象时直接使用有参构造函数传入根节点对象,也可以在添加节点时才插入root节点

注:当一棵树root节点为空时,第一个插入该树的节点就是根节点。

2、节点插入

1、思路

在Tree类中添加一个addNode方法,如果当前树的根节点为空,那么将要添加到二叉排序树的节点设置为根节点,否则就调用root节点对象的add方法,在root对象的add方法中:

  • 如果传入要添加的节点node为空,那么直接返回,不做添加。
  • 如果传入要添加的节点node的数值小于当前节点的数值,那么进行判断,如果当前节点的左子树为空,那么直接让当前节点的左子树为要添加的节点node。否则向左进行递归添加,判断待添加节点node的数据与当前左子节点数据的关系,重复以上操作。
  • 如果传入要添加的节点node的数值大于等于当前节点的数值,这种情况需要尽量避免,这个时候进行判断,如果当前节点右子树为空,那么令当前节点右子树等于要添加的节点node。否则向右进行递归添加,判断待添加节点node的数据与当前右子节点数据的关系,重复以上操作。

2、插入节点–Tree

1
2
3
4
5
6
7
public void addNode(Node node) { 
if(this.root == null) {
this.root = node;
} else {
this.root.add(node);
}
}

3、节点的比较与插入–Node

比较节点树的静态方法如下

1
2
3
public static boolean compare(Node node1,Node node2) { 
return node1.data > node2.data;
}

Node类中插入节点的方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void add(Node node) { 
if(node == null) {
return;
}
if(compare(this,node)) {
if(this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if(this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
}

三、二叉树的前中后序遍历

前序遍历的顺序:根节点–左子节点–右子节点

中序遍历的顺序:左子节点–根节点–右子节点

后序遍历的顺序:左子节点–右子节点–根节点

3.1、递归实现

1、前序遍历

先输出当前节点,然后判断当前节点的左子树是否为空,如果不为空,就向左递归进行前序遍历。然后判断当前节点的右子树是否为空,若不为空,向右递归进行前序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Tree类 
public void preOrder() {
if(this.root != null) {
this.root.preOrder();
} else {
System.out.println("二叉树为空,无法遍历!");
}
}

//Node类
public void preOrder() {
System.out.println(this);
if(this.getLeft() != null) {
this.getLeft().preOrder();
}
if(this.getRight() != null) {
this.getRight().preOrder();
}
}

2、中序遍历

先判断当前节点左子树是否为空,若不为空,向左递归进行中序遍历,然后输出当前节点;最后判断当前节点的右子树是否为空,若不为空,向右递归进行中序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Tree类 
public void infixOrder() {
if(this.root != null) {
this.root.infixOrder();
} else {
System.out.println("二叉树为空,无法遍历!");
}
}

//Node类
public void infixOrder() {
if(this.getLeft() != null) {
this.getLeft().infixOrder();
}
System.out.println(this);
if(this.getRight() != null) {
this.getRight().infixOrder();
}
}

3、后序遍历

先判断当前节点左子树是否为空,若不为空,向左递归进行后序遍历;然后判断当前节点的右子树是否为空,若不为空,向右递归进行后序遍历。最后输出当前节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Tree类 
public void postOrder() {
if(this.root != null) {
this.root.postOrder();
} else {
System.out.println("二叉树为空,无法遍历!");
}
}

//Node类
public void postOrder() {
if(this.getLeft() != null) {
this.getLeft().postOrder();
}
if(this.getRight() != null) {
this.getRight().postOrder();
}
System.out.println(this);
}

3.2、非递归实现

我们需要使用到这一数据结构来解决问题

1、前序遍历

如果当前节点不为空,先输出当前节点信息,然后将该节点压入栈,并将指针移动到当前节点的左子节点,此时如果该左子树为空,就退出循环,此时如果栈不为空,就弹出栈顶数据,将指针移动到当前结点右子树,循环,直到栈空或者当前节点为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void preOrder(Node node) { 
Stack<Node> nodeStack = new Stack<>();
while(node != null || !nodeStack.empty()) {
while(node != null) {
System.out.println(node);
nodeStack.push(node);
node = node.getLeft();
}
if(!nodeStack.empty()) {
node = nodeStack.pop();
node = node.getRight();
}
}
}

2、中序遍历

如果当前节点不为空,将当前节点压入栈中,然后将指针指向当前节点左子树,直到左子树为空,此时栈不为空,将栈顶元素弹出并输出后,将指针移动到当前结点右子树,循环,直到栈空或者当前节点为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void midOrder(Node node) { 
Stack<Node> nodeStack = new Stack<>();
while(node != null || !nodeStack.empty()) {
while(node != null) {
nodeStack.push(node);
node = node.getLeft();
}
if(!nodeStack.empty()) {
node = nodeStack.pop();
System.out.println(node);
node = node.getRight();
}
}
}

3、后序遍历

需要利用到一个辅助栈用于输出结果,由于栈具有先进后出的特点,而后序遍历的顺序是左右根,所以压入栈顺序为根、右、左。最后使用辅助栈输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void postOrder(Node node) { 
if(node == null) {
System.out.println("要遍历的二叉树为空!");
return;
}
Stack<Node> stack = new Stack<>();
//辅助栈
Stack<Node> assistStack = new Stack<>();
while(node != null || !stack.isEmpty()) {
while(node != null) {
stack.push(node);
assistStack.push(node);
node = node.getRight();
}
if(!stack.isEmpty()) {
node = stack.pop();
node = node.getLeft();
}
}
while(!assistStack.isEmpty()) {
System.out.println(assistStack.pop());
}
}

四、二叉排序树节点的删除

二叉排序树中的节点可以分为以下三种:

  • 叶子节点
  • 有一棵子树的节点
  • 有两棵子树的节点

我们需要判断待删除节点为什么类型,然后根据节点类型进行删除操作。

4.1、编写用于搜索待删除节点和待删除节点父节点的方法

1、搜索待删除节点的方法

搜索待删除节点,首先判断当前二叉排序树是否为空,若为空,直接返回,否则调用当前二叉排序树根节点的search方法

  • 如果当前传入的数据data的值刚好等于当前节点的data值,那么当前节点就是待删除节点,直接返回即可

  • 如果当前传入的数据data的值小于当前节点的值且当前节点的左子树为空,证明当前二叉排序树中没有要删除的节点;如果当前传入数据data值小于当前节点值且当前节点左子树不为空,那么调用当前节点左子树的search方法,向左递归查询。

  • 同理,如果当前传入的数据data值大于当前节点值且当前节点右子树为空,证明当前二叉排序树没有要删除节点,此刻只能返回null;如果当前传入数据data值大于当前节点且当前节点右子树不为空,那么调用当前右子树的search方法,向右递归查询。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*** 
* 根据节点的data数据搜索Node节点
* @param data 目标节点的data值
* @return 如果找到符合条件的node节点,那么返回该node节点
* 否则返回null
*/
public Node search(int data) {
if(data == this.data) {
return this;
} else if(data < this.data) {
if(this.left == null) {
return null;
}
return this.left.search(data);
} else {
if(this.right == null) {
return null;
}
return this.right.search(data);
}
}

2、搜索待删除节点父节点的方法

搜索待删除节点的父节点的方法,同理先判断当前二叉排序树的根节点是否为空,若为空,返回null,否则调用当前二叉排序树的根节点的搜索待删除节点父节点(searchParent)的方法。

  • 如果当前节点的左子树不为空且当前节点左子树的data值等于用户传入的要检索的data值或者当前节点右子树不为空且当前节点右子树的data值等于用户传入的要检索的data值,那么证明当前节点就是待检索节点,返回当前节点。

  • 如果传入的data值小于当前节点值且当前左子树不为空,那么调用当前左子节点的searchParent的方法。

  • 同理,如果传入data值大于等于当前节点的data值且当前节点右子树不为空,那么调用当前节点右子节点的searchParent方法。

  • 如果程序走到此处,证明没有找到待删除数据的父节点,此时返回null。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*** 
* 查找要删除节点的父节点
* @param data 要删除的节点的数据
* @return 待删除节点的父节点
*/
public Node searchParent(int data) {
if((this.left != null && this.left.data == data) || (this.right != null && this.right.data == data)) {
return this;
} else {
//如果要查找的值小于当前节点值,且当前节点左子节点不为空
//递归向左
if(data < this.data && this.left != null) {
return this.left.searchParent(data);
} else if(data >= this.data && this.right != null) {
return this.right.searchParent(data);
} else {
return null;
}
}
}

4.2、删除叶子节点

对于叶子节点,我们需要先找到待删除节点target和待删除节点的父节点parent,然后判断待删除叶子节点是其父节点的左子树还是右子树,如果为左子树,那么令parent.left = null,否则让parent.right = null。

  • 二叉排序树中判断待删除节点是否为叶子节点的静态方法与Node类中判断传入节点为当前左子树/右子树的方法
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
/*** 
* 判断node节点是否为叶子节点
* @param node
* @return
*/
public static boolean isLeaf(Node node) {
return node.left == null && node.right == null;
}

/***
* 判断传入节点是否为当前节点左子节点的方法
* @param target
* @return
*/
public boolean isLeft(Node target) {
return this.left != null && this.left.data == target.data;
}

/***
* 判断传入节点是否为当前节点右子节点的方法
* @param target
* @return
*/
public boolean isRight(Node target) {
return this.right != null && this.right.data == target.data;
}

4.3、删除有一棵子树的节点

对于有一棵子树的节点的删除,我们需要找到待删除节点和待删除节点的父节点,然后判断两个条件:1(待删除节点是其父节点的左子树还是右子树)、2(待删除节点有左子树还是右子树)

  • 如果待删除节点有左子树且为其父节点的左子树:此时让待删除节点的父节点的左子树等于待删除节点的左子树,即parent.left = target.left。

  • 如果待删除节点有左子树且为其父节点的右子树:此时根据二叉排序树的性质,待删除节点的左子树的数据要全部大于(等于)其父节点的数据,所以令待删除节点父节点的右子树等于待删除节点的左子树,即parent.right = target.left。

  • 如果待删除节点有右子树且为其父节点的左子树:此时让parent.left = target.right

  • 如果待删除节点有右子树且为其父节点的右子树,此时让parent.right = target.right

  • Node类中判断传入节点是否为当前节点左/右子树的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*** 
* 判断传入节点是否为当前节点左子节点的方法
* @param target
* @return
*/
public boolean isLeft(Node target) {
return this.left != null && this.left.data == target.data;
}

/***
* 判断传入节点是否为当前节点右子节点的方法
* @param target
* @return
*/
public boolean isRight(Node target) {
return this.right != null && this.right.data == target.data;
}

4.4、删除有两棵树的节点

对于有两棵子树的节点的删除:需要先取到待删除节点的右子树的最小节点的值,然后将数值最小的节点删除,最后将前面取到的最小节点的值赋值给待删除节点。

  • 获取待删除节点右子树中最小节点的值并删除最小节点的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*** 
* 1 返回以node为根节点的二叉排序树的最小节点的值
* 2 删除以node为根节点的二叉排序树的最小节点
* @param node 传入的节点(二叉排序树的根节点)
* @return 返回的以Node为根节点的二叉排序树的根节点的值
*/
public int delTreeMin(Node node) {
Node target = node;
//循环的查找左节点,就能找到最小值
while(target.left != null) {
target = target.left;
}
//此时循环结束后,target指向最小节点
//删除最小节点
delNode(target.data);
return target.data;
}
  • 判断当前节点是否有两棵子树的方法
1
2
3
4
5
6
7
8
/*** 
* 判断传入节点是否有左右子树的方法
* @param node
* @return
*/
public static boolean hasTwoSon(Node node) {
return node.left != null && node.right != null;
}

4.5、二叉排序树中根据节点数据删除节点的方法

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
/*** 
* 根据data删除节点
* @param data 要删除的节点的data
*/
public void delNode(int data) {
if(root == null) {
return;
} else {
//1 先找到要删除的节点target
Node target = search(data);
//1.1 如果要删除的节点不存在,直接返回
if(target == null) {
return;
}
//1.2 如果当前树只有一个节点,且为待删除节点,那么直接置空
if(root.left == null && root.right == null) {
root = null;
return;
}
//2 去找到target的父节点
Node parent = searchParent(data);
//2.1 如果要删除的节点是叶子节点
if(isLeaf(target)) {
//a 判断target是父节点的左子节点还是有子节点
if(parent.isLeft(target)) {
//如果是左子节点
parent.left = null;
} else if(parent.isRight(target)) {
//如果是右子节点
parent.right = null;
}
} else if(hasTwoSon(target)) {
//2.2 如果要删除的节点有左右子树
//删除右子树最小节点,同时将最小节点的值取出来
int minData = delTreeMin(target.right);
target.data = minData;
} else {
//2.3 删除只有一棵子树的节点
//如果待删除节点有左子节点
if(target.left != null) {
//如果target是parent的左子节点
if(parent.isLeft(target)) {
parent.left = target.left;
} else {
//说明target是parent的右子节点
parent.right = target.left;
}
} else {
//待删除节点有右子节点
//如果target是parent的左节点
if(parent.isLeft(target)) {
parent.left = target.right;
} else {
parent.right = target.right;
}
}
}
}
}

五、使用递归获取二叉树深度

1
2
3
4
5
6
7
8
9
10
/*** 
* 递归获取二叉树深度的方法
* 如果根为空:返回0
* 否则分别递归深入左右节点,返回深度
* @param root 二叉树的根节点
* @return 二叉树深度
*/
public static int getTreeDepth(Node root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
}

六、测试

6.1、测试二叉排序树的生成和插入

1
2
3
4
5
6
7
8
9
Tree tree = new Tree(null);
int[] arr = {7,8,19,-1,26,100,777,-1012,222,18};
for (int i = 0; i < arr.length; i++) {
int data = arr[i];
Node node = new Node(data);
tree.addNode(node);
}
System.out.println("tree:");
Tree.show(tree.root);

结果

image-20210205232120723

6.2、测试二叉排序树的删除

1、删除叶子节点

1
2
3
4
5
System.out.println("---------------------------------删除叶子节点-1012,删除前:"); 
Tree.show(tree.root);
tree.delNode(-1012);
System.out.println("---------------------------------删除叶子节点-1012,删除后:");
Tree.show(tree.root);

删除前:

image-20210205232357649

删除后:

image-20210205232417944

2、删除有一棵子树的节点

1
2
3
4
5
System.out.println("---------------------------------删除有一棵树的节点-1,删除前:"); 
Tree.show(tree.root);
tree.delNode(-1);
System.out.println("---------------------------------删除有一棵树的节点-1,删除后:");
Tree.show(tree.root);

删除前:

image-20210205232621385

删除后:

image-20210205232635923

3、删除有两棵子树的节点

1
2
3
4
5
System.out.println("---------------------------------删除有两棵子树的节点7,删除前:"); 
Tree.show(tree.root);
tree.delNode(7);
System.out.println("---------------------------------删除有两棵子树的节点7,删除后:");
Tree.show(tree.root);

删除前:

image-20210205232820859

删除后:

image-20210205232834775