本文主要使用python实现二叉查找树的如下部分：
- 二叉查找树构造
- 二叉查找树插入
- 二叉查找树遍历
- 二叉查找树删除
二叉查找树是一颗二叉树，并且基本数据结构要求满足如下条件：
- 所有左接点的值均小于它的根结点
- 所有的右接点值均大于它的根结点
- 所有的左右子树均是二叉查找树（每个接点都大于它左侧子树的任意接点，并小于右侧子树的任意接点）
来个栗子:
二叉查找树的构造：
我们想来构造一个树，我们需要3个变量：
- 左节点
- 右节点
- 根节点数据
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Node: """ Tree node: left and right child + data which can be any object """ def __init__(self, data): """ Node constructor @param data node data object """ self.left = None self.right = None self.data = data |
让我们来创建一个值为8的根结点，这个时候，左右节点均是None
root = Node(8) |
如下图看到的，我们创建了一个只有一个节点的树
插入方法
我们需要一个方法来插入元素让我们的单个节点的树变的充实起来，这个方法的参数是个数值和某个节点本身（根节点/二叉查找树）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Node: ... def insert(self, data): """ Insert new node with data @param data node data object to insert """ if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data |
插入方法会递归的调用，直到为我们的元素（节点）找到合适的位置
.
让我们来增加3个元素（节点），然后看看我们的插入方法是如何运行的
1 |
root.insert(3) |
2 |
root.insert(10) |
3 |
root.insert(1) |
插入元素3（节点）的过程:
- 第一步： 根结点调用插入方法，调用时传入的变量为3
- 第二步：3比8小，而且 根节点8的左节点为None，所以我们直接把3这个节点（3的左右节点均为None）,放到8的左节点上
插入元素10（节点）的过程:
- 根节点调用insert方法，传入变量10
- 10大于根节点，并且根节点的右分支为None,所以我们把10放到根节点的右分支
插入元素1（节点）的过程:
- 根节点调用insert方法，传入参数1
- 1比8小，并且8这个根结点有左侧分值（不为None）,所以，根结点的左节点调用insert方法，传入参数1
- 这个时候，1比3小，并且3没有左分支，我们就把1放到了3的左节点上
现在的结构是:
让我们继续插入新的元素让树更加充实.
1 |
root.insert(6) |
2 |
root.insert(4) |
3 |
root.insert(7) |
4 |
root.insert(14) |
5 |
root.insert(13) |
插入完成后的栗子:
遍历
我们需要一个方法能够帮助我们找到具体的某一个节点，这个方法会接收一个数值，返回这个数值所在的节点，并返回它的父节点（如果不寸再就返回None）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Node: ... def lookup(self, data, parent=None): """ Lookup node containing data @param data node data object to look up @param parent node's parent @returns node and node's parent if found or None, None """ if data < self.data: if self.left is None: return None, None return self.left.lookup(data, self) elif data > self.data: if self.right is None: return None, None return self.right.lookup(data, self) else: return self, parent |
我们试着查找下6
1 |
node, parent = root.lookup(6) |
具体的查找过程:
- 第一步： 传入参数6，默认的parent = None
- 第二步：6 小于根节点的8
- 第三步：这个时候，根结点的左节点3，继续调用lookup函数，这个时候的parent就是当前的节点了
- 第四步：6比3大
- 第五步：然后3的右节点（孩子），调用lookup
- 第六步：发现6等于3的右孩子，找到了！
删除方法
删除方法需要传入的参数就是一个节点的值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Node: ... def delete(self, data): """ Delete node containing data @param data node's content to delete """ # get node containing data node, parent = self.lookup(data) if node is not None: children_count = node.children_count() ... |
删除的时候有三种情况：
- 1：被删除的节点没有子节点
- 2：被删除的节点有一个子节点.
- 3：被删除的节点有2个子节点
第一种情况是非常简单的，我只需要将这个节点删除，然后将它的父节点相应的子节点置为None即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
def delete(self, data): ... if children_count == 0: # if node has no children, just remove it if parent: if parent.left is node: parent.left = None else: parent.right = None del node else: self.data = None ... |
注：方法children_count()会返回一个节点的子节点的个数
children_count:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Node: ... def children_count(self): """ Returns the number of children @returns number of children: 0, 1, 2 """ cnt = 0 if self.left: cnt += 1 if self.right: cnt += 1 return cnt |
举个例子，我们想删除节点1，3的左分支会被设置成None
1 |
root.delete(1) |
让我们来看一下第二种情况，这个时候，我们需要用它的子节点来代替被删除的节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def delete(self, data): ... elif children_count == 1: # if node has 1 child # replace node with its child if node.left: n = node.left else: n = node.right if parent: if parent.left is node: parent.left = n else: parent.right = n del node else: self.left = n.left self.right = n.right self.data = n.data ... |
举个例子，我们想删除节点14，这个时候，13会代替14，然后新的13的左右分支会被置为None
1 |
root.delete(14) |
让我们来看一下最后一种可能，就是被删除节点有两个子节点，我们会用其中一个来代被删除的节点，并递归的完成这个过程
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def delete(self, data): ... else: # if node has 2 children # find its successor parent = node successor = node.right while successor.left: parent = successor successor = successor.left # replace node data by its successor data node.data = successor.data # fix successor's parent's child if parent.left == successor: parent.left = successor.right else: parent.right = successor.right |
举例子：我们想要删除3，这个时候我们会递归的去查找右测元素，终于找到4，我们将4替换3，然后将6的子节点值None
1 |
root.delete(3) |
参考地址： http://www.laurentluce.com/posts/binary-search-tree-library-in-python/comment-page-1/
Latest posts by Zhiming Zhang (see all)
- aws eks node 自动化扩展工具 Karpenter - 8月 10, 2022
- ReplicationController and ReplicaSet in Kubernetes - 12月 20, 2021
- public key fingerprint - 5月 27, 2021
微博抽奖活动汇总 2019/05/30 11:47
目前正在学pthon，有问题还请博主多多指教！