Python二叉搜索树与双向链表转换实现方法
作者:阿涵-_- 发布时间:2022-08-23 12:46:34
标签:Python,二叉搜索树,双向链表
本文实例讲述了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程序设计有所帮助。
0
投稿
猜你喜欢
- 什么是词干提取?在语言形态学和信息检索里,词干提取是去除词缀得到词根的过程─—得到单词最一般的写法。对于一个词的形态词根,词干并不需要完全相
- 本文实例讲述了php中常量DIRECTORY_SEPARATOR用法。分享给大家供大家参考。具体如下:DIRECTORY_SEPARATOR
- python的numpy 能生成一定概率分布的随机数,但如果需要更具体的概率密度,累积概率,就要使用scipy.stats。scipy.st
- 但是Class这个东西,如果用得比较少,充其量只是一个大模块的包装方式. 只有大规模地用它来开发,才能显出它对项目管理的优越性来. 所谓的意
- PHP str_split() 函数实例把字符串 "Hello" 分割到数组中:<?php print_r(str
- Sys.path 指定用于模块搜索路径的字符串列表也可以通过sys模块的append方法在Python环境中增加搜索路径。Sys.path.
- Software as a service 软件即服务,21世纪开始兴起的一种完全创新的软件应用模式。客户通过互联网向厂商定购所需的应用软件
- python新手一枚,操作系统Win10 64 bit,Python版本,3.7因为某个脚本需要用到win32con 和win32api模块
- 前言python中进行面向对象编程,当在子类的实例中调用父类的属性时,由于子类的__init__方法重写了父类的__init__方法,如果在
- 利用二进制反格雷码(bynary reflected Gray code)的方式生成n个元素的全组合,Cn1+Cn2+...+Cnn,如在利
- sys模块sys模块是与python解释器交互的一个接口sys.argv 命令行参数List,第一个元素是程序本身路径sys.
- 前言:字体反爬是什么个意思?就是网站把自己的重要数据不直接的在源代码中呈现出来,而是通过相应字体的编码,与一个字体文件(一般后缀为ttf或w
- 如果当前绝对定位的元素需要透明(没啥内容、且不设置背景),背景元素有内容透出来的时候,IE6/IE7响应的不是期望的当前元素,而是背景元素。
- 不了解的同学先“点这里”看看什么是Firebug。简单来说,Firebug是Firefox上用来监视、编辑和调试站点的CSS、HTML、DO
- 本文实例讲述了Python实现获取邮箱内容并解析的方法。分享给大家供大家参考,具体如下:# -*- coding: utf-8 -*-fro
- 1.背景项目需求,要求获得github的repo的api,以便可以提取repo的数据进行分析。研究了一天,终于解决了这个问题,虽然效率还是比
- 引言“深入认识Python内建类型”这部分的内容会从源码角度为大家介绍Python中各种常用的内建类
- 推荐的国内镜像站[ 个人推荐清华大学pypi镜像站(https://mirrors.tuna.tsinghua.edu.cn/help/py
- 实例如下所示:import numpy as npimport pandas as pddata = {'city': [&
- # -*- coding: cp936 -*-import socketfrom threading import Thread,activ