代码举例并详细解释用循环方法在二叉搜索树插入一个结点
时间: 2023-06-01 17:05:40 浏览: 104
好的,下面是代码举例并详细解释使用循环方法在二叉搜索树插入一个结点的过程:
```python
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, val):
new_node = Node(val)
if not self.root:
self.root = new_node
return
current_node = self.root
while current_node:
if val < current_node.val:
if current_node.left is None:
current_node.left = new_node
return
current_node = current_node.left
else:
if current_node.right is None:
current_node.right = new_node
return
current_node = current_node.right
```
这里首先定义了节点类 `Node` 和二叉搜索树类 `BinarySearchTree`,然后在 `insert` 方法中实现了在二叉搜索树中插入一个结点的功能。
具体流程如下:
1. 首先创建一个新节点 `new_node`,存储要插入的值;
2. 判断当前二叉搜索树是否为空,如果为空,则将该节点作为树的根节点;
3. 如果树不为空,则从树的根节点开始遍历;
4. 如果 `val` 小于遍历到的当前节点 `current_node` 的值,则向左遍历,如果 `current_node` 的左子树为空,则将 `new_node` 插入到 `current_node` 的左子树中,并返回;
5. 如果 `val` 大于等于遍历到的当前节点 `current_node` 的值,则向右遍历,如果 `current_node` 的右子树为空,则将 `new_node` 插入到 `current_node` 的右子树中,并返回;
6. 如果还没有插入成功,则继续从刚插入的左右子树进行遍历,直到成功插入节点。
这样就可以使用循环方法在二叉搜索树中插入一个结点了。
阅读全文