# 定义二叉搜索树节点类 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 = [321,34,1443,325,532,321,5,35,36,66] 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)将代码中的value从在代码中输入改为让用户输入
时间: 2023-12-31 10:05:03 浏览: 95
定义二叉搜索树类,封装查找、插入、删除操作
5星 · 资源好评率100%
好的,您可以将代码修改如下,让用户输入要插入的节点值:
```
# 定义二叉搜索树节点类
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 = input('请输入要插入的节点值,以空格分隔:').split()
for val in values:
root = insert(root, int(val))
bstree = root
print('Binary Search Tree:')
printTree(bstree, 0)
dllist = treeToDoublyList(bstree)
print('Doubly Linked List:')
printList(dllist)
```
然后,您可以在运行代码时输入要插入的节点值,以空格分隔,比如:
```
请输入要插入的节点值,以空格分隔:5 4 6 1 2
```
这样,程序就会将这些值插入到二叉搜索树中,并将二叉搜索树转换为双向循环链表,最后输出二叉搜索树和双向循环链表的内容。
阅读全文