25.重建二叉树

2022-08-11
浏览 (422)

树的知识点：

什么叫做树？

树状图是一种数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

叶节点没有子节点，根节点没有父节点。

什么是二叉树？

每个节点最多含有两个子树的树称为二叉树。下图就是一个二叉树。

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个节点，至多有2k-1个节点

二叉树的遍历：

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

class treeNode(object):
    def __init__(self,x):
        self.val = x
        self.left = None
        self.right = None

#1. 深度优先
#2. 广度优先
#对于深度优先来说：
"""

1 先序遍历  先打印根 1,2,4,5,3,6,8,7
2 中序遍历  先打印左侧的叶子节点 4，再输出 中节点  2 ；  4 2 5 1 6 8 3 7 
3 先序遍历  输出顺序  4 5 2 8 6 7 3 1

注意：  先序   中序 后序  都是对应于根节点来说的，左右节点都是先左后右

"""
#递归
def preOrderRecusive(root):
    if root == None:
        return None

    print(root.val)
    preOrderRecusive(root.left)
    preOrderRecusive(root.right)

def midOrderRecusive(root):
    if root == None:
        return None
    midOrderRecusive(root.left)
    print(root.val)
    midOrderRecusive(root.right)


def laterOrderRecusive(root):
    if root == None:
        return None
    laterOrderRecusive(root.left)
    laterOrderRecusive(root.right)
    print(root.val)

#非递归的形式 去遍历数
#递归和循环是可以互相转换的

"""

1 先根遍历 先访问根节点，再访问左子节点，最后访问右子节点
2 中根遍历 先访问左子节点，再访问根节点，最后访问右子节点
3 后跟遍历 先访问左子节点，再访问右子节点，最后访问根节点。

"""

def preOrder(root):
    if root == None:
        return None

    stack = []
    tmpNode = root
    while tmpNode or stack :
        while tmpNode:
            print(tmpNode.val)
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node  = stack.pop()
        tmpNode = node.right

def midOrder(root):
    if root == None:
        return None

    stack = []
    tmpNode = root
    while tmpNode or stack :
        while tmpNode:

            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node  = stack.pop()
        print(node.val)
        tmpNode = node.right

def laterOrder(root):
    if root == None:
        return None

    stack = []
    tmpNode = root
    while tmpNode or stack :
        while tmpNode:
            stack.append(tmpNode)
            tmpNode = tmpNode.left
        node = stack[-1]
        tmpNode = node.right
        if node.right == None:
            node = stack.pop()
            print(node.val)
            while stack and node == stack[-1].right:
                node =  stack.pop()
                print(node.val)