树和二叉树

树

树一种抽象类型数据，用来模拟具有树状结构性质的数据集合。它是由多个有限节点组成一个层次关系的集合。特点：

• 每个节点有0个或者多个子节点
• 没有父节点的节点称之为根节点
• 每个非根节点有且只有一个根节点

术语

• 节点的度：一个节点含有的子树的个数称为该节点的度
• 树的度：最大的节点的度称之为数的度
• 叶结点或终端节点：度为零的节点
• 父节点：含有子节点的节点上级
• 子节点：一个节点还有的子树的根节点称为该节点的子节点
• 兄弟节点：具有相同父节点的节点
• 节点的层次：根节点为第一层，其子节点为第二层，类推
• 树的高度或者深度：节点最大层次
• 堂兄弟节点：父节点在同一层次的节点
• 森林：由多个树互不相交的树的集合称为森林

树的种类

• 无序树：任意节点的子节点之间没有任何的顺序关系，称之为无序树，也叫自由树
• 有序树：子节点之间由顺序关系
  • 二叉树：每个节点最多含有两个子树的树
    • 完全二叉树：若一棵树的深度为d，除去第d层外，其他各层的节点数目达到了最大值，且第d层所有节点从左向右连续紧密的排列的二叉树
    • 满二叉树：所有层的节点数达到了最大数
    • 平衡二叉树：当且仅当任何节点之间的两颗子树的高度差不大于1的二叉树
    • 排序二叉树：二叉搜索树，二叉查找树，性质：任何节点左边的数比节点上的数小，右边比节点上的数大
  • 霍夫曼树：用于信息编码
  • $B$树/$B^+$树：在MySQL的索引中使用

树的存储

• 顺序存储：将数据结构存储在固定的数组中，遍历上有一定的优势，占空间
• 链式存储

应用场景

• HTML文件
• 路由协议
• mysql索引
• 文件目录的目录结构
• AI算法都是树搜索，比如决策树

二叉树

每个节点最多只有两个子节点，左子树和右子树，性质：

• 第i层上最多$2^(i-1)$个节点
• 深度为k的二叉数最多有$2^k-1$个节点
• 具有n个节点的完全二叉树的深度必为$log2(n+1)$
• 叶结点数为$N_0$，深度为2的节点总数为$N_2$，则$N_0=N_2+1$

树的遍历

深度遍历的三种遍历顺序：

子节点中必须先左后右

• 前序遍历：根—>左—>右
• 中序遍历：左—>根—>右
• 后序遍历：左—>右—>根

二叉树的确定

根据三种遍历方式的两种来确定二叉树，其中必须给定中序遍历的结果

# 二叉树中元素添加

class Node(object):
    def __init__(self,item):
        # 定义节点的左右子树
        self.elem = item
        self.lchild = None
        self.rchild = None
        
class Tree(object):   
    # 树类
    def __init__(self):
        # 定义树类
        self.root = None
        
    def add(self, item):
        # 实例化一个节点
        node = Node(item)
        # 如果根节点是空的，直接添加元素
        if self.root is None:
            self.root = node
            return 
        # 定义队列来存放元素，首先是根节点
        queue = [self.root]
        
        # 循环条件：队列是否为空
        while queue:
            # 通过队列来实现，一端进另一端出，先进先出
            # 删除首位元素
            cur_node = queue.pop(0)
            # 判断左右子树是否为空，是的话直接追加，不是则追到队列末尾
            if cur_node.lchild is None:
                cur_node.lchild = node
                return 
            else:
                queue.append(cur_node.lchild)

            if cur_node.rchild is None:
                cur_node.rchild = node
                return 
            else:
                queue.append(cur_node.rchild)
                
    def breadth_travel(self):
        # 广度遍历
        
        # 处理空的根节点
        if self.root is None:
            return
        
        # 非空节点通过队列来处理
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem, end=" ")
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)
                
                
    def preorder(self, node):
        # 先序遍历
        
        # 如果传进的节点是Node，说明是叶子节点，不必再进行遍历
        if node is None:
            return 
        print(node.elem, end=" ")
        
        # 处理根节点的左右子树
        self.preorder(node.lchild)
        self.preorder(node.rchild)
    
    def inorder(self, node):
        # 中序遍历
        # 只需要调整打印和两次递归调用的顺序，
        # 调用的是函数自身
        if node is None:
            return 
        # 左根右
        self.inorder(node.lchild)
        print(node.elem, end=" ")
        self.inorder(node.rchild) 
    
    def postorder(self, node):
        # 后序遍历
        if node is None:
            return 
        # 左右根
        self.postorder(node.lchild)
        self.postorder(node.rchild) 
        print(node.elem, end=" ")
                
if __name__ == "__main__":
    tree = Tree()
    # 添加的顺序和遍历出来的顺序是一样的
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travel()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)
    print(" ")

# res
0 1 2 3 4 5 6 7 8 9  
0 1 3 7 8 4 9 2 5 6  
7 3 8 1 9 4 0 5 2 6  
7 8 3 9 4 1 5 6 2 0

树的遍历图解

在给出数的顺序反推树结构的时候，必须给定$\color{red}{中序}$，下面👇的栗子根据先序和中序确定一棵树：