[数据结构与算法]数据结构与算法python版 MOOC 第九周

九、树及算法-上

本系列博客基于“ (北京大学)数据结构与算法python版”慕课，课程在中国大学慕课和bilibili上均可找到。

1. 内容

1. 树结构的相关术语
2. 树的表示方法：嵌套列表，链表
3. 树的遍历（前序，中序，后序）和应用（表达式解析）
4. 使用二插堆Binary Heap实现优先队列

2. 课程代码

在GitHub中下载

3. OJ作业

所有代码均可在github中下载

3.1 二叉树复原

题目内容：
? ?给定一种序列化二叉树的方式：从根节点起始按层次遍历二叉树所有“可能”存在节点的位置：若该位置存在节点，则输出节点值，并在下一层相应增加两个可用位置；否则输出None，且不增加下一层的可用位置。
? ?例如"[5, 4, 7, 3, None, 2, None, -1, None, 9]"是下图所示的二叉树序列化的结果：

? ?其中红色箭头对所有的None进行了标记。
? ?现给出一个二叉树以这种形式序列化的结果，请复原该二叉树并给出它的中序遍历。

输入格式: 一行合法的Python表达式，可解析为包含整数与None的列表
输出格式：二叉树中序遍历的整数序列，以空格分隔

输入样例：
[5, 4, 7, 3, None, 2, None, -1, None, 9]
输出样例：
-1 3 4 5 9 2 7

输入样例2：
[5,1,4,None,None,3,6]
输出样例2：
1 5 3 4 6
注：树结构如图（红色箭头对None的对应位置进行了标记）：

方法：
用队列来存储树的节点，用左右flag来标记首先将根结点放入队列，每次从队首出列一个结点
? ?如果此时列表值为none，说明当前节点没有子节点
? ?? ?如果左右标志均=0，把左标志设为1，表示插入none，结点插回队首
? ?? ?如果左标志=0右标志=1，把右标志设为1，表示插入none，结点插回队首
? ?如果此时列表值不为none,说明当前节点有子节点
? ?? ?如果左右标志=0，把列表值变为当前结点左子树，左标志=1，结点插回队首，左子节点跟在队尾
? ?? ?如果左=1，右=0，把列表值变为当前结点右子树，右标志=1，结点插回队首，右子节点跟在队尾
因此，队列当中结点的顺序是 a, b…, a.left_child, a.right_child, b.left_child。顺序和逐层遍历一致

class BinaryTree:
    """
    A recursive implementation of Binary Tree
    Using links and Nodes approach.
    """
    def __init__(self, rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
        self.leftFlag = 0  #
        self.rightFlag = 0  #


def seq2tree(seq):
    # 将列表反序列化为树
    queue = []  # 队列储存树
    current_tree = BinaryTree(seq[0])
    whole_tree = current_tree
    queue.append(current_tree)
    i = 1  # 从1开始遍历
    while i < len(seq) and len(queue) > 0:
        current_tree = queue.pop(0)
        if seq[i] == None:  # 当前点没有子节点  相当于是判断current_tree的子节点是否插入
            if current_tree.leftFlag == 0 and current_tree.rightFlag == 0:  # 当前节点还没插入节点 所以把左flag=1 表示已经插入了none
                current_tree.leftFlag = 1
                queue.insert(0, current_tree)
            elif current_tree.leftFlag == 1 and current_tree.rightFlag == 0:  # 当前节点已经插入了左子节点 所以把右flag=1 表示已经插入了none
                current_tree.rightFlag = 1
            i = i+1
        else:
            if current_tree.leftFlag == 0 and current_tree.rightFlag == 0:  # 左右同时为0 表示还没有插入子树 此处插入左子节点
                current_tree.leftChild = BinaryTree(seq[i])
                current_tree.leftFlag = 1
                queue.append(current_tree.leftChild)
                queue.insert(0, current_tree)
                i = i+1
            elif current_tree.leftFlag == 1 and current_tree.rightFlag == 0:   # 左=1 右=0 插入右子节点
                current_tree.rightChild = BinaryTree(seq[i])
                current_tree.rightFlag = 1
                queue.append(current_tree.rightChild)
                i = i+1
            else:
                i = i
    return whole_tree


def inorderTree(root):
    # 中序遍历树
    if root == None:
        return []
    else:
        left = inorderTree(root.leftChild)
        data = root.key
        right = inorderTree(root.rightChild)
        return left+[data]+right


lst = eval(input())
tree = seq2tree(lst)
inorder = inorderTree(tree)
print(' '.join(str(x) for x in inorder))  # 请自行确定打印方式

3.2 翻转二叉树

题目内容：
? ?给定一个二叉树，请给出它的镜面翻转。为方便起见，本题只给出完全二叉树的层次遍历，请给出相应的翻转二叉树的中序遍历。

输入格式: 一行空格分隔的整数序列，表示一个完全二叉树的层次遍历
输出格式：一行空格分隔的整数序列，表示翻转后的二叉树的中序遍历

输入样例：
4 2 7 1 3 6 9
输出样例：
9 7 6 4 3 2 1

方法：通过3.1的方法将层次二叉树转为二叉树的形式 然后使用 右 中 左 的中序遍历

代码

class BinaryTree:
    """
    A recursive implementation of Binary Tree
    Using links and Nodes approach.
    """
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
        self.leftFlag = 0  #
        self.rightFlag = 0  #


def seq2tree(seq):
    # 将列表反序列化为树
    queue = []  # 队列储存树
    current_tree = BinaryTree(seq[0])
    whole_tree = current_tree
    queue.append(current_tree)
    i = 1  # 从1开始遍历
    while i < len(seq) and len(queue) > 0:
        current_tree = queue.pop(0)
        if seq[i] == None:  # 当前点没有子节点  相当于是判断current_tree的子节点是否插入
            if current_tree.leftFlag == 0 and current_tree.rightFlag == 0:  # 当前节点还没插入节点 所以把左flag=1 表示已经插入了none
                current_tree.leftFlag = 1
                queue.insert(0, current_tree)
            elif current_tree.leftFlag == 1 and current_tree.rightFlag == 0:  # 当前节点已经插入了左子节点 所以把右flag=1 表示已经插入了none
                current_tree.rightFlag = 1
            i = i+1
        else:
            if current_tree.leftFlag == 0 and current_tree.rightFlag == 0:  # 左右同时为0 表示还没有插入子树 此处插入左子节点
                current_tree.leftChild = BinaryTree(seq[i])
                current_tree.leftFlag = 1
                queue.append(current_tree.leftChild)
                queue.insert(0, current_tree)
                i = i+1
            elif current_tree.leftFlag == 1 and current_tree.rightFlag == 0:   # 左=1 右=0 插入右子节点
                current_tree.rightChild = BinaryTree(seq[i])
                current_tree.rightFlag = 1
                queue.append(current_tree.rightChild)
                i = i+1
            else:
                i = i
    return whole_tree


def tranvers_inorder_Tree(root):
    # 中序遍历树
    if root == None:
        return []
    else:
        left = tranvers_inorder_Tree(root.leftChild)
        data = root.key
        right = tranvers_inorder_Tree(root.rightChild)
        return right+[data]+left


lst = list(map(int, input().split()))
tree = seq2tree(lst)
inorder = tranvers_inorder_Tree(tree)
print(' '.join(str(x) for x in inorder))  # 请自行确定打印方式

3.3 多叉树遍历

题目内容：
? ?给定以嵌套列表形式给出的多叉树，求它的后序遍历
? ?注：每个代表非空多叉树的列表包含至少一项；列表第一项代表节点值，其后每一项分别为子树；遍历子树时以列表下标从小到大的顺序进行。

输入格式: 一行合法的Python表达式，可解析为嵌套列表形式的多叉树结构
输出格式：一行整数，以空格分隔

输入样例：
[1,[2,[3,[4],[5]],[6]],[7],[8,[9],[10]]]
输出样例：
4 5 3 6 2 7 9 10 8 1

方法：采用递归的方式

代码：

def postorder(lst):
    if len(lst) == 1:  # 遍历到了页节点
        return lst
    else:
        ordered_string = []
        for i in range(1, len(lst)):  # 遍历子节点
            child = postorder(lst[i])
            ordered_string = ordered_string+child
        ordered_string.append(lst[0])  # 加入根结点
        return ordered_string


lst = eval(input())
string = postorder(lst)
print(' '.join(str(x) for x in string))