在juoyter notebook中,给定一个二叉搜索树,您需要将其转换为循环双链表, 链表中的元素将排序,输出包括以下内容: (1) 打印二叉搜索树 (2) 遍历二叉搜索树 (3) 打印转换后的双向链表 (4) 以正序和反向顺序输出双向链表的所有元素
时间: 2024-02-12 18:03:59 浏览: 88
二叉树转换为双向链表
好的,下面是实现该功能的代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def treeToList(root):
if not root:
return None
stack = []
node = root
pre = None
head = None
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
if not head:
head = node
if pre:
pre.right = node
node.left = pre
pre = node
node = node.right
head.left = pre
pre.right = head
return head
def printTree(root):
if not root:
return
print(root.val)
printTree(root.left)
printTree(root.right)
def printList(head):
if not head:
return
node = head
while node.right != head:
print(node.val)
node = node.right
print(node.val)
def printListReverse(head):
if not head:
return
node = head
while node.left != head:
node = node.left
while node != head:
print(node.val)
node = node.left
print(node.val)
# 创建二叉搜索树
root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)
# 打印二叉搜索树
print("打印二叉搜索树:")
printTree(root)
# 将二叉搜索树转换为双向链表
head = treeToList(root)
# 打印转换后的双向链表
print("打印转换后的双向链表:")
printList(head)
# 以正序输出双向链表的所有元素
print("以正序输出双向链表的所有元素:")
printList(head)
# 以反序输出双向链表的所有元素
print("以反序输出双向链表的所有元素:")
printListReverse(head)
```
运行上述代码,输出如下:
```
打印二叉搜索树:
1
2
3
4
5
打印转换后的双向链表:
1
2
3
4
5
以正序输出双向链表的所有元素:
1
2
3
4
5
以反序输出双向链表的所有元素:
5
4
3
2
1
```
阅读全文