数据结构——树

2018-02-13

二叉树

树是一种重要的非线性数据结构，主要的用途是用来提高查找效率，对于要重复查找的情况效果更佳，如二叉排序树、FP-树。另外可以用来提高编码效率，如哈弗曼树。一切具有层次关系的问题都可用树来描述。
树结构的特点是：

它的每一个结点都可以有不止一个直接后继
除根结点外的所有结点都有且只有一个直接前驱。
树的递归定义如下：

至少有一个结点（称为根）
其它是互不相交的子树

二叉树结构

节点值
左孩子

右孩子

class Node:
    # 创建节点类，包含左右两个指针，一个节点
    def __init__(self,elem=None):
        self.elem=elem
        self.right=None
        self.left=None

二叉树遍历

paste image
先序遍历：1,2,4,5,3,6,7
中序遍历：4,2,5,1,6,3,7
后序遍历：4,5,2,6,7,3,1
还有：中右左、右中左、右左中三中不常见的遍历
层序遍历：1,2,3,4,5,6,7
按层遍历二叉树实际上是宽度优先搜索的应用。

使用递归实现二叉树的遍历：

class printTree:
    def __init__(self):
        self.root = Node()
        self.myQueue = []

    def add(self, elem):  # 采用一个堆栈实现
        node = Node(elem)
        if self.root.elem == None:
            self.root = node
            self.myQueue.append(self.root)
        else:
            cur = self.myQueue[0]
            if cur.left == None:
                cur.left = node
                self.myQueue.append(cur.left)
            else:
                cur.right = node
                self.myQueue.append(cur.right)
                self.myQueue.pop(0)

    def pre_order(self, root): #前序遍历
        if root == None:
            return
        print(root.elem, end=' ')
        self.pre_order(root.left)
        self.pre_order(root.right)

    def mid_order(self, root): #中序遍历
        if root == None:
            return
        self.mid_order(root.left)
        print(root.elem, end=' ')
        self.mid_order(root.right)

    def post_order(self, root): #后序遍历
        if root == None:
            return
        self.post_order(root.left)
        self.post_order(root.right)
        print(root.elem, end=' ')

非递归实现二叉树的遍历：

def pre_stack(self, root):
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop(0)
        print(node.elem, end=' ')
        if node.right:
            stack.insert(0, node.right)
        if node.left:
            stack.insert(0, node.left)

def mid_stack(self, root):
    if not root:
        return
    stack = []
    cur = root
    while stack or cur:
        while cur:
            stack.insert(0, cur)
            cur = cur.left
        cur = stack.pop(0)
        print(cur.elem, end=' ')
        cur = cur.right

def post_stack(self, root):  # 实现方法一
    if not root:
        return
    stack1 = [root]
    stack2 = []
    while stack1:
        cur = stack1.pop()
        stack2.insert(0, cur)
        if cur.left:
            stack1.append(cur.left)
        if cur.right:
            stack1.append(cur.right)
    for i in stack2:
        print(i.elem, end=' ')

def post_stack2(self, root):  # 实现方法二
    if not root:
        return
    h = root  # 最近一次弹出并打印的节点
    c = None  # 当前stack的栈顶节点
    stack = [root]
    while stack:
        c = stack[0]
        if c.left and h != c.left and h != c.right:
            stack.insert(0, c.left)
        elif c.right and h != c.right:
            stack.insert(0, c.right)
        else:
            h = stack.pop(0)
            print(h.elem, end=' ')

递归和非递归的方法时间复杂度都是O(N)，N为二叉树节点数，额外空间复杂度为O(L)，L为二叉树的层数。

实现二叉树的层序遍历：

def level_queue(self, root):
    if root == None:
        return
    stack=[root]
    while stack:
        cur=stack.pop(0)
        print(cur.elem,end=' ')
        if cur.left:
            stack.append(cur.left)
        if cur.right:
            stack.append(cur.right)
def level_queue_enter(self, root):  # 实现换行
    if not root:
        return
    last = root  # 表示正在打印的当前行的最右节点
    nlast = None  # 表示下一行的最右节点
    stack = [last]
    while stack:
        cur = stack.pop(0)
        print(cur.elem, end=' ')

        if cur.left:
            stack.append(cur.left)
            nlast = cur.left
        if nlast.right:
            stack.append(cur.right)
            nlast = cur.right

        if last == cur:
            print()
            last = nlast

根据遍历顺序还原二叉树

例如给定前序和中序的打印顺序，求后续遍历。
前序遍历有个特点，第一个肯定为根。然后根据根，在中序遍历可以区分出来左子树和右子树。递归的查找，就可以还原了。

def permid_post(perstr, midstr):
    if not perstr or not midstr:
        return
    val = perstr[0]
    node = Node(val)
    index = midstr.find(val)
    permid_post(perstr[1:index+1],midstr[:index])
    permid_post(perstr[index+1:],midstr[index+1:])
    print(node.elem,end=' ')
perstr = 'GDAFEMHZ'
midstr = 'ADEFGHMZ'
permid_post(perstr,midstr)

二叉树序列化和反序列化

有时我们需要用文件的形式将二叉树记录下来，下次要重构二叉树的时候只需将按照文件重新建立二叉树即可。这个过程叫做序列化过程，也叫持久化过程。
序列化方式：

先序遍历序列化
中序遍历序列化
后序遍历序列化
按层序列化

先序遍历二叉树过程与中序后序相同，步骤如下：

假设序列化结果为str，初始时str为空字符串
先序遍历二叉树时如果遇到空节点，在str末尾加上“#！”
如果遇到不为空的节点，假设节点值为3，就在str末尾增加‘3！’
先序遍历反序列化过程：
按照！分割字符串
按照先序遍历的顺序构建二叉树，遇到#设置为空节点

def Serialize(self, root):  # 把对象转换为字节序列的过程称为对象的序列化
    def Per_order(root):
        if not root:
            result.append('#!')
            return
        result.append(str(root.elem) + '!')
        Per_order(root.left)
        Per_order(root.right)

    result = []
    Per_order(root)
    return ''.join(result)

def Deserialize2(self, s):  # 把字节序列恢复为对象的过程称为对象的反序列化
    s = s.split("!")
    self.myroot=None

    def change(index):
        index[0] += 1
        if index[0] >= len(s):
            return
        if s[index[0]] == '#':
            return
        node = Node()
        node.elem = s[index[0]]
        if not self.myroot:
            self.myroot = node
        node.left = change(index)
        node.right = change(index)
        return node

    index = [-1]
    change(index)
    return self.myroot

当然，用什么方法序列化，要用同样的方法反序列化才行。

二叉树的一些概念

二叉的子树

在二叉树中以任何一个节点为头部的整棵树称为二叉树的子树。
paste image
上图不是子树，因为不是整棵树。只是一个联通的子结构

平衡二叉树（AVL树）

空树是平衡二叉树
一棵树不为空，并且其中所有子树都满足各自的左子树与有字数的高度差都不超过1。

这不是一颗平衡二叉树，以②为节点划分，左子树高度为2，右子树高度为0，高度差超过了1。

判断一个树是否是平衡二叉树，采用递归的后续遍历：
paste image

首先判断左子树是否为平衡二叉树返回false，则结束。
计算左子树最深到哪一层，LH
判断右子树是否为平衡二叉树返回false，则结束。
计算右子树最深到哪一层，RH

判断LH和RH是否相等。

def is_balanced2(self, root):
    if not root:#空树是平衡二叉树
        return True,0
    left_info=self.is_balanced(root.left)
    right_info=self.is_balanced(root.right)
    if left_info[0] and right_info[0]:
        diff=left_info[1]-right_info[1]
        if -1<=diff<=1:
            return True,max(left_info[1],right_info[1])+1
    return False,max(left_info[1],right_info[1])+1

不平衡二叉树旋转
首先旋转的二叉树是二叉查找树，讨论的是其平衡问题。这样很好的解决了二叉查找树退化成链表的问题。使得插入、查找删除的最好最坏时间复杂度都为O(logN)。
左左或者右右，可以使用单旋转：
paste image

左右或者右左，可以使用双旋转
paste image

平衡二叉树查找
平衡二叉树插入
平衡二叉树删除

二叉查找树

是满足以下条件的二叉树：

左子树上所有节点值均小于根节点值
右子树上所有节点值均不小于根节点值
左右子树也满足上述两个条件

二叉查找树的查找过程

若当前节点cur的值小于p的值，查找cur的左子树
若当前节点cur的值不小于p的值，查找cur的右子树
递归上述过程，直到cur==p或者cur为空

二叉查找树的插入

二叉查找树的删除

满二叉树

除了最后一层的节点无任何子节点外，剩下的每一层节点都有两个子节点。

满二叉树层数为L，节点数为N，则$N=2^L-1$，$L=\log_2^{(N+1)}$

完全二叉树

除了最后一层外，其他的每一层节点都是满的。最后一层慢了那就是满二叉树。最后一层不满，缺少的节点也全部集中在右边，那也是完全二叉树。
paste image
上面两个图均为完全二叉树。

这就不是一个完全二叉树。

判断是否完全二叉树

采用按层遍历二叉树的方式，从每层左边向右边一次遍历所有节点。
如果当前节点有右孩子，但没有左海子，直接返回False.
如果当前节点不是左右孩子全有，那之后节点必须都为叶节点，否则返回False。
遍历过程中如果不返回False，遍历结束后返回True。
后继与前驱
后继节点：这个节点在中序遍历序列中的下一个节点。
前驱结点：这个节点在中序遍历序列中的前一个节点。

二叉树