飞鸿踏雪

《数据结构》树与二叉树

树

树的基本概念

  • 定义
    • 树是一种数据结构，它是由n个有限节点组成一个具有层次关系的集合
  • 特点
    • 每个节点有零个或多个子节点
    • 没有父节点的节点称为根节点
    • 每一个非根节点有且只有一个父节点
    • 除了根节点外，每个子节点可以分为多个不相交的子树
  • 结构图
  • 树的高度、深度、层
    • 节点的高度 = 节点到叶子节点的最长路径
    • 节点的深度 = 根节点到这个节点所经历的边的个数
    • 节点的层数 = 节点的深度 + 1
    • 树的高度 = 根节点的高度
  • 树的基本术语
    • 节点的度：节点拥有的子树的数目
    • 叶子：度为零的结点
    • 分支结点：度不为零的结点
    • 树的度：树中结点的最大的度
    • 层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1
    • 树的高度：树中节点的最大层次
    • 无序树：树中结点的各子树之间的次序是不重要的，可以交换位置
    • 无序树：树中结点的各子树之间的次序是重要的，不可以交换位置
    • 森林：0个或多个不相较的树组成
  • 树的性质
    • 树的节点数 = 所有节点的度数之和 + 1
    • 度为m的树中第i层上最多有$m^{i-1}$个结点
    • 已知度m和高度h
      • 求树的最少节点数
        • 让1~h-1层节点数都为1，最后一层节点数为m
      • 求树的最多结点数
        • 让树成为满m叉树

树的存储结构/树的表示

  • 双亲表示法
    • 采用一组连续空间来存储每个节点
    • 在每个节点中设置一个伪指针
    • 尾指针指示器双亲节点在数组中的位置
  • 孩子表示法
    • 将每个节点的孩子节点用单链表连接
  • 孩子兄弟表示法
    • 又叫二叉树表示法
    • 以二叉链表作为树的存储结构
    • 节点内容包含3个部分
      • 孩子节点
      • 数据
      • 兄弟节点

树林和二叉树的转换

  • 树与二叉树
    • 在兄弟节点之间加一连线
    • 对每个节点，只保留它与第一个孩子的连线
    • 以树根为轴心，顺时针旋转45度
  • 树、树林与二叉树
    • 将森林中的每棵树转换成相应的二叉树
    • 每棵树的根也可以视为兄弟关系，在每棵树之间加一根连线
    • 以第一棵树的根为轴心旋转45

树和森林的遍历对应关系

树 森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历

二叉树

基本概念

  • 定义
    • 二叉树是每个节点最多有两个子树的树结构
    • 有五个基本形态
      • 二叉树可以是空集
      • 根可以有空的左子树或右子树
      • 左、右子树皆为空
  • 性质
    • 二叉树第i层上的节点数目最多为$2^{i-1}$
    • 深度为k的二叉树最多有$2^k-1$个节点（满二叉树）
    • 包含n个节点的二叉树的高度至少为$log_2(n+1)$
    • 树的节点数 = 所有节点的度数之和 + 1
    • 在任意一颗二叉树中，若终端节点的个数为$n_0$,度为2的节点为$n_2$,则$n_0 = n_2 + 1$

特殊的二叉树

  • 满二叉树
    • 高度为h，并且有$2^h -1$个结点的二叉树
  • 完全二叉树
    • 叶子结点只能出现在最下层和次下层，最下层的叶子结点集中在树的左部
    • 一棵满二叉树必定是一棵完全二叉树
    • 完全二叉树未必是满二叉树
    • 完全二叉树中，度为1的节点数 = 0个或者1个
  • 二叉查找树
    • 左子树节点比根节点值小
    • 右子树节点比根节点值大
    • 左右子树页分别为二叉查找树
  • 平衡二叉树
    • 树上任一结点的左子树和右子树的深度值差不超过1

二叉树的存储结构

  • 顺序存储结构
    • 定义
      • 一般用数组存二叉树的节点
      • 只要知道根节点的存储位置，就可以通过下标计算，把整棵树串起来
    • 特点
      • 节点x存储在下标为i的位置
      • 该节点的左节点存储在下标为2i的位置
      • 该节点的右节点存储在下标为2i+1的位置
      • 下标i/2的位置，存储的就是该节点的父节点
      • 空间利用率不高，容易造成空间浪费
    • 适用
      • 完全二叉树
      • 满二叉树
    • 结构图
  • 链式存储结构
    • 定义
      • 只要知道根节点，就可以通过左右子节点的指针把整棵二叉树串起来
    • 特点
      • 二叉链表中至少包含3个域
        • 数据域data
        • 左指针lchild
        • 右指针rchild
    • 适用于
      • 二叉树
    • 结构图

二叉树的实现

二叉树的代码表示

1
2
3
4
5
6
7
8


typedef struct TreeNode *BinTree;
struct TreeNode
{
    int Data;//存值
    BinTree Left//左儿子结点
    BinTree Right //右儿子结点
}

二叉树的三种遍历方法

前序

根节点->左节点->右节点

递归代码

1
2
3
4
5
6
7
8
9

void PreOrderTraversal(BinTree BT)
{
    if(BT)
    {
        printf("%d",BT->Data);//打印根
        PreOrderTraversal(BT->Left);//进入左子树
        PreOrderTraversal(BT->Right);//进入右子树
    }
}

非递归代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void PreOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack S = CreateStack();//创建并初始化堆栈S
    while (T||!IsEmpty(S))
    {//当树不为空或堆栈不空
        while(T)
        {
            Push(S,T);//压栈，第一次遇到该结点
            printf("%d",T->Data);//访问结点
            T = T->Left;//遍历左子树
        }
        if(!IsEmpty(S))
        {//当堆栈不空
            T = Pop(S);//出栈，第二次遇到该结点
            T = T->Right;//访问右结点
        }
    }
}

中序

左节点->根节点->右节点

递归代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void InOrderTraversal(BinTree BT)
{
    if(BT)
    {
        InOrdeerTraversal(BT->Left);//进入左子树
        printf("%d",BT->Data);//打印根
        InOrderTraversal(BT->Right);//进入右子树

    }
}

非递归代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void InOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack S = CreatStack();//
    while(T||!IsEmpty(S))
    {
        while(T)
        {
            Push(S,T);
            T = T->Left;
        }
        if(!IsEmpty(S))
        {
            T = Pop(S);
            printf("%d",T->Data);
            T = T->Right;
        }
    }
}

后序

左节点->右节点->根节点

递归方式

1
2
3
4
5
6
7
8
9

void PostOrderTraversal(BinTree BT)
{
    if(BT)
    {
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d.BT->Data");
    }
}

非递归方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void PostOrederTraversal(BinTree BT )
{
    BinTree T = BT;
    Stack S = CreateStack();
    vector<BinTree> v;
    Push(S,T);
    while(!IsEmpty(S))
    {
        T = Pop(S);
        v.push_back(T);
        if(T->Left)
            Push(S,T->Left);
        if(T->Right)
            Push(S,T->Right);
    }
    reverse(v.begin(),v.end());
    for(int i = 0; i < v.size();i++)
        printf("%d",v[i]->Data);
}

层序遍历

从上至下，从左往右访问所有结点

基于队列实现过程

  1. 根结点入队
  2. 从队列中取出一个元素
  3. 访问该元素所指结点
  4. 若该元素所指结点的左孩子结点非空，左孩子结点入队
  5. 若该元素所指结点的右孩子结点非空，右孩子结点入队
  6. 循环2-4，直到队列中为空

非递归方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void LevelOrderTraversal(BinTree BT)
{
    queue<BinTree> q;
    BinTree T;
    if(!BT)
        return;
    q.push(BT);
    while(!q.empty())
    {
        T = q.front();
        q.pop();
        printf("%d",T->Data);
        if(T->Left)
            q.push(T->Left);
        if(t->Right)
            q.push(T->Right);
    }
}

三种遍历示例

(01) 前序遍历结果 ： 3 1 2 5 4 6 (02) 中序遍历结果 ： 1 2 3 4 5 6 (03) 后序遍历结果 ： 2 1 4 6 5 3

常考结论

  • 不能由唯一序列确定二叉树的是
    • 先序序列和后序序列
  • 先序遍历第一个节点为根节点；后序遍历最后一个节点位根节点
  • 前序序列与后序序列的关系相当于以前序列序列为入栈次序，以中序序列为出栈顺序
  • 前序序列与后序序列刚好相反的时候，二叉树的高度 = 节点数（即每层只有一个节点）
  • 后序遍历可以找到m到n的路径（其中m是n的祖先）
  • 根据两个序列确定二叉树的方法

线索二叉树

基本概念和参考点

  • 对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫做线索化
  • 线索二叉树是一种物理结构
  • 引入线索的目的是加快对二叉树的遍历
  • n个节点的线索二叉树上含有线索数量为n + 1 个
  • 线索二叉树就是利用二叉树的n + 1个空指针来存放节点的前驱和后继信息的
  • 后续线索二叉树不能有效解决求后续后继的问题，后续线索树的遍历仍需要栈的支持

节点结构

lchild ltag data rtag rchild
指针域 标识域 数据域 标识域 指针域
  • ltag = 0,表示指向节点的左孩子
  • ltag = 1，则表示lchild为线索，指向节点的直接前驱
  • rtag = 0,表示指向节点的右孩子
  • rtag = 1,则表示rchild为线索，指向节点的直接后继

中序线索化的过程

（前序和后序的线索化只需要将遍历方法改为前序或后序即可）

  1. 对二叉树进行中序遍历
  2. 节点右子节点为空的指针域指向它的后继节点
  3. 节点左子节点为空的指针域指向它的前驱节点

树和二叉树的应用

哈夫曼树/最优二叉树

  • 定义
    • 树的带权路径长度最小的二叉树
    • WPL = 路径长度 * 结点权值
  • 特点
    • 没有度为1的结点
    • n个叶结点的哈夫曼树共有2n-1个结点
    • 哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树
    • 对同一组权值，可能存在不同构的多棵哈夫曼树
    • 哈夫曼树不一定是完全二叉树
  • 构造
    • 每次把队列中值最小的合并，合并后的值加入队列中再继续比较
  • 例题

哈夫曼编码

  • 概念
    • 前缀编码：一个编码是另一个编码的前缀的编码
    • 如下图哈夫曼树中“I”的编码为00，“u”的编码为1100等等
    • 出现频率越高的字符越会在上层，这样它的编码越短
    • 出现频率越低的字符越会在下层，编码越短
    • 经过这样设计，最终整个文本存储空间才会最大化的缩减
    • 得到下哈夫曼编码图的编码表之后
    • 'we will we will r u'这句重新进行编码就可以得到很大的压缩
    • 01 110 10 01 1111 00 00 10 01 110 10 01 111 00 00 10 11101 10 1110
    • 最终只需50位内存，比ascii码表示节省了2/3空间

最终编码表

字符 i w '' e i u r
编码 00 01 10 110 1111 11100 11101

并查集

  • 定义
    • 并查集是一种简单的集合表示，支持3种操作
    • 并查集的存储结构是双亲表示法存储的树，主要是为了方便两个主要的操作
  • 例题

并查集操作

Initial(S)
  • 将集合S中的每个元素都初始化为只有一个单元数的子集合
1
2
3
4
5

void Initial(int S[])
{
    for(int i = 0; i < size ; i++)
        S[i] = -1;
}

Union(S,Root1,Root2)
  • 把集合S中的子集合Root2并入子集合Root1
  • 要求Root1和Root2互不相交，否则不执行合并
1
2
3
4

void Union(int S[],int Root1,int Root2)
{
    S[Root2] = Root1;
}

Find(S,x)
  • 查找集合S中单元素x所在的子集合，并返回该子集合的根结点
1
2
3
4
5
6

int Find(int S[],int x)
{
    while(S[x] >=0)
        x = S[x];
    return x;
}