Python二叉搜索树与双向链表转换算法示例
本文实例讲述了Python二叉搜索树与双向链表转换算法。分享给大家供大家参考，具体如下：
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
普通的二叉树也可以转换成双向链表，只不过不是排序的
思路：
1.与中序遍历相同
2.采用递归，先链接左指针，再链接右指针
代码1，更改doubleLinkedList，最后返回list的第一个元素：
classTreeNode: def__init__(self,x): self.val=x self.left=None self.right=None classSolution: deflastElem(self,list): iflen(list)==0: returnNone else:returnlist[len(list)-1] defConvertCore(self,pRoot,doubleLinkedList): ifpRoot: ifpRoot.left: self.ConvertCore(pRoot.left,doubleLinkedList) pRoot.left=self.lastElem(doubleLinkedList) ifself.lastElem(doubleLinkedList): self.lastElem(doubleLinkedList).right=pRoot doubleLinkedList.append(pRoot) ifpRoot.right: self.ConvertCore(pRoot.right,doubleLinkedList) defConvert(self,pRootOfTree): ifpRootOfTree==None: returnNone doubleLinkedList=[] self.ConvertCore(pRootOfTree,doubleLinkedList) returndoubleLinkedList[0]
代码2，lastListNode指向双向链表中的最后一个节点，因此每次操作最后一个节点。这里要更改值，因此采用list的形式。
classTreeNode: def__init__(self,x): self.val=x self.left=None self.right=None classSolution: defConvertCore(self,pRoot,lastListNode): ifpRoot: ifpRoot.left: self.ConvertCore(pRoot.left,lastListNode) pRoot.left=lastListNode[0] iflastListNode[0]: lastListNode[0].right=pRoot lastListNode[0]=pRoot ifpRoot.right: self.ConvertCore(pRoot.right,lastListNode) defConvert(self,pRootOfTree): #writecodehere ifpRootOfTree==None: returnNone lastListNode=[None] self.ConvertCore(pRootOfTree,lastListNode) whilelastListNode[0].left: lastListNode[0]=lastListNode[0].left returnlastListNode[0]
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。