为二叉搜索树节点定义一个类,该类具有三个属性:值、左和右。 实现一个函数以将节点插入二叉搜索树中。您可以使用递归来执行此操作。 实现一个函数来按顺序遍历二叉搜索树。这将为您提供节点值的排序列表。 实现一个函数,将二叉搜索树转换为循环双向链表。您可以使用上一步中的节点值的排序列表来执行此操作。 实现一个函数来打印二叉搜索树。您可以使用递归以可读格式打印树。 实现一个函数,以正顺序和反向顺序打印转换后的双向链表。您可以在两个方向上遍历列表来执行此操作。最后打印BStree和双向链表的图示
时间: 2024-02-12 10:03:39 浏览: 85
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
好的,我会根据您的要求来提供答案。下面是代码实现和图示:
```python
# 定义二叉搜索树节点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 插入节点
def insert(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
# 顺序遍历二叉搜索树
def inorderTraversal(root):
res = []
if not root:
return res
res += inorderTraversal(root.left)
res.append(root.val)
res += inorderTraversal(root.right)
return res
# 将二叉搜索树转换为双向循环链表
def treeToDoublyList(root):
if not root:
return None
inorder = inorderTraversal(root)
head = cur = TreeNode(None)
for val in inorder:
cur.right = TreeNode(val)
cur.right.left = cur
cur = cur.right
head.right.left = cur
cur.right = head.right
return head.right
# 打印二叉搜索树
def printTree(root, space):
if not root:
return
space += 5
printTree(root.right, space)
print(' ' * space, root.val)
printTree(root.left, space)
# 打印双向循环链表
def printList(head):
if not head:
return
print(head.val, end=' ')
cur = head.right
while cur != head:
print(cur.val, end=' ')
cur = cur.right
print()
# 测试
if __name__ == '__main__':
root = None
values = [4, 2, 5, 1, 3]
for val in values:
root = insert(root, val)
bstree = root
print('Binary Search Tree:')
printTree(bstree, 0)
dllist = treeToDoublyList(bstree)
print('Doubly Linked List:')
printList(dllist)
```
图示:
```
Binary Search Tree:
5
4
3
2
1
Doubly Linked List:
1 2 3 4 5
```
阅读全文