牛客网在线编程专题《剑指offer-面试题27》二叉搜索树与双向链表

Microstrong0305

于 2019-09-06 00:48:05 发布

阅读量302

点赞数 1

分类专栏：算法剑指offer 文章标签：剑指offer 二叉树二叉搜索树双向链表二叉搜索树与双向链表

本文链接：https://blog.csdn.net/program_developer/article/details/100569831

版权

算法同时被 2 个专栏收录

82 篇文章

订阅专栏

剑指offer

46 篇文章

订阅专栏

本文介绍了如何将二叉搜索树转换为排序的双向链表，通过中序遍历的方式，利用递归实现节点间的链接。同时，文章提供了已通过测试的代码实现，包括二叉搜索树的搜索、插入、构建以及双向链表的打印等功能。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

我的个人微信公众号：Microstrong

微信公众号ID：MicrostrongAI

公众号介绍：Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容，分享在学习过程中的读书笔记！期待您的关注，欢迎一起学习交流进步！

知乎专栏：https://zhuanlan.zhihu.com/Microstrong

Github：https://github.com/Microstrong0305

个人博客：https://blog.csdn.net/program_developer

题目链接：

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述：

解题思路：
在二叉树中，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。由于这两种结点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此在理论上有可能实现二叉搜索树和排序的双向链表的转换。在搜索二叉树中，左子结点的值总是小于父结点的值，右子结点的值总是大于父结点的值。因此我们在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点指针。接下来我们考虑该如何转换。

由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每一个结点，这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每一个结点。当遍历到根结点的时候，我们把树看成三部分：值为10的结点、根结点值为6的左子树、根结点值为14的右子树。根据排序链表的定义，值为10的结点将和它的左子树的最大一个结点（即值为8的结点）链接起来，同时它还将和右子树最小的结点（即值为12的结点）链接起来，如图2所示。

注：根结点、左子树和右子树。在把左、右子树都转换成排序的双向链表之后再和根结点链接起来，整棵二又搜索树也就转换成了排序的双向链表。

按照中序遍历的顺序，当我们遍历转换到根结点（值为10的结点）时，它的左子树已经转换成一个排序的链表了，并且处在链表中的最后一个结点是当前值最大的结点。我们把值为8的结点和根结点链接起来，此时链表中的最后一个结点就是10了。接着我们去遍历转换右子树，并把根结点和右子树中最小的结点链接起来。至于怎么去转换它的左子树和右子树，由于遍历和转换过程是一样的，我们很自然地想到可以用递归。

已经AC的代码：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

    def Convert(self, pRootOfTree):
        '''
        :param pRootOfTree: 二叉树的根节点
        :return: 双向链表的头节点
        '''
        # 用于保存处理过程中的双向链表的尾结点
        self.pLastNodeInList = None
        self.ConvertNode(pRootOfTree)

        # pLastNodeInList指向双向链表的尾节点, 我们需要返回头节点
        pHeadOfList = self.pLastNodeInList
        while pHeadOfList != None and pHeadOfList.left != None:
            pHeadOfList = pHeadOfList.left

        return pHeadOfList

    def ConvertNode(self, pNode):
        '''
        :param pNode: 当前的根结点
        :pLastNodeInList: 已经处理好的双向链表的尾结点
        :return:
        '''
        #  结点不为空
        if pNode == None:
            return

        pCurrent = pNode
        # 如果有左子树就先处理左子树
        if pCurrent.left != None:
            self.ConvertNode(pCurrent.left)
        # 将当前结点的前驱指向已经处理好的双向链表（由当前结点的左子树构成）的尾结点
        pCurrent.left = self.pLastNodeInList
        # 如果左子树转换成的双向链表不为空，设置尾结点的后继
        if self.pLastNodeInList != None:
            self.pLastNodeInList.right = pCurrent
        # 记录当前结点为尾结点
        self.pLastNodeInList = pCurrent
        # 处理右子树
        if pCurrent.right != None:
            self.ConvertNode(pCurrent.right)

class Painter:
    def printList(self, head):
        while head != None:
            print(str(head.val) + '->', end='')
            head = head.right

    def printTree(self, root):
        if root != None:
            self.printTree(root.left)
            print(str(root.val) + '->', end='')
            self.printTree(root.right)

if __name__ == "__main__":
    # //            10
    # //         /      \
    # //        6        14
    # //       /\        /\
    # //      4  8     12  16
    node10 = TreeNode(10)
    node6 = TreeNode(6)
    node14 = TreeNode(14)
    node4 = TreeNode(4)
    node8 = TreeNode(8)
    node12 = TreeNode(12)
    node16 = TreeNode(16)
    node10.left = node6
    node10.right = node14
    node6.left = node4
    node6.right = node8
    node14.left = node12
    node14.right = node16
    print("Before convert: ")
    pinter = Painter()
    pinter.printTree(node10)
    print("")
    sol  = Solution()
    head = sol.Convert(node10)
    print("After convert : ")
    pinter.printList(head)
    print()

Reference：

【1】《剑指offer》，何海涛著。

【2】https://wiki.jikexueyuan.com/project/for-offer/question-twenty-seven.html

20200525更新

主要实现功能为：

二叉搜索树的搜索
二叉搜索树的插入
构建二叉搜索树
二叉搜索树转换为排序的双向链表
中序遍历二叉搜索树
从头到尾打印双向链表

已经AC的代码：

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Binary_Sort_Tree:
    def __init__(self, node_list):
        self.root = TreeNode(node_list[0])
        for data in node_list[1:]:
            self.insert(data)

    # 插入
    def insert(self, data):
        flag, n, p = self.SearchBST(self.root, self.root, data)
        if not flag:
            new_node = TreeNode(data)
            if data > p.val:
                p.right = new_node
            else:
                p.left = new_node

    # 搜索
    def SearchBST(self, node, parent, key):
        # 递归结束条件
        if not node:
            return False, node, parent

        if node.val == key:
            return True, node, parent

        if key < node.val:
            return self.SearchBST(node.left, node, key)
        else:
            return self.SearchBST(node.right, node, key)


class Solution:

    def __init__(self):
        # 用于保存处理过程中的双向链表的尾结点
        self.pLastNodeInList = None

    def Convert(self, pRootOfTree):
        self.ConvertNode(pRootOfTree)
        # pLastNodeInList指向双向链表的尾节点, 我们需要返回头节点
        pHeadOfList = self.pLastNodeInList
        while pHeadOfList != None and pHeadOfList.left != None:
            pHeadOfList = pHeadOfList.left

        return pHeadOfList

    def ConvertNode(self, pNode):
        # 结点为空
        if not pNode:
            return None

        pCurrent = pNode
        # 如果有左子树就先处理左子树
        if pCurrent.left != None:
            self.ConvertNode(pCurrent.left)
        # 将当前结点的前驱指向已经处理好的双向链表（由当前结点的左子树构成）的尾结点
        pCurrent.left = self.pLastNodeInList
        # 如果左子树转换成的双向链表不为空，设置尾结点的后继
        if self.pLastNodeInList != None:
            self.pLastNodeInList.right = pCurrent
            # 记录当前结点为尾结点
        self.pLastNodeInList = pCurrent
        # 处理右子树
        if pCurrent.right != None:
            self.ConvertNode(pCurrent.right)


class Painter:
    def printList(self, head):
        while head != None:
            print(str(head.val) + '->', end='')
            head = head.right

    def printTree(self, root):
        if root != None:
            self.printTree(root.left)
            print(str(root.val) + '->', end='')
            self.printTree(root.right)


if __name__ == "__main__":
    # 构建二叉排序树
    tree = [10, 6, 14, 4, 8, 12, 16]
    binarySortTree = Binary_Sort_Tree(tree)

    print("Before convert: 中序遍历二叉排序树")
    pinter = Painter()
    pinter.printTree(binarySortTree.root)

    sol = Solution()
    head = sol.Convert(binarySortTree.root)

    print("\nAfter convert: 打印出排序后的双向链表")
    pinter.printList(head)

Reference：

【1】python实现二叉查找树，地址：https://blog.csdn.net/u010089444/article/details/70854510