首页 数据结构

# 二叉搜索树

二叉树定义

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这个定义有助于我们写出更高效地在树中插入、查找和删除节点的算法。二叉树在计算机科学中的应用非常广泛。

二叉树种类

普通二叉树、完全二叉树、满二叉树、线索二叉树、哈夫曼树、二叉搜索树（排序树）、平衡二叉树、AVL 平衡二叉树、红黑树、B 树、B + 树

二叉搜索树

二叉搜索树（BST）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。

image-20230303090523796
# 不认识 "二叉" 这俩字了… 这里先只模拟二叉搜索树
# 啥？你问我为啥？
# 因为书上只讲了二叉搜索树🤪
方法 效果
❑ insert(key) 向树中插入一个新的键
❑ search(key) 在树中查找一个键。如果节点存在，则返回 true；如果不存在，则返回 false
❑ inOrderTraverse() 通过中序遍历方式遍历所有节点
❑ preOrderTraverse() 通过先序遍历方式遍历所有节点
❑ postOrderTraverse() 通过后序遍历方式遍历所有节点
❑ min() 返回树中最小的值 / 键
❑ max() 返回树中最大的值 / 键
❑ remove(key) 从树中移除某个键

废话少说，直接上代码！(因为写的时候全写注释里面了，所以主要看注释内容哦)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 先定义节点类, 有存储值key  有左节点left  有右节点right
class Node{
  constructor(key){
    this.key = key
    this.left = null
    this.right = null
  }
}

// 定义二叉树类, 有一个根节点,默认为null
class BinarySearchTree{
  constructor(){
    this.root = null
  }
    
}

# 插入节点

直接开始！注意其中的递归！

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
//插入节点的方法 
insertNode(node,key){
  if(this.compareFn(key,node)<0){
    if(node.left===null){
      node.left = new Node(key)
    }else{
      this.insertNode(node.left, key)	//比较发现小了? 递归往左
    }
  }
  else{
    if(node.right===null){
      node.right = new Node(key)
    }else{
      this.insertNode(node.right, key)	//比较发现大了? 递归往右
    }
  }
}
// 插入key	判断根节点如果都没有?那直接新建节点作为根节点,key存进去
insert(key){
  if(this.root===null){
    this.root=new Node(key)
    return true
  }else{
    this.insertNode(this.root,key)
  }
}

#

在看得出来二叉搜索树中需要大量的比较，小于 root 去左边，大于 root 去右边，那查找也不例外了，小于 root 去左边找。大于再去右边找，直到等于某个 key, 既然一直要做各种比较，我们把比较的过程封装成一个函数.

1
2
3
4
5
6
7
8
9
10
11
//封装比较
function compare(key, node) {
  if(node === null) return;
  else if (key > node.key) {
    return 1;
  } else if (key < node.key) {
    return -1;
  } else {
    return 0;
  }
}

大概这样子👺 我懒得写了，让 chatGPT 写的…
image-20230303091718968

# 查询节点

查询也类似 同样是递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//查询节点的方法
searchNode(node,key){
  if(node === null){
    return false
  }
  if(this.compareFn(key,node)<0){
     return this.searchNode(node.left,key)
  }else if(this.compareFn(key,node)>0){
     return this.searchNode(node.right,key)
  }else{
    return true
  }
}
//查询key
search(key){
   return this.searchNode(this.root,key)
}

早上 7:08 早起准备开始学习，时间真的很宝贵，洗漱的时候开了热水，放出来的全是冷水，还扣我 2 毛 5 太坑了！等我有钱了一定要有一个 24 小时热水的家！就像 汪峰在《春天里》唱的那样（emm 好像是这个歌名吧…）看来汪峰也经历过洗冷水的痛

下面就全是递归！地柜！递龟！😵😵😵

# 遍历

# 中序

中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是以 从小到大 的顺序访问所有节点。

image-20230303083706397 
1
2
3
4
5
6
7
8
9
10
11
12
//中序遍历节点
inOrderTraverseNode(node,callback){
  if(node!=null){
    this.inOrderTraverseNode(node.left,callback)
    callback(node.key) // 3 5 6 7 8 9 10 11...
    this.inOrderTraverseNode(node.right,callback)
  }
}
//中序遍历
inOrderTraverse(callback){
  return this.inOrderTraverseNode(this.root,callback)
}

# 先序

先序遍历是以 优先于 后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

image-20230303083735420 
1
2
3
4
5
6
7
8
9
10
11
12
//先序遍历节点
preOrderTraverseNode(node,callback){
  if(node!=null){
    callback(node.key)	// 11 7 5 3 6 9 8 10 15 ...
    this.preOrderTraverseNode(node.left,callback)
    this.preOrderTraverseNode(node.right,callback)
  }
}
//先序遍历
preOrderTraverse(callback){
  return this.preOrderTraverseNode(this.root,callback)
}

# 后序

后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小。

image-20230303084820414 
1
2
3
4
5
6
7
8
9
10
11
12
//后序遍历节点
postOrderTraverseNode(node,callback){
   if(node!=null){
    this.postOrderTraverseNode(node.left,callback)
    this.postOrderTraverseNode(node.right,callback)
    callback(node.key)
  }
}
//后序遍历
postOrderTraverse(callback){
  return this.postOrderTraverseNode(this.root,callback)
}

# 总结

哈哈哈当初数据结构听得云里雾里，现在倒是发现了，先序后序中序就是 callback 回调在节点遍历时放的位置不同

就像八卦一样

乾 (☰) 坤 (☷) 震 (☳) 艮 (☶) gèn 离 (☲) 坎 (☵) 兑 (☱) 巽 (☴) xùn

八卦

各位看官！看 离卦 兑卦 巽卦像不像 中序，先序，后序？(好吧确实很抽象)

另外：以上方法全部都是分开写的，比如 (xx 遍历，xx 遍历节点)

之所以这样，是因为正常情况需要把遍历节点的方法作为 private 方法，不能让用户访问或者修改

只应该向用户暴露 xx 遍历 方法 而不展示内部细节

这里用的是 JS 就当是处理过了吧已经 知道这个概念就行

# 言归正传，来看搜索节点最大值最小值

先看图

image-20230303092501119

你能在三秒钟之内找到最小值和最大值吗？

啥？你一秒就好了？你真行！

但计算机比你更行，都知道是最左边节点和最右边节点嘛，因为插入节点时就排好序了

直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//搜索最小值
min(){
  return this.minNode(this.root)
}
//搜索最小节点
minNode(node){
  let current = node
  if(current != null && current.left != null){	// 持续往左找,直到最左
    current = current.left
  }
  return current
}
//搜索最大值
  max(){
  return this.maxNode(this.root)
}
//搜索最大节点
maxNode(node){
  let current = node
  if(current != null && current.right != null){	// 持续往右找,直到最右(不是那个最右)
    current = current.right
  }
  return current
}

# 最后 remove~!

太麻烦了，懒得解释了

三种情况:

  1. 要删除的节点是最底层节点：直接赋 null
  2. 要删除的节点有一个子节点：直接让该节点的父节点的 left 或者 right 指向这个子节点
  3. 要删除的节点有两个子节点：我没法简述了 看原文

(1) 当找到了要移除的节点后，需要找到它右边子树中最小的节点（它的继承者
(2) 然后，用它右侧子树中最小节点的键去更新这个节点的值。通过这一步，我们改变了这个节点的键，也就是说它被移除了。
(3) 但是，这样在树中就有两个拥有相同键的节点了，这是不行的。要继续把右侧子树中的最小节点移除，毕竟它已经被移至要移除的节点的位置了。
(4) 最后，向它的父节点返回更新后节点的引用。findMinNode 方法的实现和 min 方法的实现方式是一样的。唯一的不同之处在于，在 min 方法中只返回键，而在 findMinNode 中返回了节点。

image-20230303094426335

全部代码… 知道原理就行，真不想写了

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
class Node{
  constructor(key){
    this.key = key
    this.left = null
    this.right = null
  }
}
//封装比较
function compare(key, node) {
  if(node === null) return;
  else if (key > node.key) {
    return 1;
  } else if (key < node.key) {
    return -1;
  } else {
    return 0;
  }
}
class BinarySearchTree{
  constructor(compareFn=compare){
    this.compareFn = compareFn
    this.root = null
  }
  //插入节点的方法
  insertNode(node,key){
    if(this.compareFn(key,node)<0){
      if(node.left===null){
        node.left = new Node(key)
      }else{
        this.insertNode(node.left, key)
      }
    }
    else{
      if(node.right===null){
        node.right = new Node(key)
      }else{
        this.insertNode(node.right, key)
      }
    }
  }
  // 插入key
  insert(key){
    if(this.root===null){
      this.root=new Node(key)
      return true
    }else{
      this.insertNode(this.root,key)
    }
  }
  //搜索节点的方法
  searchNode(node,key){
    if(node === null){
      return false
    }
    if(this.compareFn(key,node)<0){
       return this.searchNode(node.left,key)
    }else if(this.compareFn(key,node)>0){
       return this.searchNode(node.right,key)
    }else{
      return true
    }
  }
  //搜索key
  search(key){
     return this.searchNode(this.root,key)
  }
  //中序遍历节点
  inOrderTraverseNode(node,callback){
    if(node!=null){
      this.inOrderTraverseNode(node.left,callback)
      callback(node.key)
      this.inOrderTraverseNode(node.right,callback)
    }
  }
  //中序遍历
  inOrderTraverse(callback){
    return this.inOrderTraverseNode(this.root,callback)
  }
  //先序遍历节点
  preOrderTraverseNode(node,callback){
    if(node!=null){
      callback(node.key)
      this.preOrderTraverseNode(node.left,callback)
      this.preOrderTraverseNode(node.right,callback)
    }
  }
  //先序遍历
  preOrderTraverse(callback){
    return this.preOrderTraverseNode(this.root,callback)
  }
  //后序遍历节点
  postOrderTraverseNode(node,callback){
     if(node!=null){
      this.postOrderTraverseNode(node.left,callback)
      this.postOrderTraverseNode(node.right,callback)
      callback(node.key)
    }
  }
  //后序遍历
  postOrderTraverse(callback){
    return this.postOrderTraverseNode(this.root,callback)
  }
  //搜索最小值
  min(){
    return this.minNode(this.root).key
  }
  //搜索最小节点
  minNode(node){
    let current = node
    if(current != null && current.left != null){
      current = current.left
    }
    return current
  }
  //搜索最大值
  max(){
    return this.maxNode(this.root).key
  }
  //搜索最大节点
  maxNode(node){
    let current = node
    if(current != null && current.right != null){
      current = current.right
    }
    return current
  }
  //删除节点
  removeNode(node,key){
      if (node == null) { // {2}
        return null;
      }
      if (this.compareFn(key, node.key)<0) { 
        node.left = this.removeNode(node.left, key)
        return node; 
      } else if (this.compareFn(key, node.key)>0) { 
        node.right = this.removeNode(node.right, key)
        return node; 
      } else {
        // 键等于node.key
        // 第一种情况
        if (node.left == null && node.right == null) {
          node = null; 
          return node; 
        }
        // 第二种情况
        if (node.left == null) {
          node = node.right; 
          return node; 
        } else if (node.right == null) { 
          node = node.left; 
          return node;
        }
        // 第三种情况
        const aux = this.minNode(node.right); 
        node.key = aux.key; 
        node.right = this.removeNode(node.right, aux.key); 
        return node; 
      }
    
  }
  //删除方法
  remove(key){
    this.root = this.removeNode(this.root,key)
  }
}

const bst = new BinarySearchTree()
/*
bst.insert(x)
min
max
inOrderTraverse
remove
search
*/

# 最后的最后

有这些基础知识就可以去看看平衡二叉树，红黑树之类

不要把数据结构和算法划等号前端一样需要学数据结构，而且算法也很重要