Python二叉搜索树与双向链表转换实现方法
作者:阿涵-_- 时间:2022-08-23 12:46:34
本文实例讲述了Python二叉搜索树与双向链表实现方法。分享给大家供大家参考,具体如下:
# encoding=utf8
'''
题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点,只能调整树中结点指针的指向。
'''
class BinaryTreeNode():
def __init__(self, value, left = None, right = None):
self.value = value
self.left = left
self.right = right
def create_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)
return node_10
def print_a_tree(root):
if root is None:return
print_a_tree(root.left)
print root.value, ' ',
print_a_tree(root.right)
def print_a_linked_list(head):
print 'linked_list:'
while head is not None:
print head.value, ' ',
head = head.right
print ''
def create_linked_list(root):
'''构造树的双向链表,返回这个双向链表的最左结点和最右结点的指针'''
if root is None:
return (None, None)
# 递归构造出左子树的双向链表
(l_1, r_1) = create_linked_list(root.left)
left_most = l_1 if l_1 is not None else root
(l_2, r_2) = create_linked_list(root.right)
right_most = r_2 if r_2 is not None else root
# 将整理好的左右子树和root连接起来
root.left = r_1
if r_1 is not None:r_1.right = root
root.right = l_2
if l_2 is not None: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,二叉搜索树,双向链表
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
django的auth认证,authenticate和装饰器功能详解
2021-10-06 00:34:51
![](https://img.aspxhome.com/file/2023/8/91998_0s.png)
构建成功web应用的十项黄金法则
2010-09-17 19:11:00
![](https://img.aspxhome.com/file/UploadPic/20109/17/01-99s.jpg)
SQL Server 数据库操作实用技巧锦集
2009-01-20 13:20:00
安装MySQL5.0后出现1607异常的解决办法
2009-02-26 15:52:00
ASP编写计数器的优化方法
2009-01-21 19:46:00
python计算n的阶乘的方法代码
2023-08-20 07:33:00
Python求导数的方法
2023-11-22 07:51:15
Google谷歌农历鼠年春节的变化
2008-02-11 17:07:00
![](https://img.aspxhome.com/file/UploadPic/20082/11/200821117922974s.png)
ASP用户登录验证代码
2008-05-15 12:49:00
asp如何编写翻页函数?
2009-11-07 18:46:00
解决python3 HTMLTestRunner测试报告中文乱码的问题
2021-10-19 04:34:06
牢不可破的九宫格布局
2009-07-24 12:40:00
![](https://img.aspxhome.com/file/UploadPic/20097/24/jiougongge1-43s.gif)
python实现根据窗口标题调用窗口的方法
2022-06-12 04:24:40
对Server.UrlEncode进行字符反编译
2009-06-22 12:54:00
如何把IP表存到SQL数据库里去?
2009-11-02 20:21:00
PHP闭包定义与使用简单示例
2023-11-23 03:12:15
PHP常量及变量区别原理详解
2023-09-05 06:35:45
![](https://img.aspxhome.com/file/2023/2/55612_0s.png)
SQL存储过程初探
2009-09-09 14:22:00
![](https://img.aspxhome.com/file/UploadPic/20099/9/cccr-25s.jpg)
xmlhttp中运行getResponseHeader出错,提示:The requested header was not found
2010-03-27 21:47:00
Python字符串的15个基本操作(小结)
2023-08-11 00:11:13