Python二叉搜索树与双向链表转换实现方法
本文实例讲述了Python二叉搜索树与双向链表实现方法。分享给大家供大家参考，具体如下：
#encoding=utf8 ''' 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点，只能调整树中结点指针的指向。 ''' classBinaryTreeNode(): def__init__(self,value,left=None,right=None): self.value=value self.left=left self.right=right defcreate_a_tree(): node_4=BinaryTreeNode(4) node_8=BinaryTreeNode(8) node_6=BinaryTreeNode(6,node_4,node_8) node_12=BinaryTreeNode(12) node_16=BinaryTreeNode(16) node_14=BinaryTreeNode(14,node_12,node_16) node_10=BinaryTreeNode(10,node_6,node_14) returnnode_10 defprint_a_tree(root): ifrootisNone:return print_a_tree(root.left) printroot.value,'', print_a_tree(root.right) defprint_a_linked_list(head): print'linked_list:' whileheadisnotNone: printhead.value,'', head=head.right print'' defcreate_linked_list(root): '''构造树的双向链表，返回这个双向链表的最左结点和最右结点的指针''' ifrootisNone: return(None,None) #递归构造出左子树的双向链表 (l_1,r_1)=create_linked_list(root.left) left_most=l_1ifl_1isnotNoneelseroot (l_2,r_2)=create_linked_list(root.right) right_most=r_2ifr_2isnotNoneelseroot #将整理好的左右子树和root连接起来 root.left=r_1 ifr_1isnotNone:r_1.right=root root.right=l_2 ifl_2isnotNone:l_2.left=root #由于是双向链表，返回给上层最左边的结点和最右边的结点指针 return(left_most,right_most) if__name__=='__main__': tree_1=create_a_tree() print_a_tree(tree_1) (left_most,right_most)=create_linked_list(tree_1) print_a_linked_list(left_most) pass
更多关于Python相关内容可查看本站专题：《Python正则表达式用法总结》、《Python数据结构与算法教程》、《PythonSocket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。