python 创建一个菜单依次调用下面内容(1)打印二叉搜索树 (2)遍历二叉搜索树 (3)打印转换后的双链表 (4)以正的顺序和反向的顺序输出双链表中的所有元素
时间: 2023-12-09 13:05:40 浏览: 79
Python二叉搜索树与双向链表转换算法示例
好的,下面是一个简单的 Python 代码,可以创建一个菜单,依次调用下面内容:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BSTtoDLL:
def __init__(self):
self.head = None
self.prev = None
def binaryTreeToDLL(self, root):
if root is None:
return
self.binaryTreeToDLL(root.left)
if self.prev is None:
self.head = root
else:
root.left = self.prev
self.prev.right = root
self.prev = root
self.binaryTreeToDLL(root.right)
def printBST(self, root):
if root is None:
return
self.printBST(root.left)
print(root.val, end=" ")
self.printBST(root.right)
def printDLL(self, head):
if head is None:
return
while head.right:
print(head.val, end=" ")
head = head.right
print(head.val, end=" ")
print()
while head:
print(head.val, end=" ")
head = head.left
if __name__ == '__main__':
bst_to_dll = BSTtoDLL()
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
while True:
print("请选择以下操作:")
print("1. 打印二叉搜索树")
print("2. 遍历二叉搜索树")
print("3. 打印转换后的双链表")
print("4. 以正的顺序和反向的顺序输出双链表中的所有元素")
print("0. 退出程序")
choice = int(input())
if choice == 0:
break
elif choice == 1:
bst_to_dll.printBST(root)
print()
elif choice == 2:
bst_to_dll.binaryTreeToDLL(root)
bst_to_dll.printDLL(bst_to_dll.head)
elif choice == 3:
bst_to_dll.binaryTreeToDLL(root)
bst_to_dll.printDLL(bst_to_dll.head)
elif choice == 4:
bst_to_dll.binaryTreeToDLL(root)
bst_to_dll.printDLL(bst_to_dll.head)
```
这个程序创建了一个 `TreeNode` 类,以表示二叉搜索树中的节点。`BSTtoDLL` 类实现了三个方法,分别是 `binaryTreeToDLL`、`printBST` 和 `printDLL`。`binaryTreeToDLL` 方法将二叉搜索树转换成双链表,`printBST` 方法打印二叉搜索树,`printDLL` 方法打印双链表。在程序的主函数中,使用一个无限循环,让用户选择要执行的操作。根据用户的选择,调用相应的方法。
阅读全文