二叉查找树转变为有序双向链表

2019-11-14 17:45:51

字体：大中小

来源：转载

供稿：网友

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

　　比如将二元查找树
                                         10
                                        /    /
                                      6       14
                                    / /     /　 /
                                 4     8 12   16
转换成双向链表

4=6=8=10=12=14=16。

一道微软的面试题。

二叉查找树的每个节点都有两个指针，双向链表的节点也是两个指针，不创建新节点只调整指针是可以完成转变的。

对于二叉查找树的每个节点Node，它的左子树中所有的关键字都小于Node的关键字，而右子树中的所有关键字都大于Node的关键字。

采用递归的思维可以很方便的完成转变，将节点的左右子树分别转变成有序链表，然后将节点的指针分别指向这两个链表。

import randomclass Node(object):    def __init__(self,key):        self.key=key        self.left=None        self.right=Noneclass BSTree(object):    def __init__(self):        self.root=None    def put(self,key):        if not self.root:            self.root=Node(key)        else:            self.root=self._put(self.root,key)    def _put(self,node,key):        if node is None:            node=Node(key)        elif key<node.key:            node.left=self._put(node.left,key)        elif key>node.key:            node.right=self._put(node.right,key)        return node      def convert(self):        if self.root:            return self._convert(self.root)    def _convert(self,node,asright=True):        if not node:            return None        else:            left=self._convert(node.left,False)            if left:                left.right=node                node.left=left            right=self._convert(node.right)            if right:                right.left=node                node.right=right            cur=node            if asright:                while cur.left:                    cur=cur.left            if not asright:                while cur.right:                    cur=cur.right            return cur                            if __name__=='__main__':    t=BSTree()       for i in range(10):        t.put(random.randint(0,100))        cur=t.convert()    if cur:        PRint cur.key        while cur.right:            cur=cur.right            print cur.key        while cur.left:            cur=cur.left            print cur.key

　　另一种思路是采用中序遍历的方法。二叉查找树中序遍历的话就是从小到大排列。将遍历过的节点转为有序链表，然后将下一个要遍历的节点加到链表结尾。

import randomclass Node(object):    def __init__(self,key):        self.key=key        self.left=None        self.right=Noneclass Sorted_LinkedList(object):    def __init__(self):        self.head=None    def travel(self):        node=self.head        while node:            print node.key            node=node.rightclass BSTree(object):    def __init__(self):        self.root=None        self.list=Sorted_LinkedList()        self.curNode=None    def put(self,key):        if not self.root:            self.root=Node(key)        else:            self.root=self._put(self.root,key)    def _put(self,node,key):        if node is None:            node=Node(key)        elif key<node.key:            node.left=self._put(node.left,key)        elif key>node.key:            node.right=self._put(node.right,key)        return node      def convert(self):        self._travel(self.root)        return self.list    def _travel(self,node):        if node:             self._travel(node.left)             if self.curNode:                 self.curNode.right=node                 node.left=self.curNode             else:                 self.list.head=node             self.curNode=node             self._travel(node.right)                        if __name__=='__main__':    t=BSTree()       for i in range(100):        t.put(random.randint(0,100))    l=t.convert()    l.travel()

上一篇：django中“url映射规则”和“服务端响应顺序”

下一篇：python调用外部子进程，通过管道实现异步标准输入和输出的交互