二叉树 Binary Tree

二叉树的特点
    每个节点的度最大为2（最多拥有2棵子树）
    左子树和右子树是有顺序的
    即使某个节点只有一棵子树，也要区分左右子树

二叉树的性质
    非空二叉树的第i层最多有 2^(i-1) 个节点（i >= 1）
    高度为h的二叉树上最多有 2^h - 1 个节点（h >= 1）
    对于任何一棵非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有 n0 = n2 + 1
        推导：设度为1的节点个数为n1，总节点数 n = n0 + n1 + n2
              边数 T = n1 + 2*n2 ，T = n - 1
              =>    n1 + 2*n2 = n - 1 = n0 + n1 + n2    =>    n0 = n2 + 1

二叉树节点表示
    每个节点node包含三部分：数据域elem，指向左子树的的指针lchild，指向右子树的指针rchild

二叉树遍历
    深度优先，一般用递归
        先序 Preorder
        中序 Inorder
        后序 Postorder
    广度优先，一般用队列

真二叉树 Proper Binary Tree
    所有节点的度都为0或2

满二叉树 Full Binary Tree
    所有节点的度都为0或2，且所有叶子节点都在最后一层
    设高为h（h>=1），则：第i层节点：2^(i-1)，叶子节点：2^(h-1)，总节点：n = 2^h - 1
                      =>    h = log2(n+1)

完全二叉树 Complete Binary Tree
    叶子节点只会出现在最后2层，且最后1层的叶子节点都靠左对齐
    完全二叉树从根节点至倒数第2层是一棵满二叉树；满二叉树一定是一棵完全二叉树
    性质：
        度为1的节点只有左子树；度为1的节点要么是0个，要么是1个
        节点数相同的二叉树中，完全二叉树的高度最小

        设完全二叉树高度为h，则：
            至少有 2^(h-1) 个节点
            最多有 2^h - 1 个节点
            总结点数为n，则有 h = floor( log2n ) + 1
                推导：2^(h-1) <= n < 2^h
                    =>    h - 1 <= log2n < h
                    =>    h = floor( log2n ) + 1

        一棵有n个节点的完全二叉树，从上到下、从左到右对节点从1开始进行编号，对任意第i个节点，有：
            如果 i = 1 ,它是根节点
            如果 i > 1 ,它的父节点编号为 floor(i // 2)
            如果 2i <= n ,它的左子节点编号为 2i
            如果 2i > n ,它没有左子节点
            如果 2i + 1 <= n ,它的右子节点编号为 2i + 1
            如果 2i + 1 > n ,它没有右子节点

二叉树定义、深度优先遍历、广度优先遍历

定义单位元素

class Node(object):
    def __init__(self,elem):
        self.elem = elem
        self.lchild = None
        self.rchild = None

定义二叉树

class Tree(object):
    def __init__(self,root=None):
        self.root = root

    # 添加节点
    # 对树逐层从左到右遍历，当出现空位时加入节点
    def add(self,elem):
        node = Node(elem)

        # 若为空树，添加的节点就是根节点
        if self.root == None :
            self.root = node
        else :
            # 创建空队列，把树中的节点逐层从左到右加入队列
            queue = []
            queue.append(self.root)
            while queue :
                # 每次取出队列中的第一个元素，即每层节点从左到右的顺序
                cur = queue.pop(0)
                # 当有节点度不为2时，执行添加
                if cur.lchild == None :
                    cur.lchild = node
                    return
                elif cur.rchild == None :
                    cur.rchild = node
                    return
                # 若该节点度为2，则将它的两个子节点先左后右加入队列
                else :
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)
  
  
    # 深度优先遍历，使用递归

    # 先序遍历，1,2,4,8,9,5,10,3,6,7
    # 对于一个节点，先访问自己，再访问左子树，最后访问右子树
    def Preorder(self,root):
        if root == None :
            return
        else :
            print(root.elem)
            self.Preorder(root.lchild)
            self.Preorder(root.rchild)

    # 中序遍历，8,4,9,2,10,5,1,6,3,7
    # 对于一个节点，先访问左子树，再访问自己，最后访问右子树
    def Inorder(self,root):
        if root == None :
            return
        else :
            self.Inorder(root.lchild)
            print(root.elem)
            self.Inorder(root.rchild)

    # 后续遍历，8,9,4,10,5,2,6,7,3,1
    #对于一个节点，先访问左子树，再访问右子树，最后访问自己
    def Postorder(self,root):
        if root == None :
            return
        else :
            self.Postorder(root.lchild)
            self.Postorder(root.rchild)
            print(root.elem)

    # 广度优先遍历
    def breadth_search(self,root):
        if root == None :
            return

        queue = []
        queue.append(root)
        while queue :
            cur = queue.pop(0)
            print(cur.elem)
            if cur.lchild != None :
                queue.append(cur.lchild)
            if cur.rchild != None :
                queue.append(cur.rchild)