【数据结构导论】第四章-树和二叉树

发表于 更新于 分类于 本文字数： 2k 阅读时长 ≈ 7 分钟

树结构、森林

树的基本概念

树（Tree）是 n （n >= 0）个结点的有限集合。

一棵树满足下列两个条件：

(1) 当 n = 0 时，称为空树

(2) 当 n > 0 时，有且仅有一个称为根的结点，除根结点外，其余结分为 m(m >= 0)个互不相交的非空集合 T1 , T2 , … , Tm ，这些合中的每一个集合都是一棵树，称为根的子树。

术语

结点的度：树上任意结点所拥有的子树的数目称为该结点的度。

叶子：度为 0 的结点称为叶子或终端结点。

树的度：一棵树中所有结点的度的最大值称为该树的度。

结点的层次：从根开始算起，根的层次为 1，其余结点的层次为其双亲的结层次加 1。

树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度。

有序树：若树中各结点的子树从左到右是有次序的，不能转换，称为有序树。

无序树：若树中各结点的子树是无次序的，可以转换，则成为无序树。

森林基本概念

森林(Forest) m(m >= 0)棵互不相交的树的集合。树的每个结点的子树是林。删除一个非空树的根结点，它的子树便构成森林。

树的基本运算

(1) 求根 Root(T)：求树 T 的根节点;

(2) 求双亲 Parent(T,X)

(3) 求孩子 Child(T,X,i)

(4) 建树 Create(X,T1,…,Tk); k > 1;

(5) 剪枝 Delete(T,X,i)

(6) 遍历 TraverseTree(T)

二叉树

二叉树的概念

二叉树(Binart Tree)是n ( n >= 0)个元素的有限集合。

左子树、右子树

二叉树的任一结点都有两棵子树（它们中的任何一个都可以是空子树），并这两棵子树之间有次序关系，即如果互换了位置则成为两棵不同的二叉树。叉树上任一结点左右子树的根分别称为该结点的左孩子和右孩子。

二叉树的基本运算

  1. 初始化 Initiate(BT)：建立一棵空二叉树

  2. 求双亲 Parent(BT,X)：求出二叉树上结点 X 的双亲结点

  3. 求左孩子 Lchild(BT,X)，求右孩子 Rchild(BT,X)：分别求二叉树 BT 上结点 X 的左、右孩子

  4. 建二叉树 Create(BT)：建立一棵二叉树 BT

  5. 先序遍历 PreOrder(BT)：按先序对二叉树进行遍历

  6. 中序遍历 InOrder(BT)：按中序对二叉树进行遍历

  7. 后序遍历 PostOrder(BT)：按后序对二叉树进行遍历

  8. 层次遍历 LevelOrder(BT)：按层从上往下，同一层中结点按从往右的顺序，对二叉树进行遍历

二叉树的性质

性质 1：二叉树的第 i (I >= 1)层上至多有 2i - 1 个结点

性质 2：深度为 k (k >= 1)的二叉树至多有 2k - 1 个结点

性质 3：对任何一棵二叉树，若度数为 0 的结点（叶节点）个数为 n0 ，数为 2 的结点个数为 n2 ，则 n0 = n2 + 1

性质 4：含有n个结点的完全二叉树的深度为 (log2n) + 1

性质 5：如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i结点A有：
(1) 若 i = 1，则结点A是根：若i > 1，则A的双亲 Parent(A) 的编号为 [i/2] ;

(2) 若 2 * i > n，则结点A既无左孩子，也无右孩子；否则A的左孩子Lchild(A)的编号为2 * i ;

(3) 若 2 * i + 1 > n，则结点A无右孩子；否则A的右孩子 Rchild(A) 的编号为 2 * i + 1 ;

二叉树顺序存储

二叉树的顺序存储结构可以使用一维数组实现，根据二叉树的性质 5，采用编号作为数组的下标，将结点存入数组中。

对于非完全二叉树，需要增设若干个虚拟结点将其转化为完全二叉树。各个拟结点在数组中用特殊符号”^”表示。

二叉树链式存储及类 C 语言描述

二叉树最常用的链式存储结构有二叉链表和三叉链表。

二叉链表类 C 语言描述：

1
2
3
4
5
6
typedef struct btnode
{
    DataType data;
    struct binode *lchild, *rchild; //指向左右孩子的指针
} * BinTree;
BinTree root;

三叉链表类 C 语言描述：

1
2
3
4
5
6
typedef struct ttnode
{
    DataType data;
    struct ttnode *lchild, *parent, *rchild;
} * TBinTree;
TBinTree root;

二叉树的遍历算法

  • 先序遍历
1
2
3
4
5
6
7
8
9
void preorder(BinTree bt)
{
    if (bt != NULL)
    {
        visit(bt);            //访问根节点
        preorder(bt->lchild); //先序遍历左子树
        preorder(bt->rchild); //先序遍历右子树
    }
}
  • 中序遍历
1
2
3
4
5
6
7
8
9
void inorder(BinTree bt)
{
    if (bt != NULL)
    {
        inorder(bt->lchild); //中序遍历左子树
        visit(bt);           //访问根结点
        inorder(bt->rchild); //中序遍历右子树
    }
}
  • 后序遍历
1
2
3
4
5
6
7
8
9
void postorder(BinTree bt)
{
    if (bt != NULL)
    {
        postorder(bt->lchild); //后序遍历左子树
        postorder(by->rchild); //后序遍历右子树
        visit(bt);             //访问根结点
    }
}
  • 树结点数计算
1
2
3
4
5
6
int count(BinTree bt)
{
    if (bt == NULL)
        return 0;                                     //空树返回0
    return count(bt->lchild) + count(bt->rchild) + 1; //左子+右子树+根结点
}
  • 树深度计算
1
2
3
4
5
6
7
8
9
int height(BinTree bt)
{
    int lh, rh; //初始左右子树高度为0
    if (bt == NULL)
        return 0;
    lh = height(bt->lchild); //左子树高度
    rh = height(bt->rchild); //右子树高度
    return 1 + (lh > rh ? lh : rh);
}

树和森林

树的先序、后序和层次遍历方法

  • 先序遍历，若树非空，则：

    1. 访问根结点
    2. 依次先序遍历根的各棵子树

  • 后序遍历，若树非空，则：

    1. 依次后序遍历根的各棵子树
    2. 访问根结点

  • 层次遍历

    1. 若树非空，访问根结点
    2. 若第 i 层结点已经访问，第 i + 1 层结点尚未访问，则从左到右依次访问第 i + 1 层结点

森林的先序遍历方法

若森林非空，则：

(1) 访问森林中第一棵树的根结点

(2) 先序遍历第一棵树的根结点的子树组成的森林

(3) 先序遍历出去第一棵树之外其余的树组成的森林

森林的中序遍历方法

若森林非空，则：

(1) 中序遍历森林中第一棵树的根结点的子树组成的森林

(2) 访问第一棵树的根结点

(3) 中序遍历出去第一棵树之外其余的树组成的森林

树、森林与二叉树的关系

  • 树与二叉树可以互相转换
  • 森林和二叉树可以互相转换

树转换成二叉树的方法

(1) 将所有兄弟结点连接起来

(2) 保留第一个兄弟结点与父结点的连接，断开其他兄弟结点与父结点的连接，然后以根结点为轴心顺时针旋转 45° 角

森林转换成二叉树的方法

(1) 将每棵树转换成相应的二叉树

(2) 将（1）得到的各棵二叉树的根结点看作是兄弟连接起来

二叉树转换成对应森林的方法

(1) 断开根结点与右孩子的连接线，得到二叉树 T1 和 T2

(2) 连接 T1 的根结点与左子树的右子树

(3) 重复(1)(2)将 T2 转换成对应的森林

判定树和哈夫曼树

判定树的概念

分类运算的作用是将输入数据按预定的标准划分成不同的种类，用于描述分类过程的二叉树称为判定树。

哈夫曼树的概念

给定一组值 P1,… ,Pk,如何构造出有k个叶子且以这些值为权的判定树，使得其平均比较次数为最小。满足上述条件的判定树称为哈夫曼（Huffman）树。

哈夫曼编码

对哈夫曼树每个结点的左分支和右分支分别置“0”或“1”，就可以得到哈弗曼编码。

哈夫曼树构造过程和哈夫曼算法

每次合并具有最小权值和次小权值的两个根结点，直到只剩一个根结点为止。