首页 > Python算法 > Python查找算法
阅读数：51
Python二叉搜索树（二叉查找树）
二叉搜索树是一种特殊的二叉树，树中的元素排列符合二叉搜索树性质。二叉搜索树中，每一个节点存储的元素称作该节点的键值。二叉搜索树也称二叉查找树。
根据这些性质可以推出，插入、删除和查找二叉搜索树操作的时间复杂度都是 O(lgn)。一般来说，二叉搜索树可以用 3 个列表模拟存储，它们分别是 left、right 和 key。这 3 个列表中，下标相同的位置属于同一个节点。编号为 i 的节点的左孩子用 left[i] 表示，右孩子用 right[i] 表示，而键值用 key[i] 表示。
二叉搜索树支持的操作有：
图 1：二叉搜索树的节点
同样，把树的节点定义为一个类：
随后，把二叉搜索树也定义为一个新的类。假设二叉搜索树中的所有元素都以列表的形式输入，我们可以在类内的 init( ) 函数中初始化。
初始化空二叉搜索树的代码如下：
这段代码中，用到了二叉搜索树的插入操作，下面就会讲到。在执行插入操作之前，首先要写出查找操作，即在二叉搜索树中查找是否有键值为 val 的节点。如果有，返回节点的位置；如果没有，返回 0。
图 2：从根节点开始
1) 首先，如图 2 所示，从根节点开始查找。根节点的键值为 9，比我们要查找的键值要大。可以得出，要查找的节点若存在，必定在它的左子树中。所以，要查找的下一个节点就是根节点的左孩子节点。如图 3 所示，进入左子树。
图 3：进入左子树
2) 其次，把当前节点的键值和要查找的键值对比，发现它的键值小于要查找的键值。可以得出，要查找的节点若存在，必定在当前节点的右子树中。
3) 重复类似的步骤，在键值为 5 的节点处同样判定为进入右子树，如图 4 所示。
图 4：找到节点
此时，节点的键值与要查找的键值相等，返回当前位置，查找结束。
4) 最后，我们用键值 18 来做一次查找，这一次 18 不存在于二叉搜索树中。同样，从根节点开始，通过当前节点的键值大小判定，走过键值为 9→14→19→17 的节点，如图 5 所示。
图 5：查找键值 18 的路径
此时，要查找的键值 18 大于当前节点的键值 17。如果要查找的节点存在，那么它必定在当前节点的右子树中。但是，当前节点的右孩子为空，说明不存在右子树，也不存在键值为 18 的节点。返回 0，查找结束。查找的路径如图 5 所示。
下面是查找操作的代码实现，同样作为类内的一个函数：
除简单的查找操作外，我们还可以在二叉搜索树中查找一个数的前驱和后继。在二叉搜索树中， x 的前驱指小于 x 的所有数中最大的数，而后继指大于 x 的所有数中最小的数。同样地，我们用图片来演示查找前驱和后继的过程。
以节点 5 为例，在二叉搜索树中查找它的前驱。
如图 6 所示，在搜索到键值为 5 的节点后，发现节点有左子树。
图 6：搜索到键值为 5 的节点
此时，进入左子树并查找左子树中的最大值。如果左子树中有多个节点，进入左子树后应当不断地往右继续遍历，直到右子树为空。此时，如图 7 所示，键值为5的节点的左子树中只有一个键值为3的节点；此时，该节点的右子树已经为空，那么 5 的前驱就是 3 了。
图 7：找到前驱
我们再以15为例求一次前驱。
1) 如图 8 所示，从根节点开始，查找算法走过了图 12 中最右侧的这一条路径，到达了键值为 15 的节点。
图 8：查找节点 15
而键值为 15 的节点没有左子树，则它的前驱在 9→14→19→17 这一条路径中。所以，在这一条路径经过的节点中，所有键值小于 15 的节点里最大的节点就是 15 的前驱。在这棵二叉搜索树中，15 的前驱是 14。
2) 同理，如果二叉搜索树中不存在搜索 x，那么 x 的前驱仍然在它经过的路径中。假设在同一棵二叉搜索树中搜索 18，会经过图 9 所示这样一条路径。
图 9：查找节点 18
4) 此时，如图 9 所示，查找函数到达一个空节点。在这种情况下，当前节点自然不会有左子树。采用同样的方法，在经过的路径中求得前驱 17 即可。
在二叉搜索树中求前驱的代码如下：
同理，作为 x 后继的数一定大于 x。如果键值为 x 的节点有右子树，x 的后继就是它右子树中键值最小的节点，也就是进入右子树后最左侧的节点。如果键值为 x 的节点没有右子树，那么 x 的后继一定在从根节点到 x 经过的查找路径中。
1) 我们以 14 为例，在图 10 中的二叉搜索树进行后继的查找。
图 10：找到键值为 14 的节点
2) 在开始查找后，很快就找到了键值为 14 的节点，如图 10 所示。此时，进入 14 的右子树，并不断向左搜索，直到当前节点的左子树为空。很快，14 的后继 15 就找到了，如图 11 所示。
图 11：找到后继
3) 当二叉搜索树中没有要查找的值，或查找到的节点没有右子树时，与查找前驱时一样，在路径中找到最小的后继即可。
下面是后继查找的代码实现：
由于查找后继的代码与查找前驱结构基本相同，在此不多做阐述。
1) 如图 12 所示，插入操作同样从根节点开始，根节点上的键值 9 小于 18，说明 18 正确的插入位置应当在节点的右子树中。
图 12：从根节点开始查找
2) 类似地，18 也大于 14，所以仍然进入右子树，如图 13 所示。
图 13：进入右子树
3) 按照这个规律，元素 18 的插入操作沿着 9→14→19→17 的路线一路向下，到达了键值为 17 的节点，如图 14 所示。
图 14：找到插入位置的父亲节点
4) 此时，元素 18 大于 17，应该进入 17 的右子树；但 17 的右指针为空，说明它没有右孩子。这时候，新建一个空节点，把新节点的键值赋值为 18，再让键值为 17 的节点的右指针指向新的节点。插入之后的二叉搜索树如图 15 所示。
图 15：插入节点
这样，节点就插入完成了。如果二叉搜索树中节点的键值没有与要插入的元素重合，那么一定会有这样一个唯一的空位供新节点插入；反之，如果有重合的节点，那么一定会被查找到。这时候，不需要插入，直接 return 退出函数即可。
将插入操作的代码加入类中，具体如下：
在删除二叉搜索树中的节点时，又分为两种情况：
我们仍然用图解的方法来展示删除节点的过程。
1) 首先，以删除键值为17的节点为例。如图 16 所示，在二叉搜索树中搜索到节点17，并且得到判断：当前节点只有左子树。
图 16：找到键值为 17 的节点
此时，直接删除键值为 17 的节点，并使它的左孩子直接与父节点相连。删除节点 17 后的二叉搜索树如图 17 所示。
图 17：删除完毕
2) 接着，举个待删除节点有两个孩子节点的例子。当要删除键值为 5 的节点时，同样先在二叉搜索树中进行搜索，如图 18 所示。
图 18：找到键值为 5 的节点
3) 检测到当前节点有两个孩子节点，这时候，如图 19 所示，在二叉搜索树中查找 5 的后继，得到键值为 8 的节点。
图 19：找到 5 的后继 8
4) 此时，对键值为 8 的节点同样执行二叉搜索树中的删除操作。由于这个节点没有孩子节点，所以直接把这个节点删除即可。图 20 所示为删除后继完毕之后的二叉查找树。
图 20：删除后继完毕
5) 最后，把原来要删除的节点上的键值改为后继的值，如图 21 所示。
图 21：改变要删除节点的键值:
至此，删除操作就完成了。
二叉搜索树中删除操作的代码实现如下：
把实现这些操作的函数都写在类中，就可以组成一棵拥有完整功能的二叉搜索树了。
二叉搜索树基础
二叉搜索树可以是一棵空树，也可以是具有如下几条性质的一棵二叉树：- 若任意一个节点的左子树非空，那么左子树中所有的元素都小于当前节点存储的元素；
- 若任意一个节点的右子树非空，那么右子树中所有的元素都大于当前节点存储的元素；
- 任意一个节点的左右子树也为二叉搜索树；
- 二叉搜索树中没有两个节点有相同的键值。
根据这些性质可以推出，插入、删除和查找二叉搜索树操作的时间复杂度都是 O(lgn)。一般来说，二叉搜索树可以用 3 个列表模拟存储，它们分别是 left、right 和 key。这 3 个列表中，下标相同的位置属于同一个节点。编号为 i 的节点的左孩子用 left[i] 表示，右孩子用 right[i] 表示，而键值用 key[i] 表示。
二叉搜索树支持的操作有：
- 建立二叉搜索树；
- 插入键值为 x 的节点；
- 查询键值为 x 的节点在二叉搜索树中的排名；
- 删除键值为 x 的节点；
- 求键值为 x 的节点的前驱与后继。
二叉搜索树的建立
二叉搜索树的每个节点和二叉树一样，有一个储存节点本身数据的变量，还有两个储存左右孩子的变量，如图 1 所示。图 1：二叉搜索树的节点
同样，把树的节点定义为一个类：
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right= None
随后，把二叉搜索树也定义为一个新的类。假设二叉搜索树中的所有元素都以列表的形式输入，我们可以在类内的 init( ) 函数中初始化。
初始化空二叉搜索树的代码如下：
class BST:
def __init__(self, tlist):
self.root = TreeNode(tlist[0]) #把第一个元素建立为根节点
for i in tlist[1:]: #按顺序把剩下的元素用insert()函数插入二叉搜索树中
self.insert(i)
这段代码中，用到了二叉搜索树的插入操作，下面就会讲到。在执行插入操作之前，首先要写出查找操作，即在二叉搜索树中查找是否有键值为 val 的节点。如果有，返回节点的位置；如果没有，返回 0。
二叉搜索树查找节点
我们用图 2 中这棵二叉搜索树来演示一下查找的过程，以查找键值为 8 的节点为例。图 2：从根节点开始
1) 首先，如图 2 所示，从根节点开始查找。根节点的键值为 9，比我们要查找的键值要大。可以得出，要查找的节点若存在，必定在它的左子树中。所以，要查找的下一个节点就是根节点的左孩子节点。如图 3 所示，进入左子树。
图 3：进入左子树
2) 其次，把当前节点的键值和要查找的键值对比，发现它的键值小于要查找的键值。可以得出，要查找的节点若存在，必定在当前节点的右子树中。
3) 重复类似的步骤，在键值为 5 的节点处同样判定为进入右子树，如图 4 所示。
图 4：找到节点
此时，节点的键值与要查找的键值相等，返回当前位置，查找结束。
4) 最后，我们用键值 18 来做一次查找，这一次 18 不存在于二叉搜索树中。同样，从根节点开始，通过当前节点的键值大小判定，走过键值为 9→14→19→17 的节点，如图 5 所示。
图 5：查找键值 18 的路径
此时，要查找的键值 18 大于当前节点的键值 17。如果要查找的节点存在，那么它必定在当前节点的右子树中。但是，当前节点的右孩子为空，说明不存在右子树，也不存在键值为 18 的节点。返回 0，查找结束。查找的路径如图 5 所示。
下面是查找操作的代码实现，同样作为类内的一个函数：
class BST:
def __init__(self, tlist):
self.root = TreeNode(tlist[0]) #把第一个元素建立为根节点
for i in tlist[1:]: #按顺序把剩下的元素用insert()函数插入二叉搜索树中
self.insert(i)
#查找
def search(self, node, parent, data):
if node is None: #如果当前的位置为空，但仍没有查找到与data相等的元素
return 0, node, parent
elif data == node.data: #查找到了与data相等的元素
return 1, node, parent
elif data < node.data: #data小于当前节点的数据，进入左子树
return self.search(node.left, node, data)
else: #data大于当前节点的数据，进入右子树
return self.search(node.right, node, data)
在这段代码中，无论是否成功查找到 data，都要返回最后的节点 node 和它的父亲节点 parent，用于其他操作中。除简单的查找操作外，我们还可以在二叉搜索树中查找一个数的前驱和后继。在二叉搜索树中， x 的前驱指小于 x 的所有数中最大的数，而后继指大于 x 的所有数中最小的数。同样地，我们用图片来演示查找前驱和后继的过程。
二叉树前驱节点查找
首先我们来看在二叉树中如何查找一个数的前驱。我们知道，作为 x 前驱的数一定是小于 x 的。那么，如果键值为 x 的节点有左子树，x 的前驱就是它左子树中键值最大的节点。如果键值为 x 的节点没有左子树，那么 x 的前驱一定在从根节点到x经过的查找路径中。很显然，查找的过程就是节点的键值向 x 靠近的一个过程。以节点 5 为例，在二叉搜索树中查找它的前驱。
如图 6 所示，在搜索到键值为 5 的节点后，发现节点有左子树。
图 6：搜索到键值为 5 的节点
此时，进入左子树并查找左子树中的最大值。如果左子树中有多个节点，进入左子树后应当不断地往右继续遍历，直到右子树为空。此时，如图 7 所示，键值为5的节点的左子树中只有一个键值为3的节点；此时，该节点的右子树已经为空，那么 5 的前驱就是 3 了。
图 7：找到前驱
1) 如图 8 所示，从根节点开始，查找算法走过了图 12 中最右侧的这一条路径，到达了键值为 15 的节点。
图 8：查找节点 15
而键值为 15 的节点没有左子树，则它的前驱在 9→14→19→17 这一条路径中。所以，在这一条路径经过的节点中，所有键值小于 15 的节点里最大的节点就是 15 的前驱。在这棵二叉搜索树中，15 的前驱是 14。
2) 同理，如果二叉搜索树中不存在搜索 x，那么 x 的前驱仍然在它经过的路径中。假设在同一棵二叉搜索树中搜索 18，会经过图 9 所示这样一条路径。
图 9：查找节点 18
4) 此时，如图 9 所示，查找函数到达一个空节点。在这种情况下，当前节点自然不会有左子树。采用同样的方法，在经过的路径中求得前驱 17 即可。
在二叉搜索树中求前驱的代码如下：
#查找前驱
def getlast(self, node, data，maxn):
if node is None: #如果当前的位置为空，但仍没有查找到与data相等的元素
return 0, maxn #返回目前经过路径上最大的符合前驱要求的数
elif data == node.data: #找到了与data相等的元素
if node.left == None: #值为data的节点没有左子树
return 1, maxn #返回目前经过路径上最大的符合前驱要求的数
else: #值为data的节点有左子树
tmp = node.left #进入左子树后找到左子树中最大的数
while tmp.right is not None:
tmp = tmp.right
return 1, tmp #返回左子树中最大的数（最右边的数）
elif data < node.data: #data小于当前节点的数据，进入左子树
return self.getlast(node.left, data, maxn)
else: #data大于当前节点的数据，进入右子树
If maxn.data < node.data #如果当前数据比已经存储在maxn中的前驱要大，更新maxn
maxn = node
return self.getlast(node.right, data, maxn)
二叉树后继节点查找
查找后继的方法和查找前驱的方法极为类似，只需要改动一些判断条件即可。同理，作为 x 后继的数一定大于 x。如果键值为 x 的节点有右子树，x 的后继就是它右子树中键值最小的节点，也就是进入右子树后最左侧的节点。如果键值为 x 的节点没有右子树，那么 x 的后继一定在从根节点到 x 经过的查找路径中。
1) 我们以 14 为例，在图 10 中的二叉搜索树进行后继的查找。
图 10：找到键值为 14 的节点
2) 在开始查找后，很快就找到了键值为 14 的节点，如图 10 所示。此时，进入 14 的右子树，并不断向左搜索，直到当前节点的左子树为空。很快，14 的后继 15 就找到了，如图 11 所示。
图 11：找到后继
3) 当二叉搜索树中没有要查找的值，或查找到的节点没有右子树时，与查找前驱时一样，在路径中找到最小的后继即可。
下面是后继查找的代码实现：
#查找后继
def getnext(self, node, data，minn):
if node is None: #如果当前的位置为空，但仍没有查找到与data相等的元素
return 0, minn #返回目前经过路径上最小的符合后继要求的数
elif data == node.data: #找到了与data相等的元素
if node.right == None: #值为data的节点没有右子树
return 1, minn #返回目前经过路径上最小的符合后继要求的数
else: #值为data的节点有右子树
tmp = node.right #进入右子树后找到右子树中最小的数
while tmp.left is not None:
tmp = tmp.left
return 1, tmp #返回右子树中最小的数（最左边的数）
elif data < node.data: #data小于当前节点的数据，进入左子树
if minn.data > node.data #如果当前数据比已经存储在minn中的后继要小，更新minn
minn = node
return self.getlast(node.left, data, minn)
else: #data大于当前节点的数据，进入右子树
return self.getlast(node.right, data, minn)
由于查找后继的代码与查找前驱结构基本相同，在此不多做阐述。
二叉搜索树插入节点
而插入操作和查找操作的原理极为相似，使用相同的判定方法，为节点查找到插入的正确位置。我们仍然以同一棵二叉查找树为例，用元素 18 模拟插入的过程。1) 如图 12 所示，插入操作同样从根节点开始，根节点上的键值 9 小于 18，说明 18 正确的插入位置应当在节点的右子树中。
图 12：从根节点开始查找
2) 类似地，18 也大于 14，所以仍然进入右子树，如图 13 所示。
图 13：进入右子树
3) 按照这个规律，元素 18 的插入操作沿着 9→14→19→17 的路线一路向下，到达了键值为 17 的节点，如图 14 所示。
图 14：找到插入位置的父亲节点
4) 此时，元素 18 大于 17，应该进入 17 的右子树；但 17 的右指针为空，说明它没有右孩子。这时候，新建一个空节点，把新节点的键值赋值为 18，再让键值为 17 的节点的右指针指向新的节点。插入之后的二叉搜索树如图 15 所示。
图 15：插入节点
这样，节点就插入完成了。如果二叉搜索树中节点的键值没有与要插入的元素重合，那么一定会有这样一个唯一的空位供新节点插入；反之，如果有重合的节点，那么一定会被查找到。这时候，不需要插入，直接 return 退出函数即可。
将插入操作的代码加入类中，具体如下：
class BST:
#初始化
def __init__(self, tlist):
self.root = TreeNode(tlist[0]) #把第一个元素建立为根节点
for i in tlist[1:]: #按顺序把剩下的元素用insert函数插入二叉搜索树中
self.insert(i)
#查找
def search(self, node, parent, data):
if node is None: #如果当前的位置为空，但仍没有查找到与data相等的元素
return 0, node, parent
elif data == node.data: #找到了与data相等的元素
return 1, node, parent
elif data < node.data: #data小于当前节点的数据，进入左子树
return self.search(node.left, node, data)
else: #data大于当前节点的数据，进入右子树
return self.search(node.right, node, data)
#插入
def insert(self, data):
exist, n, p = self.search(self.root, self.root, data) #接收查找操作的数据
if exist: #如果数据为data的节点已经存在，则不需要执行插入操作，直接返回
return
else: #数据为data的节点不存在
new_node = TreeNode(data) #新建一个节点
if data > p.data: #如果data大于父亲节点，在右孩子的位置上插入
p.right = new_node
else: #如果data小于父亲节点，在左孩子的位置上插入
p.left= new_node
二叉搜索树删除节点
最后要讲到的一种操作是二叉搜索树中的删除操作，效果是删除二叉搜索树中键值为 x 的节点。首先，先查找到键值为 x 的节点，再进行删除操作。在删除二叉搜索树中的节点时，又分为两种情况：
- 键值为 x 的节点的子节点个数小于 2，此时直接删除掉当前节点，并令当前节点的子节点填补上删除后的空位，与父节点相连；
- 键值为 x 的节点有左右子树，此时在二叉搜索树中查找键值x的后继节点 next。此时，next 必然没有左子树，所以直接删除 next，让 next 的右孩子代替 next 原来的位置。随后，再把键值 x 改成 next 的键值。
我们仍然用图解的方法来展示删除节点的过程。
1) 首先，以删除键值为17的节点为例。如图 16 所示，在二叉搜索树中搜索到节点17，并且得到判断：当前节点只有左子树。
图 16：找到键值为 17 的节点
此时，直接删除键值为 17 的节点，并使它的左孩子直接与父节点相连。删除节点 17 后的二叉搜索树如图 17 所示。
图 17：删除完毕
2) 接着，举个待删除节点有两个孩子节点的例子。当要删除键值为 5 的节点时，同样先在二叉搜索树中进行搜索，如图 18 所示。
图 18：找到键值为 5 的节点
3) 检测到当前节点有两个孩子节点，这时候，如图 19 所示，在二叉搜索树中查找 5 的后继，得到键值为 8 的节点。
图 19：找到 5 的后继 8
4) 此时，对键值为 8 的节点同样执行二叉搜索树中的删除操作。由于这个节点没有孩子节点，所以直接把这个节点删除即可。图 20 所示为删除后继完毕之后的二叉查找树。
图 20：删除后继完毕
5) 最后，把原来要删除的节点上的键值改为后继的值，如图 21 所示。
图 21：改变要删除节点的键值:
至此，删除操作就完成了。
二叉搜索树中删除操作的代码实现如下：
#删除操作
def delete(self, root, data):
exist, n, p = self.search(root, root, data)
if not exist: #要删除的数据不存在
print("data does not exist")
else:
if n.left is None: #要删除的节点左子树为空
if n == p.left: #如果n是左孩子，把p的左孩子赋值为n的右孩子
p.left= n.right
else: #如果n是右孩子，把p的右孩子赋值为n的右孩子
p.right= n.right
del n #删除n
elif n.right is None: #要删除的节点右子树为空
if n == p.left: #如果n是左孩子，把p的左孩子赋值为n的左孩子
p.left= n.left
else: #如果n是右孩子，把p的右孩子赋值为n的左孩子
p.right= n.left
del n #删除n
else: # 左右子树均不为空
tmp = n.right #进入n的右子树
if tmp.left is None: #如果n的右孩子没有左子树，则n的右孩子就是n的后继
n.data = tmp.data
n.right = tmp.right
del tmp
else:
next = tmp.left
while next.left is not None: #在右子树中查找n的后继
tmp = next
next = next.left
n.data = next.data
tmp.left= next.right
del next #删除next
把实现这些操作的函数都写在类中，就可以组成一棵拥有完整功能的二叉搜索树了。
