树——数据结构与算法 总结5

1. 树的性质：

树中的节点数等于所有节点的度数之和加1

2. 树的基本术语

• 节点的度：节点所拥有的子树的个数
• 树的度：树中各节点度的最大值

    

• 叶子节点 (leaf node)：度为 0 的节点，也称为终端节点（外节点）
• 分支节点(branch node)：度不为 0 的节点，也称为非终端节点（内节点）
• 孩子 (child)：树中某节点子树的根节点称为这个节点的孩子节点
• 双亲(parent)：这个节点称为它孩子节点的双亲节点
• 兄弟(brother)：具有同一个双亲的孩子节点互称为兄弟
• 路径：节点序列 n1, n2, …, nk 称为一条由 n1 至 nk 的路径，当且仅当满足如下关系：结点 ni 是 ni+1 的双亲（0<=i<k）
• 路径长度(path length)：路径上经过的边的个数
• 祖先(ancestor)、子孙(descendant)：如果有一条路径从节点 x 到节点 y，则 x 称为 y 的祖先，而 y 称为 x 的子孙
• 节点所在层数：根节点的层数为 1；对其余节点，若某节点在第 k 层，则其孩子节点在第 k+1 层。

    

• 树的深度（高度）：树中所有节点的最大层数
• 森林：互不相交的树集合
• 有序树：子树有序的树，如家族树
• 无序树：不考虑子树的顺序的树
• 层序编号：将树中节点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。
• 树通常有先序遍历、后序遍历和层序遍历。非二叉树的树没有中序遍历。
• 二叉树：二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（空二叉树），或者由一个根节点和两颗互不相交的二叉树组成.
• 满二叉树：在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子都在同一层上
• 完全二叉树：在满二叉树中，从最后一个节点开始，连续去掉任意个节点，就是一棵完全二叉树。

3. 二叉链表存储

二叉链表的存储方式：

二叉树的节点对应链表节点：

n 个节点的二叉链表有 2n-(n-1) = n+1 个空指针域

如果想用遍历序列生成二叉树的二叉链表，可以用扩展二叉树的前序遍历。

3. 树的遍历

3.1 二叉树的遍历

Preorder Traversal 先序遍历：A B D H I E J C F K G

遍历图来自：数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）_中序遍历-CSDN博客

Inorder Traversal 中序遍历: H D I B E J A F K C G

给出中序遍历，就能知道左右关系

Postorder Traversal后序遍历：H I D J E B K F G C A

层序遍历：从根开始逐层向下遍历（可以用队列实现）

（二叉树遍历图取自： 数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）_中序遍历-CSDN博客）

知道前序和后序遍历不能确定一棵唯一的二叉树；

知道前序和中序或者后序和中序遍历可以确定一棵唯一的二叉树

所以如果给出遍历的顺序让画出树，一定会给出中序遍历的顺序，而中序遍历的顺序可以确定左右关系，所以可以按照中序遍历的顺序再根据其他遍历确定结构。

# 遍历二叉树的Python实现
 
class BTNode():  # 节点类
    def __init__(self, data = None, lchild = None, rchild = None):
        self.data = data
        self.lchild = lchild  # 左孩子
        self.rchild = rchild  # 右孩子
 
def createBinTree():  # 根据输入创造二叉树，返回根节点
    ch = input()  # 一个字母代表一个节点，‘*’号表示节点为None
    if ch == '*':
        T = None
    else:
        T = BTNode()
        T.data = ch  # 生成根节点
        T.lchild = createBinTree()
        T.rchild = createBinTree()
    return T
 
def preorder(T):  # 先序遍历
    if T in None:
        return
    print(T.data, end = ' ')
    preorder(T.lchild)
    preorder(T.rchild)
 
def postorder(T):  # 后序遍历
    if T is None:
        return
    postorder(T.lchild)
    postorder(T.rchild)
    pring(T.data, end = ' ')
 
def inorder(T):  # 中序遍历
    if T is None:
        return
    inorder(T.lchild)
    print(T.data, end = ' ')
    inorder(T.rchild)
 
def levelorder(T):  # 基于队的层序遍历
    queue = []
    sum = 0
    if T is not None:
        queue.append(T)
    while queue!=[]:
        q = queue.pop(0)
        print(q.data,end='')
        if q.lchild:
            queue.append(q.lchild)
        if q.rchild:
            queue.append(q.rchild)
 
def countleaf(T):  # 计算叶子节点数量
    global n  #用于存储叶子节点数的变量
    if T is None:
        return n
    if T.lchild is None and T.rchild is None:
        n+=1
    countleaf(T.lchild)
    countleaf(T.rchild)

 3.2 树和森林的遍历

层次遍历:从上到下，从左至右依次遍历树中各个节点

先根遍历:先访问根，然后依次先序遍历每一棵子树

后根遍历:依次后序遍历根的每一棵子树，然后访问根

树的先根遍历对应二叉树的先序遍历

树的后根遍历对应二叉树的中序遍历

先根遍历森林和先序遍历与该森林对应的二叉树结果相同

后根遍历森林和中序遍历与该森林对应的二叉树结果相同

非二叉树的树没有中序遍历。

4. 二叉树的性质

性质 1：非空二叉树上叶子结点数等于度为2的结点数加1。即。

性质 2：二叉树的第 i 层上最多有个结点（i≥1）

性质 3：一棵深度为 k 的二叉树中，最多有 个结点，最少有k个结点。

性质 4：具有 n 个结点的完全二叉树的深度为 ⌊⌋  + 1

性质 5：对一棵具有 n 个结点的完全二叉树中从 1 开始按层序编号，对于任意的序号为 i（1≤i≤n）的结点（简称结点 i），有：

（1）如果  i＞1 ，则结点 i 的双亲结点的序号为⌊i/2⌋ ，否则结点 i 无双亲结点

（2）如果 2i≤n，则结点 i 的左孩子的序号为 2i，否则结点i 无左孩子

（3）如果 2i+1≤n，则结点 i 的右孩子的序号为2i+1，否则结点 i 无右孩子

5. 二叉树的应用：哈夫曼编码（权值最小的树）

哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。

叶子结点的权值：对叶子结点赋予的一个有意义的数值量

二叉树的带权路径长度：从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和

最优二叉树（哈夫曼树 Huffman tree）：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树

最优二叉树的特点：（1）权值越大的叶子结点越靠近根结点。（2）只有度为 0 和度为 2 的结点，不存在度为 1 的结点

哈夫曼算法：

1. 将n个叶子结点的数据存放到列表中
2. 对列表进行排序，找列表中两个权值最小的结点分别作为左右子树（两个中更小的作为左子树），创建一个新的树，新树的根的权值为左右两个子树的权值之和，并修改这三个结点的指针指向。
3. 把刚才的两个权值最小的结点从列中删除，把新的根节点加入列表
4. 重复第二第三步，直到列表中只有一个元素为止
5. 这个元素就是根，返回根节点

哈夫曼树的构造算法思想及构造过程：就是求各权值和路径相乘之后叠加的最小值。

哈夫曼编码（Huffman coding）

根据权值，画出哈夫曼树，左路标为0，右路标为1，就可得到每个元素的编码。

1. 为什么哈夫曼编码能保证字符编码总长最短?

因为哈夫曼树的带权路径长度的含义:各个字符的码长与其出现次数或频度的乘积之和，也就是电文的代码总长。

2. 为什么哈夫曼编码能保证是前缀编码?

因为在哈夫曼树中，每个字符结点都是叶子结点，它们不可能在根结点到其他字符结点的路径上。

6. 树、二叉树和森林间的转换 （左长子，右兄弟）

从物理结构上看，树的孩子兄弟表示法和二叉树的二叉链表表示法是相同的，只是解释不同的。以二叉链表作为媒介，可到处树和二叉树之间的一一对应关系。

6.1 将一棵树转换为二叉树的方法是：

（1）加线——树中所有相邻兄弟之间加一条连线

（2）去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。

（3）层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

       (二叉树根节点的右子树必为空)

6.2 将一个森林转换为二叉树的方法是

（1）将森林中的每棵树转换为二叉树

（2）将每棵树的根结点视为兄弟，在所有根结点之间加上连线（成为二叉树的右子树）

（3）按照二叉树结点之间的关系进行层次调整

6.3 二叉树转换为树（森林）

（1）加线——若某结点 x 是其双亲 y 的左孩子，则把结点 x 的右孩子、右孩子的右孩子、…，与结点 y 连线

（2）去线——删去所有双亲结点与右孩子结点的连线

（3）层次调整——整理由（1）、（2）两步所得到的树（森林），使之层次分明。