数据结构——树的基本知识

一、树型结构：

1、树的基本概念

    一种表示层次关系（一对多）的数据结构
    有且只有一个特定的节点，该节点没有前驱节点，被称为根节点
    剩余n个互不相交的子集，其中每个子集也都是一棵树，都被称为根节点的子树
    注意：树型结构具有递归性（树中有树）
1
2
3
4

2、树的表示方式：

    倒悬树、嵌套法、凹凸法
1

3、树的专业术语

    节点：组成树的基础元素，同时他也是一棵树
    节点的度：该节点子树的数量
    树的度：树中节点的度的最大值
    树的密度：树中所有节点的数量
    树的深度（高度）：树的最大层次为树的深度
    节点的层次：根节点的层次为一，它的孩子层次为2，孩子的孩子层次为3，以此类推
    叶子节点：节点的度为0的节点
    双亲节点和孩子节点：节点的子树被称为该节点的孩子节点，该节点就是孩子节点的双亲节点
    兄弟节点：具有同一个双亲节点，互为兄弟节点
    堂兄弟：双亲节点互为兄弟节点
    祖先：从根节点出发，到该节点，路径上经过的所有节点都成为该节点的祖先
    子孙：一个节点的子树中任意一个节点都是它的子孙
1
2
3
4
5
6
7
8
9
10
11
12

4、树的存储

    树可以顺序存储、链式存储，还可以混合存储
    可以根据存储的信息不同，树有以下存储方式：
    	
    		双亲表示法
        	顺序存储
        	优点：方便找到双亲
        	缺点：查找孩子结点时麻烦

       		孩子表示法：
            顺序存储：浪费内存
            优点：查找孩子结点方便
            缺点：找双亲不方便

            链式存储：节约内存空间

        兄弟表示法：
            链式存储
            双亲只存储第一个子结点
            优点：可以方便找到所有的兄弟结点
            缺点：找双亲麻烦
        
注意：普通树不常用，一般会使用二叉树进行存储
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、二叉树：

是一种常用的数据结构，比普通树处理起来要简单，而且普通也比较方便地转换成二叉树
定义：节点的度最多为2
二叉树是n个有限元素的集合，该集合或者为空、或者由一个为跟（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。
在二叉树中一个元素也称为一个节点
1
2
3
4

特殊的二叉树类型：

1、满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，每层的节点树都是2^(n-1),则这棵二叉树为满二叉树。
2、完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。
完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

二叉树的性质：

性质1：二叉树的第i层上至多有2^(i-1)（i≥1）个节点。
性质2：深度为h的二叉树中至多含有2^h-1个节点。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。
性质4：具有n个节点的满二叉树深为log2n+1。
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点： 
    当i=1时，该节点为根，它无双亲节点。
    当i>1时，该节点的双亲节点的编号为i/2。
    若2i≤n，则有编号为2i的左节点，否则没有左节点。
    若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。
1
2
3
4
5
6
7
8
9

二叉树的操作：

构建、销毁、遍历、高度、密度、插入、删除、查询、求左、求右、求根
1

二叉树的存储：

    顺序存储：必须按照完全二叉树的格式，把每个节点按照从上到下、从左到右的顺序依次存入连续的内存中，如果有空位置则使用特殊数据代替存入
    数据项：
        存储节点的内存首地址
        容量
1
2
3
4

二叉树的遍历

    前序：根、左、右    ABDGCEHF
    中序：左、根、右    DGBAHECF
    后序：左、右、根    GDBHEFCA
    注意：前中后由根结点决定，并且左右子树的遍历顺序不会改变
    注意：根据  前序+中序  或者 后序+中序 就可以还原一棵树，只有 前序+后序 是无法还原的
    层序：从上到下、从左到右依次遍历一棵树  ABCDEFGH
    注意：层序遍历必须配合队列进行
1
2
3
4
5
6
7

有序二叉树

    左子树的数据小于根，右子树的数据大于等于根，这种树称为有序二叉树、二叉搜索树、二叉排序树
    注意：这种树的节点需要频繁地插入、删除，因此不适合顺序存储
    注意：插入、删除都要保证有序

    有序二叉树的中枢遍历刚好就是从小到大，所有有序二叉树也是一种排序算法，查找是二分查找
1
2
3
4
5

线索二叉树：

规律：在n个结点的链式二叉树必定有n+1个空指针域
有序链式二叉树中有很多空指针，可以让这些指针指向下一个、前一个节点，这样在遍历时可以不用递归而可以使用循环遍历，提高树的遍历速度

中序线索二叉树结点数据项：
    数据
    左子树指针 
    右子树指针 
    右子树指针的标志位（假表示真的右子树，真表示右子树指向下一个节点）

实现过程：
    1、构建有序二叉树
    2、创建线索
    3、通过线索循环遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13

选择树：（胜者树、败者树）

是一种完全二叉树，待比较的数据都存储在最后一层，根节点是根据左右子树其中一个生成，因此根节点是最大或最小的
选择树的功能是快速的找出最大值或最小值
1
2

堆：

是一种完全二叉树，不适合链式存储
大顶堆（大根堆）：根节点比左右大
小顶堆（小根堆）：根节点比左右小

数据项：
    存储数据的内存首地址
    容量
    数量
操作：创建、销毁、添加、删除、空堆、满堆
堆可以实现优先队列的效果
1
2
3
4
5
6
7
8
9
10

平衡二叉搜索树（AVL树）：

前提是有序的二叉树，它的左右子树的高度差不超过1，而且它的所有子树也满足这个条件
如果一个有序二叉树呈现接近单支状（类似链表），它的查找效率接近链表，因此只有达到平衡时它的查找效率最高
由于节点的值受限，因此只能通过调整达到有序，而不能进行值的修改
 
二叉树不平衡的基础原因：
      x                                               y   
    /   \                                           /   \
   y     t1                                        z     x          
  /       \                                       / \   / \
 z         t2           以y为轴向右旋转           t3 t4 t2  t1
/ \         
t3 t4

      x                                               y   
    /   \                                           /   \
   t1    y                                         x     z          
        / \                                       / \   / \
       t2  z         以y为轴向左旋转              t1  t2 t3 t4    
          / \
        t3   t4

      x                                               x                             z
    /   \                                           /   \                         /   \
   y     t1                                        z     t1                      y     x
  / \                                             / \                           / \   / \
 t2  z                  以z为轴向左旋转           y   t4                        t2 t3 t4 t1 
    / \                 以z为轴向右旋转          / \ 
   t3 t4                最终平衡                t2 t3

      x                                               x                                z
    /   \                                           /   \                             /  \
   t1    y                                         t1    z                           x    y    
        / \                                             / \                         / \  / \
       z   t2         以z为轴向右旋转                   t3  y                       t1 t3 t4 t2
      / \             以z为轴向左旋转                      / \
    t3   t4           最终平衡                           t4  t2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

红黑树：

也是一种自平衡的数，它不是根据子树的高度差来调整平衡的，而是给节点设置一种颜色，来达到平衡
红黑树的特性：
    1、每个节点或者是黑色，或者是红色
    2、根节点必须是黑色
    3、每个叶子节点（NULL）是黑色
    4、如果一个节点是红色，则它的子节点必须是黑色
        不能有两个连续的红色节点
    5、从一个节点到该节点的子孙节点的所有路径上包含了相同数量的黑色节点
        保证大致上红黑树是平衡的（最长路径不超过最短路径的两倍）

红黑树插入后的调整：
    插入的节点一定是红色
        1、如果父节点是黑色，直接插入
        2、如果父节点是红色，需要调整
            a、叔叔节点不存在或叔叔节点为黑色
                进行左旋或右旋
                祖父节点置红 父节点置黑
            b、叔叔存在且为红色
                把祖父置红，父节点和叔叔置黑
                把祖父节点当做当前节点，继续向上讨论调整
    
    优点：插入、删除的效率比AVL树高
    缺点：没有AVL树平均，查找效率没有AVL树高，但也并不差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

哈夫曼树：

基本概念：
    路径长度：从一个节点到另一个节点之间的路径条目数
        根节点到第n层节点的路径长度为n-1
    树的路径长度：从根节点出发到每个节点的路径长度之和
    节点的权：若将树中节点赋予一个有某种意义的数值，该数值称为该节点的权
    节点的带全路径长度：从根节点到该节点的路径长度与该节点的权的乘积
    树的带权路径长度：所有的叶子节点的带权路径长度之和，称为WPL
        WPL是衡量一颗带权二叉树优劣的标准
    
    例子：成绩划分
        成绩：<60  60~69  70~79  80~89 90~100
        等级： E    D       C       B     A
        比例： 5%   15%     40%    30%    10%
    
        普通带权二叉树的WPL： 5*1+15*2+40*3+30*4+10*4=315
        哈夫曼树的WPL：40+2*30+3*15+4*10+4*5=205
        哈夫曼树的目的是为了生成一颗WPL最小的带权二叉树

构建哈夫曼树：
    1、把n个带权节点存入一个集合F中，把每个节点左右子树置空
    2、从F中选取权值最小的两个节点作为左右子树构建成一颗新的二叉树，且新的根节点的权为左右子树的权值之和
    3、从F中删除刚刚选出来的两个节点，把新得到的根节点放入F中
    4、重复2、3步骤，直到F中只剩下一棵树，即是哈夫曼树
    
哈夫曼编码
    目的：解决当年远距离通信（电报）的数据传输最优解
    待发送的文字： BADCA DFEED
    方法1：转成二进制发送   A000 B001   共30个字符
    方法2：
        a、根据文字出现的频率，构建哈夫曼树
            假设频率：A27   B8  C15  D15  E30  F5
        b、规定哈夫曼树的左分支为0，右分支为1，则从根节点到叶子节点经过的路径分支所组成的0、1序列为该对应字符的哈夫曼编码
        哈夫曼编码：A01 B1001 C101 D00 E11 F1000
        1001010010101001000111100 共25个字符
    作用：数据压缩、文件压缩的其中一种方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35