美文网首页Python
python-025-把二叉树转换为双向链表

python-025-把二叉树转换为双向链表

作者: DKider | 来源:发表于2019-03-26 20:36 被阅读17次

题目:给定一个二叉树,将其转换为双向链表。


双向链表的特征是每一个节点都保存着其前驱节点和后继节点的地址,而二叉树是一样的结构,只不过是左右孩子的节点的地址,所以我们只需要将左孩子节点指针作为前驱节点指针,右孩子节点指针作为后继节点指针即可。

非常明显我们又要利用递归了,这题还有其他解法,这里就不多说了。

双向链表有两个头节点,一个Phead,一个Pend,如何在转换二叉树时如何保存这个双向链表的前后头结点,是一个难题,可以写一个双向链表对象,其属性为self.phead,和self.pend,然后将转变二叉树作为它的一个方法。
当然也可以用函数式编程,将这两个指针在函数内声明为全局变量即可。

具体思路,用中序遍历算法改编,(很多对二叉树的算法都是用三种遍历方式改编来的

遍历每一个节点时,改变其指针指向:

pend.right_child = root
root.left_child = pend

pend = root

上面的过程即可使节点加入到双向链表的尾部。

代码实现:

def BiTreeToDLink(root):
    global pHead
    global pEnd
    if root is None:
        return
    #左子树
    BiTreeToDLink(root.left_child)
    #根节点的左孩子指向pEnd,pEnd的有孩子指向root
    root.left_child=pEnd
    if None == pEnd:
        pHead=root
    else:
        pEnd.right_child = root
    #右子树
    pEnd=root
    BiTreeToDLink(root.right_child)

运行:

if __name__ == '__main__':
    root=constuctBiTree(12)
    print("中序遍历:")
    print_tree_mid_order(root)
    pHead=None
    pEnd=None
    BiTreeToDLink(root)
    cur=pHead
    print("双向链表正序:")
    while cur is not None:
        print(cur.data)
        cur=cur.right_child
    cur = pEnd
    print("双向链表倒序:")
    while cur is not None:
        print(cur.data)
        cur = cur.left_child

运行结果,我链表用的随机数组生成的:

image.png image.png image.png

明白了吗?
全部代码:

import random
class BiTNode:
    """docstring for BiTNode"""
    def __init__(self,arg):
        self.data = arg
        self.left_child = None
        self.right_child = None

def arrayToBiTree(array):
    #判断arr是否为空
    if len(array)==0:
        return BiTNode(array[0])
    mid=len(array)//2 # 有序数组的中间元素的下标
    #print(mid)
    #start=0 # 数组第一个元素的下标
    #end=-1 # 数组最后一个元素的下标
    if len(array)>0:
        #将中间元素作为二叉树的根
        root=BiTNode(array[mid])
        #如果左边的元素个数不为零,则递归调用函数,生成左子树
        if len(array[:mid])>0:
            root.left_child = arrayToBiTree(array[:mid])
        #如果右边的元素个数不为零,则递归调用函数,生成左子树
        if len(array[mid+1:])>0:
            root.right_child = arrayToBiTree(array[mid+1:])
    return root 

def constuctBiTree(x):
    #构造一个没有零的二叉树
    arr=[]
    for i in range(x):
        x=random.randint(0,9)
        arr.append(x)
    print(arr)
    root=arrayToBiTree(arr)
    return root

#中序遍历
def print_tree_mid_order(root):
    #先判断二叉树是否为空,当左右节点都为空时
    if root is None:
        return
    #中序遍历 左根右
    #遍历左子树
    if root.left_child is not None:
        print_tree_mid_order(root.left_child)
    #遍历根节点
    print(root.data)
    #遍历右子树
    if root.right_child is not None:
        print_tree_mid_order(root.right_child)

def BiTreeToDLink(root):
    global pHead
    global pEnd
    if root is None:
        return
    #左子树
    BiTreeToDLink(root.left_child)
    #根节点的左孩子指向pEnd,pEnd的有孩子指向root
    root.left_child=pEnd
    if None == pEnd:
        pHead=root
    else:
        pEnd.right_child = root
    #右子树
    pEnd=root
    BiTreeToDLink(root.right_child)

if __name__ == '__main__':
    root=constuctBiTree(12)
    print("中序遍历:")
    print_tree_mid_order(root)
    pHead=None
    pEnd=None
    BiTreeToDLink(root)
    cur=pHead
    print("双向链表正序:")
    while cur is not None:
        print(cur.data)
        cur=cur.right_child
    cur = pEnd
    print("双向链表倒序:")
    while cur is not None:
        print(cur.data)
        cur = cur.left_child


今天的就到这里,我想我以后应该早上发文。

今天尝试ajax爬取,分析ajax给我弄懵了。。。。
一会继续试一试。

相关文章

  • python-025-把二叉树转换为双向链表

    题目:给定一个二叉树,将其转换为双向链表。 双向链表的特征是每一个节点都保存着其前驱节点和后继节点的地址,而二叉树...

  • 二叉排序树转双向链表

    排序二叉树转换为排序双向链表 题目:输入一棵二叉排序树,将该二叉排序树转换成一个排序的带头结点的双向链表。如: 转...

  • BST与双向链表

    把BST转换为双向链表 给出一棵BST,将其转换为双向链表,left保存前节点,right保存后节点。 例如: ...

  • 69_二叉树的线索化实现

    关键词:二叉树的额线索化 0. 什么是线索化二叉树? 将二叉树转换为双向链表的过程(非线性==》线性) 能够反映某...

  • 将二叉搜索树转化为排序的双向链表

    题目 将二叉搜索树转化为排序的双向链表 例如,下图二叉搜索树转换为图中的排序的双向链表。 解析 转换为排序的双向链...

  • 数据结构和算法总结

    常用数据结构: 数组,栈,队列,链表(单向链表,双端链表,双向链表),哈希表(hash table),树(二叉树,...

  • 1.路径之和 2.最近公共祖先 3.是否后序bst 4.二叉树转

    3.是否是bst的后续便利 4.二叉树转链表 5.bst转双向链表 6.第k小的元素 7.序列化8.删除bst一个点

  • Linux内核设计与实现——内核数据结构

    主要内容 链表 队列 映射 二叉树 1. 链表 单向链表、双向链表 环形链表 linux内核中的链表使用方法和一般...

  • 二叉树转链表

    给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外...

  • 双向链表&双向循环链表

    链表分为:单链表、单向循环链表、双向链表、双向循环链表本节主要说明:双向链表、双向循环链表 定义结点 一、双向链表...

网友评论

    本文标题:python-025-把二叉树转换为双向链表

    本文链接:https://www.haomeiwen.com/subject/dsonvqtx.html