数据结构-二叉排序/搜索树

二叉排序树(BST)详细讲解,顺带讲解什么是二叉搜索树和线索二叉树。

二叉排序树BST★

二叉排序树,又称为二叉查找树。它或者是一颗空树,或者具有下列性质的二叉树。

  • 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 它的左、右子树也分别为二叉排序树。

二叉排序树插入

根据其定义,我们将插入节点的方法展示如下:

  1. 第一个输入的数据作为此二叉树的树根。
  2. 之后的数据以递归的方式与树根进行比较,小于数个置于左子树,大于树根置于右子树。

下面给出其递归实现过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//给树增加一个新节点
public void insert(int key){
root = insert(key,root);
}
private TreeNode insert(int key,TreeNode t){
//递归结束条件
if(t==null){
return new TreeNode(key,null,null);
}
//递归式 key小,插入当前节点的左子树
if(t.key>key){
t.left = insert(key,t.left);
}
//key大于当前节点,插入当前节点的右子树。
else if(t.key<key){
t.right = insert(key,t.right);
}
return t;
}

建立二叉树后,我们仅需通过一次中序遍历(LDR,左下为最小值,右下为最大值)即可完成排序输出,当然,我们也可以将得到的结果放入队列中加以存储。

二叉排序树删除

对于二叉排序树中的节点A,对它的删除分为三种情况,目的就是不改变排序树的性质:

  1. 如果A为叶子节点,则直接删除节点A即可。
  2. 如果A只有一个子节点,就直接将A的子节点连至A的父节点上,并将A删除;
  3. 如果A有两个子节点,我们就以用A节点的直接前驱或者直接后继来替换A节点,调整直接前驱或者直接后继的位置。

分析:

下面分为三个情况进行讨论,对应上面的三类情况:

情况一:叶子节点直接删除即可,我们直接将当前结点置空。

情况二:这里我们无需寻找其父节点,直接将其存在的子树(左或右子树)的根节点的地址覆盖要删除的结点即可,因为在递归的过程中会修改其父节点的子树地址。

情况三:当有两个子节点时,我们为了保持排序树本身的性质不变,需要找其直接前驱或者直接后继来顶替该位置,由上图我们可以看出,若寻找其直接前驱,应找其左子树的最大节点(上图为37节点);若找其直接后继,应找其右子树的最小节点(上图为48节点)。

在这里,我们先按照找直接前驱进行讨论

(1)如何寻找37节点呢?因为我们要删除47节点,所以我们寻找其直接前驱应在47的左子树上寻找最大值。问题相继就转变成了以35为根节点的一棵二叉排序树如何寻找最大值的问题。根据二叉排序树的定义和我们插入排序的一些经验来看,寻找一棵树的最大值仅需要不断的从根节点寻找其右孩子即可,直到当前结点的右孩子为空,那这个结点就是我们要寻找的节点。

(2)找到之后,用替换结点(37)的值来替换我们要删除的结点,然后我们就可以考虑删除(37)那个节点就可以了,而(37)结点一定为叶子节点或者只有左子树的结点,然后我们把要删除节点的直接前驱结点(37)按照情况一或情况二进行删除即可。

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 void remove(int key){
root = remove(key,root);
}
private TreeNode remove(int key,TreeNode t){
//要删除结点为空,返回空
if(t==null) return null;
//寻找要删除的结点,并在递归返回的时候更新各个结点的子树引用
if(key<t.key){
t.left = remove(key,t.left);
}
else if(key>t.key){
t.right = remove(key,t.right);
}
//找到之后查看其有无左右子树 若都有找其直接前驱
else if(t.left!=null&&t.right!=null){
//不删除结点,直接赋值 将47改成37
//finMax请在下面的代码实现中查看
t.key = findMax(t.left);
//然后将37结点删除
t.right = remove(t.key,t.right);
}
//若只有一个子树或者为叶子节点
//叶子节点直接置空,只有一个子树时直接与子节点相连
else{
t= (t.left != null)?t.left:t.right;
}
return t;
}

直接后继分析过程与上面类似,已在下面的的代码实现中给出,在此不再赘述。

二叉排序树代码实现

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
public class BinarySearchTree {
//树结点
private static class TreeNode{
int key;
TreeNode left;
TreeNode right;
private TreeNode(int key, TreeNode left, TreeNode right) {
this.key = key;
this.left = left;
this.right = right;
}
}
//根节点
private TreeNode root;
//初始化
public BinarySearchTree() {
this.root = null;
}
//树置空
public void makeEmpty(){
this.root = null;
}
//判断树是否为空
public boolean isEmpty(){
return root==null;
}
//是否包含某个元素
public boolean search(int key){
return search(this.root,key);
}
//采用递归来进行二叉排序树的查找
private boolean search(TreeNode current,int key){
//递归终止条件1:如果没找到,则返回false
if(current==null) return false;
//如果当前节点的值大于key,则应该从当前节点的左子树当中查找
if(key<current.key) {
return search(current.left,key);
}
//如果当前节点的值小于key,则应该从当前结点的右子树当中查找
else if(key>current.key) {
return search(current.right,key);
}
//递归终止条件2:如果相等,则返回true
else return true;
}
//给树增加一个新节点
public void insert(int key){
root = insert(key,root);
}
private TreeNode insert(int key,TreeNode t){
//递归结束条件
if(t==null){
return new TreeNode(key,null,null);
}
//递归式 key小,插入当前节点的左子树
if(t.key>key){
t.left = insert(key,t.left);
}
//key大于当前节点,插入当前节点的右子树。
else if(t.key<key){
t.right = insert(key,t.right);
}
return t;
}
//给树移除一个节点 ★
public void remove(int key){
root = remove(key,root);
}
//采用其后继节点的方式进行
private TreeNode remove(int key,TreeNode t){
if(t==null){
return null;
}
if(key<t.key){
t.left = remove(key,t.left);
}
else if(key>t.key){
t.right = remove(key,t.right);
}
else if(t.left!=null&&t.right!=null){
t.key = findMax(t.left);
t.left = remove(t.key,t.left);
}
else{
t= (t.left != null)?t.left:t.right;
}
return t;
}
//查找树中的最小值 最左边那个值
public int findMin(){
if(isEmpty()){
return Integer.MIN_VALUE;
}
return findMin(root);
}
private int findMin(TreeNode t){
if(t==null){
return Integer.MIN_VALUE;
}
if(t.left!=null){
t = t.left;
}
return t.key;
}
//查找树中的最大值
public int findMax(){
if(isEmpty()){
return Integer.MAX_VALUE;
}
return findMax(root);
}
private int findMax(TreeNode t){
if(t==null){
return Integer.MAX_VALUE;
}
if(t.right!=null){
t = t.right;
}
return t.key;
}
//输出树中元素 中序遍历可有序输出
public void printTree(){
if(isEmpty()){
System.out.println("Empty Tree");
}
else{
printTree(root);
}
System.out.println();
}
private void printTree(TreeNode current){
if(current!=null){
printTree(current.left);
System.out.print(current.key+" ");
printTree(current.right);
}
}
}

二叉搜索树

二叉搜索树概论

二叉搜索树特点如下:

  • 可以为空集合,但若不是空集合则节点上一定要有一个键值。
  • 每一个树根的值需大于左子树的值
  • 每一个树根的值需小于右子树的值
  • 左右子树也是二叉搜索树
  • 树的每个节点值都不同

事实上,二叉搜索树是在二叉排序树的基础上的进一步延伸,所以,只要懂得二叉树的排序就可以理解二叉排序树的搜索。这样的结构有一个好处是很容易获得最大值(Maximum)、最小值(minimum)、某元素的前驱(Precursor)、某元素的后继(Successor)。

  1. 最大值:树的最右节点。
  2. 最小值:树的最左节点。
  3. 某元素前驱:左子树的最右。
  4. 某元素的后继:右子树的最左。

其基本操作有:(1)搜索 (2)遍历 (3)插入 (4)删除

二叉搜索树搜索

算法:

  1. 从根结点开始查找,把根结点设置为当前结点;
  2. 若当前结点为空,返回null;
  3. 若当前结点不为空,用当前结点的value跟查找value作比较;
  4. 若当前结点value等于查找value,那么该value就是查找目标,返回当前结点;
  5. 若当前结点value大于查找value,把当前结点的左子结点设置为当前结点,跳转步骤2;
  6. 若当前结点value小于查找value,把当前结点的右子结点设置为当前结点,跳转步骤2;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public  Node<Integer> searchInBinarySortTree(Node<Integer> root,int value){
if(root==null){
return null;
}
else if(root.getData().equals(value)){
return root;
}
else if(root.getData()>value){
return searchInBinarySortTree(root.getLchild(),value);
}
else if(root.getData()<value){
return searchInBinarySortTree(root.getRchild(),value);
}
return null;
}

二叉搜索树遍历

由于二叉搜索树的特性,如使用中序遍历则可输出一个排好序的二叉树,这里就不细讲了,若不了解请点击这里数据结构-LeetCode树相关题目进行了解。

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------