摘要：二叉搜索树不一定是完全二叉树，因此不能像堆一样可以数组表示。在当前为根节点的子树中，查找为的节点。否则递归地到左右子树中找到为的节点，并更新。当当前节点有左孩子时，获得左子树中最小的节点。以上是我所了解的二叉搜索树的基本功能
二叉查找树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
二叉搜索树不一定是完全二叉树，因此不能像堆一样可以数组表示。
定义一个TNode类来实例化节点，有key,value,l_child,r_child属性。其中key,value通过构造函数传入，l_child,r_child初始化为None。
再定义一个BSTree类，根节点初始化为None。
然后给BSTree添加以下方法：
insert(key,value) 插入一个节点
update(key,value) 更新节点的值
search(key) 通过key来找相应节点的value
remove(key) 通过key来删除树中相应节点
以及深度优先和广度优先的遍历方法。
insert:
传入参数key,value，插入一个新的节点。但是如果树中已经存在key为key的节点，就将插入操作转变为更新操作。
def __insert(self, key, value, curr_node):
if curr_node is None:
return TNode(key, value)
if key < curr_node.key:
curr_node.l_child = self.__insert(key, value, curr_node.l_child)
elif key > curr_node.key:
curr_node.r_child = self.__insert(key, value, curr_node.r_child)
else:
curr_node.value = value
return curr_node
当当前的节点为None时，根据参数中的key和value建立新的节点，并返回这个节点。当key值小于当前节点的key时，将新节点插入到当前节点的左子树的相应位置，然后返回当前节点。同理key值大于当前节点的key时，将新节点插入到当前节点的右子树的相应位置，返回当前节点。如果key等于当前节点key，将插入操作改变为更新操作。
search:
def __search(self, node, key):
if node:
if node.key == key:
return node
elif node.key > key:
return self.__search(node.l_child, key)
else:
return self.__search(node.r_child, key)
return False
在当前node为根节点的子树中，查找key为key的子节点，如果当前node的key值与参数相同，返回当前节点。否则递归地到左右子树中找key为key的节点，如果没有找到，最终返回False。
update:
def __update(self, key, value, node):
if node:
if node.key == key:
node.value = value
elif node.key > key:
self.__update(key, value, node.l_child)
else:
self.__update(key, value, node.r_child)
在当前node为根节点的子树中，查找key为key的节点。如果当前node的key值与参数相同，更新当前节点的value。否则递归地到左右子树中找到key为key的节点，并更新value。
remove:
执行remove操作时，分为两种情况。
1.当前要删除的节点没有右子节点，此时将左子节点作为当前节点，返回。
2.当前要删除的节点(node_to_delete)有右子节点(r_child)，找到右子节点下，最小的节点(r_child_smallest_child)，将该节点与要删除的节点换位置。具体操作为：先拿到r_child_smallest_child，再将该节点从以r_child为根的子树中删除。再将node_to_delete的左孩子作为r_child_smallest_child的左孩子，node_to_delete的右孩子作为r_child_smallest_child的右孩子。最终将r_child_smallest_child赋给node_to_delete，并返回。
代码如下：
def __remove(self, node, key):
if node:
if node.key < key:
node.r_child = self.__remove(node.r_child, key)
elif node.key > key:
node.l_child = self.__remove(node.l_child, key)
else:
if node.r_child is None:
node = node.l_child
else:
node_r_child_smallest_child = self.__get_smallest_child(node.r_child)
self.__remove_smallest(node.r_child)
node_r_child_smallest_child.r_child = node.r_child
node_r_child_smallest_child.l_child = node.l_child
node = node_r_child_smallest_child
return node
return False
其中__remove_smallest和__get_smallest_child含义分别是：删除当前节点下，最小的节点，以及获得当前节点下最小的节点。
代码如下：
def __remove_smallest(self, node):
if node.l_child:
node.l_child = self.__remove_smallest(node.l_child)
return node
return node.r_child
当当前节点有左孩子时，删除左子树中最小的节点，并且返回当前节点。没有左孩子时，返回右孩子。
def __get_smallest_child(self, node):
if node.l_child:
return self.__get_smallest_child(node.l_child)
return node
当当前节点有左孩子时，获得左子树中最小的节点。没有左孩子时，返回当前节点。
深度优先遍历，可以选择先序遍历，中序遍历，后续遍历，以其中之一为例：
def __l_m_r(self, node):
if node:
self.__l_m_r(node.l_child)
print(node)
self.__l_m_r(node.r_child)
当进行广度优先遍历时，需要用到队列。
def bfs(self):
queue = deque()
queue.append(self.root)
while queue:
node = queue.popleft()
if node:
l_child = node.l_child
r_child = node.r_child
print(node.value)
queue.append(l_child)
queue.append(r_child)
以上是我所了解的二叉搜索树的基本功能
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/44613.html
摘要：图展示了二叉搜索树的这一特性，显示的键没有关联任何的值。因为我们必须能够创建和使用一个空的二叉搜索树，所以我们将使用两个类来实现，第一个类我们称之为，第二个类我们称之为。图说明了将新节点插入到一个二叉搜索树的过程。 二叉搜索树 我们已经知道了在一个集合中获取键值对的两种不同的方法。回忆一下这些集合是如何实现ADT（抽象数据类型）MAP的。我们讨论两种ADT MAP的实现方式，基于列表的...
摘要：现在对我们来说首要的问题是从二叉搜索树中删除一个节点。搜索树分析通过二叉搜索树实现的完成，我们将对我们已经实现的方法进行一个快速的分析。对它的执行效果造成限制的是二叉树的高度。当表示树的高度时，一个满二叉树中节点的总数是。 搜索树实现（续） 最后，我们把注意力转向二叉搜索树中最具挑战性的方法，删除一个键值（参见Listing 7）。首要任务是要找到搜索树中要删除的节点。如果树有一个以上...
摘要：我们知道，当树变得不平衡时和操作会使二叉搜索树的性能降低到。树实现抽象数据类型就像一个普通的二叉搜索树，唯一不同的是这棵树的工作方式。我们通过比较每个节点的左右子树的高度完成比较。 平衡二叉搜索树 在上一节中我们讨论了建立一个二叉搜索树。我们知道，当树变得不平衡时get和put操作会使二叉搜索树的性能降低到O(n)。在这一节中我们将看到一种特殊的二叉搜索树，它可以自动进行调整，以确保树...
阅读 917·2021-11-24 09:39
阅读 3313·2021-10-27 14:20
阅读 2301·2019-08-30 14:08
阅读 3320·2019-08-29 16:34
阅读 2146·2019-08-26 12:14
阅读 2083·2019-08-26 11:54
阅读 2754·2019-08-26 11:44
阅读 2451·2019-08-26 11:38
