二叉搜索树与双向链表(python)

一,问题
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

二,分析

先举个栗子:有如下二叉搜索树,想成为排序的双向链表

我们需要先找到根节点的左孩子,再找到左孩子的最右叶子节点,让这个叶子节点和根节点用指针互指。

代码:

left=pRootOfTree.left

if left:

    while left.right:

        left=left.right

    left.right=pRootOfTree

    pRootOfTree=left

同理,找到根节点右孩子的最左叶子节点,让这个节点和根节点用指针互指

right=pRootOfTree.right

if right:

    while right.left:

        right=right.left

    right.left=pRootOfTree

    pRootOfTree=right

 

然后递归调用,搞定所有的子树

最后找到最左叶子节点(链表头),输出此链表

 

三,完整代码

 

原文地址:https://www.cnblogs.com/buyaodong/p/13182794.html