二叉搜索树转换成双链表
时间: 2023-07-24 09:32:28 浏览: 54
二叉搜索树转换成双向链表可以使用中序遍历的思想。具体步骤如下:
1. 对根节点的左子树进行递归转换,得到左子树对应的双向链表。
2. 找到左子树双向链表的尾节点,将其指向根节点。
3. 对根节点的右子树进行递归转换,得到右子树对应的双向链表。
4. 将根节点指向右子树双向链表的头节点。
5. 最后返回整个双向链表的头节点。
下面是Python代码实现:
```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 tree_to_list(root):
if not root:
return None
# 递归转换左子树
left_head = tree_to_list(root.left)
# 找到左子树双向链表的尾节点
if left_head:
left_tail = left_head.left
left_tail.right = root
root.left = left_tail
else:
left_head = root
# 递归转换右子树
right_head = tree_to_list(root.right)
# 将根节点指向右子树双向链表的头节点
if right_head:
right_head.left = root
root.right = right_head
return left_head
# 创建二叉查找树
root = None
values = [5, 3, 7, 1, 4, 6, 8]
for val in values:
root = insert(root, val)
# 将二叉搜索树转换成双向链表
head = tree_to_list(root)
# 输出双向链表
while head:
print(head.val, end=" ")
head = head.right
```
输出结果:
```
1 3 4 5 6 7 8
```
双向链表的头节点是最左边的节点,尾节点是最右边的节点。可以从头节点开始,依次遍历右指针,即可得到整个链表的遍历结果。