任意给定一组数据,设计一个算法,建立一棵二叉排序树,对它进行查找、插入、删除等操作的代码实现
时间: 2024-02-20 19:00:30 浏览: 94
任给一组数,利用二叉树进行排序,查询,插入,删除操作。
好的,我会根据您的要求,为您介绍如何建立一棵二叉排序树,并提供相应的代码实现。
1. 二叉排序树的定义
二叉排序树(Binary Search Tree)也称二叉查找树、二叉搜索树,是一种特殊的二叉树。其特点是:对于每个节点,左子树上所有节点的值都小于这个节点的值,右子树上所有节点的值都大于这个节点的值。因此,二叉排序树的中序遍历是一个有序序列。
2. 二叉排序树的建立
二叉排序树的建立过程是:从根节点开始,将每一个节点插入到合适的位置上。具体步骤如下:
(1)如果树为空,插入的节点作为根节点。
(2)如果插入的节点值小于根节点,将其插入到左子树中。
(3)如果插入的节点值大于根节点,将其插入到右子树中。
(4)如果插入的节点值等于根节点,不进行插入。
下面是建立二叉排序树的代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
curr = self.root
while True:
if val < curr.val:
if curr.left:
curr = curr.left
else:
curr.left = TreeNode(val)
return
elif val > curr.val:
if curr.right:
curr = curr.right
else:
curr.right = TreeNode(val)
return
else:
return
```
3. 二叉排序树的查找
二叉排序树的查找过程是:从根节点开始,比较查找值与当前节点的值的大小关系,如果相等,则返回当前节点;否则,根据大小关系进入左子树或右子树继续查找。具体步骤如下:
(1)如果树为空,则查找失败。
(2)如果查找值等于根节点的值,则查找成功。
(3)如果查找值小于根节点的值,则在左子树中查找。
(4)如果查找值大于根节点的值,则在右子树中查找。
下面是查找二叉排序树的代码实现:
```python
class BST:
def __init__(self):
self.root = None
def insert(self, val):
# 略去插入代码
def search(self, val):
curr = self.root
while curr:
if val == curr.val:
return curr
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return None
```
4. 二叉排序树的删除
二叉排序树的删除过程比较复杂,需要考虑到三种情况:
(1)待删除节点没有子节点,直接删除即可。
(2)待删除节点只有一个子节点,将子节点移动到待删除节点的位置上。
(3)待删除节点有两个子节点,需要找到其右子树中的最小节点或左子树中的最大节点,将其替换待删除节点的值,并删除该最小节点或最大节点。
下面是删除二叉排序树的代码实现:
```python
class BST:
def __init__(self):
self.root = None
def insert(self, val):
# 略去插入代码
def search(self, val):
# 略去查找代码
def delete(self, val):
node = self.search(val)
if not node:
return False
if not node.left and not node.right:
if node == self.root:
self.root = None
else:
parent = self._find_parent(node)
if parent.left == node:
parent.left = None
else:
parent.right = None
elif node.left and not node.right:
if node == self.root:
self.root = node.left
else:
parent = self._find_parent(node)
if parent.left == node:
parent.left = node.left
else:
parent.right = node.left
elif not node.left and node.right:
if node == self.root:
self.root = node.right
else:
parent = self._find_parent(node)
if parent.left == node:
parent.left = node.right
else:
parent.right = node.right
else:
min_node = node.right
while min_node.left:
min_node = min_node.left
node.val = min_node.val
parent = self._find_parent(min_node)
if parent.left == min_node:
parent.left = None
else:
parent.right = None
return True
def _find_parent(self, node):
curr = self.root
parent = None
while curr:
if curr == node:
return parent
elif node.val < curr.val:
parent = curr
curr = curr.left
else:
parent = curr
curr = curr.right
return None
```
以上就是二叉排序树的建立、查找、删除的代码实现。希望对您有所帮助。
阅读全文