2025-8-01 15:49

Heiweilu

6530 字

28 分钟

树的定义

树（Tree） : 是 n （n>=0）个结点的有限集。n = 0 时称为空树。在任意一棵非空树中：

有且仅有一个特定的称为 根（Root） 的结点；

当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集：T(1)、T（2）…T（m)，其余每一个集合本身又是一棵树，并且称为根的 子树（SubTree)。如下图所示：

概念：

子树

根节点 A 的子树 T1、T2

❗注意：子树个数没有限制，但是一定互不相交。比如以下这个不符合树的定义：

结点的度

拥有的子树个数称为结点的 度（Degree）。树的度是树内各结点的度的最大值

度为 0 的结点称为 叶结点（Leaf） 或 终端结点。

度不为 0 的结点称为 非终端结点 或 分支结点。除根结点之外，分支结点也称为 内部结点。

下面树中，结点的度的最大值时结点 D 的度，为 3。

结点间关系

树的其他相关概念

结点的层次（Level） 从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 l 层，则其子树的根就在第 l+1 层。

其双亲在同一层的结点互为 堂兄弟。

结点的最大层次称为树的 深度（Depth） 或高度。

将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为 有序树，否则称为 无序树。

森林（Forest） 是m（m≥0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林

叶子节点：指没有子节点的节点，也称为叶节点或终端节点

树的存储结构

双亲表示法

假设以一组连续空间存储树的结点，同时在每个结点中，数据域存储结点 data 信息，指针域存储 parent (双亲)地址。

双亲表示法结点数据结构代码

#define MAX_TREE_SIZE 100
typedef int TElemType;

typedef struct PTNode /* 结点结构 */
{
    TElemType data;    /* 结点数据域 */
    int parent;        /* 双亲地址，指针域 */
}PTNode;

typedef struct  /* 树结构 */
{
    PTNode nodes[MAX_TREE_SIZE];  /* 结点数组 */
    int r, n;               /* 根的位置和结点数 */
}PTree;

因为根节点没有双亲，所以设置指针域为 -1。这样的存储结构，可以根据结点的 parent 指针很容易找到它的双亲结点，所用的时间复杂度为O(1)，直到parent = -1 为止，表示找到了树结点的根，但是如果想知道结点的孩子是什么，那要遍历整个结构才行。

我们增加一个结点最左边孩子的域，不妨叫它 长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1.
关注各兄弟之间的关系,可以增加一个右兄弟域来体现兄弟关系，同样的，如果右兄弟不存在，则赋值为-1。们还可以把此结构扩展为有双亲域、长子域、再有右兄弟域。

孩子表示法

把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点，则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。如图所示：

数据结构代码

/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100
typedef struct CTNode /* 孩子结点 */
{
    int child;
    struct CTNode *next;
} *ChildPtr;

typedef struct /* 表头结构 */
{
    TElemType data;
    ChildPtr firstchild;
} CTBox;

typedef struct /* 树结构 */
{
    CTBox node[MAX_TREE_SIZE];  /* 结点数组 */
    int r, n;                   /* 根的结点和位置 */
}CTree;

如果想知道某结点的双亲怎么办？增加一个 parent 指针域即可。

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
其中 data 是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址。

数据结构定义代码如下：

/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
    TElemType data;
    struct CSNoe *firstchild, *rightsib;
} CSNode, *CSTree;

二叉树

定义

二叉树（BinaryTree） 是 n（n≥O）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

特点

每个结点最多有两棵子树。
左子树和右子树是有顺序的，次序不能任意颠倒。
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

5种基本形态：

特殊二叉树

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。满二叉树的特点有: （1）叶子只能出现在最下一层。出现在其他层就不可能达成平衡。（2）非叶子结点的度一定是2。否则就是“缺胳膊少腿”了。（3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i

上图4棵树中，树 2，3，4分别都缺失序号，没有按照序号来生长。只有树 1是序号连续的生长，所以只有树 1 是完全二叉树。即如果编号出现空档，就说明不是完全二叉树。

性质

这里性质不用背，有个印象就行，需用到的时候再去阅读。

性质1：

二叉树的第 i 层上至多有 2^(i-1) 个结点（i≥1)

性质2：

深度为 k 的二叉树至多有 2^(k)-1 个结点（k≥1）

性质3：

任何一棵二叉树 T，如果其终端结点数为 n，度为 2 的结点数为 n_2，则n_0=n_2+1

性质4：

有个结点的完全二叉树的深度为 [log_2 n]+1（[x]表示不大于x的最大整数）。

性质5：

果对一棵有 n 个结点的完全二叉树（其深度为log2n]+1）的结点按层序编号（从第 1 层到第[log_2 n]+1 层，每层从左到右），对任一结点 i（1

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。

如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。

如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。

存储结构

顺序存储结构

二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。用一维数组存储二叉树中的结点。以下是完全二叉树的示例：
一般二叉树表示：^表示没有结点
极端情况：非常浪费空间

二叉链表

指针域 lchild 和 rchild 分别存放左孩子和右孩子的指针。

二叉链表数据结构定义：

typedef struct BiTNode /* 结点结构 */
{
    TElemType data;         /* 数据域 */
    struct BiTNode *lchild, *rchild;   /* 左右孩子指针 */
} BitNode, *BiTree;

结构示意图：

遍历二叉树

定义

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

遍历方法

1. 前序遍历

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图所示，遍历的顺序为：ABDGHCEIF。

前序遍历算法: 二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归。

/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse(BiTree T)
{
  if(T==NULL)
    return;
  printf("%c",T->data);
  PreOrderTraverse(T->lchild);
  PreOrderTraverse(T->rchild);
}

2. 中序遍历

是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如图所示，遍历的顺序为：GDHBAEICF。

中序遍历算法: 和前序遍历算法仅仅只是代码的顺序上的差异。它等于是把调用左孩子的递归函数提前了。

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
  if(T==NULL)
    return;
  InOrderTraverse(T->lchild);
  printf("%c",T->data);
  InOrderTraverse(T->rchild);
}

3. 后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图所示，遍历的顺序为：GHDBIEFCA。

/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(BiTree T)
{
  if(T==NULL)
    return;
  PostOrderTraverse(T->lchild);
  PostOrderTraverse(T->rchild);
  printf("%c",T->data);
}

4. 层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图所示，遍历的顺序为：ABCDEFGHI。

问题示例

已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历结果是多少？

首先我们知道前序遍历的中序遍历的流程区别：
如果只考虑前序遍历的结果，因为首先打印的 A，得知 A 为根节点。
由中序遍历结果 CBAEDF 和 A 为根节点可知 CB 为 A 的左子树，EDF 为 A 的右子树。如下图所示：
再由前序遍历结果 ABCDEF 可知，A 遍历右子树会先打印，右子树最先打印结果为 D，得到如下图：
最后根据中序遍历结果 CBAEDF 的 DEF 可知 D 为 E 的左子树，F 为 D 的右子树：
得到了二叉树结构图，不难推断后续遍历的结果，由后续遍历的执行流程可知，刚才推导出C是B的左孩子，而B是A的左孩子，那就意味着后序序列的前两位一定是CB。同样的办法也可以得到EFD这样的后序顺序，最终就自然的得到CBEFDA这样的序列

从这里我们也得到两个二叉树遍历的性质。

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。已知前序和后序遍历，是不能确定一棵二叉树

二叉树的建立

为了能让每个结点确认是否有左右孩子，我们对它进行了扩展，变成图右图的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，比如 “#”。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。比如AB#D##C##。

实现算法

/* 按前序输入二叉树中结点的值（一个字符）*/
/* #表示空树，构造二叉链表表示二叉树T。*/

void CreatBiTree(BiTree *T)
{
    TElemType ch;
    scanf("%c", &ch);
    if(ch == '#')
        *T=NULL;
    else
    {
        *T=(BiTree)malloc(sizeof(BiTree));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data=ch;  /* 生成根节点 */
        CreatBiTree(&(*T)->lchild); /* 构造左子树 */
        CreatBiTree(&(*T)->rchild); /* 构造右子树 */
    }
}

线索二叉树

定义

线索二叉树： 指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程称作线索化。实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

结点结构如图所示：

ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

结构实现

二叉树的线索存储结构定义代码：

/* 二叉树的二叉线索存储结构定义 */
typedef enum {Link, Thread} PointerTag; /* Link=O表示指向左右孩子指针 */
                                        /* Thread==1表示指向前驱或后继的线索 */
typedef struct BiThrNode /* 二叉线索存储结点结构 */
{
    TElemType data;     /* 结点数据 */
    struct BiThrNode *lchild, *rchild;  /* 左右孩子指针 */
    PointerTag LTag;
    PointerTag RTag;            /* 左右标志 */
}BiThrNode, *BiThrTree;

中序遍历线索化的递归函数代码：

BiThrTree pre; /* 全局变量，始终指向刚刚访问过的结点 */

/* 中序遍历进行中序线索化 */
void InThreaading(BiThrTree p )
{
    if(p)
    {
        InThreading(p->lchild);  /* 递归左子树线索化 */
        if(!p->lchild) /* 没有左孩子 */
        {
            p->LTag=Thread;     /* 前驱线索 */
            p->lchild=pre;      /* 左孩子指针指向前驱 */
        }
        if(!pre->rchild)        /* 前驱没有右孩子 */
        {
            pre->RTag=Thread;  /* 后继线索 */
            pre->rchild=p;      /* 前驱有孩子指针指向后继（当前结点p）*/
        }
        pre=p;          /* 保持pre 指向p的前驱*/
        InThreading(p->rchild);   /* 递归右子树线索化 */
    }
}

有了线索二叉树之后，还要对他进行遍历，就相当于操作一个双向链表结构。和双向链表结构一样，在二叉树线索链表上添加一个头结点，并令其 lchild 域的指针指向二叉树的根结点点（图中的①），其中 rchild 域的指针指向中序遍历时访问的最后一个结点点（图中的②）。反之，令二叉树的中序序列中的第一个结点中，lchild 域指针和最后一个结点的 rchild 域的指针均指向头结点点（图中的③和④）。这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

遍历代码：

/* T指向头结点，头结点左链 lchild 指向根结点，头结点右链 rchild 指向中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树 T */

Status InOrderTravers_Thr(BiThrTree T)
{
    BiThrTree p;
    p = T->lchild;      /* p指向根结点 */
    while(p != T)  /* 空树或遍历结束时 */
    {
        while(p->LTag==Link) /* 当LTag==0时循环到中序序列第一个结点 */
        {
            p = p->lchild;
        }
        printf("%c",p->data);   /* 显示结点数据，可以更改为其他对结点操作 */
        while(p->RTag==Thread && p->rchild !=T)
        {
            p = p->rchild;
            printf("%c",p->data);
        }
        p=p->rchild;    /* p进至其右子树根 */
    }
    return OK;
}

代码说明：

从这段代码也可以看出，它等于是一个链表的扫描，所以时间复杂度为0（n）。由于它充分利用了空指针域的空间（这等于节省了空间），又保证了创建时的一次遍历就可以终生受用前驱后继的信息（这意味着节省了时间）。所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

树、森林与二叉树的转换

树转换为二叉树

转换步骤如下：

加线。在所有兄弟结点之间加一条连线。
去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

森林转换为二叉树

森林是由若干棵树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。步骤如下：

把每个树转换为二叉树。
第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，也就是反过来做而已。如图所示。步骤如下：

加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点.哈，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。
去线。删除原二叉树中所有结点与其右孩子结点的连线。
层次调整。使之结构层次分明。

二叉树转换为森林

判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。那么如果是转换成森林，步骤如下：

从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除，直到所有右孩子连线都删除为止，得到分离的二叉树。
再将每棵分离后的二叉树转换为树即可。

赫夫曼树及其应用

赫夫曼树

美国数学家赫夫曼（DavidHuffman），也有的翻译为哈夫曼。他在1952年发明了赫夫曼编码，为了纪念他的成就，于是就把他在编码中用到的特殊的二叉树称之为赫夫曼树，他的编码方法称为赫夫曼编码。也就是说，我们现在介绍的知识全都来自于近60年前这位伟大科学家的研究成果，而我们平时所用的压缩和解压缩技术也都是基于赫夫曼的研究之上发展而来，我们应该要记住他。

赫夫曼树定义与原理

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长。

树的路径长度就是从树根到每一结点的路径长度之和。

如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有n个权值{w1，W2,…wn），构造一棵有n个叶子结点的二叉树，每个叶子结点带权Wk，每个叶子的路径长度为Ik，我们通常记作，则其中带权路径长度WPL最小的二叉树称做赫夫曼树

构造赫夫曼树的赫夫曼算法描述。

根据给定的 n 个权值 {w1，W2,…Wn} 构成 n 棵二叉树的集合 F = {T1,T2,…Tn}，其中每棵二叉树 Ti 中只有一个带权为Wi 根结点，其左右子树均为空。
在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
在 F 中删除这两棵树，同时将新得到的二叉树加入F中。
重复 2 和 3 步骤，直到 F 只含一棵树为止。这棵树便是赫夫曼树。

赫夫曼编码

一般地，设需要编码的字符集为 {d1,d2,…dn}，各个字符在电文中出现的次数或频率集合为 {w1，W2,…wn}，以 d1，d2，dn 作为叶子结点，以 W1,W2，…wn 作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表 0，右分支代表 1，则从根结点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码，这就是赫夫曼编码。

图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。

此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如表所示这样的定义。

字母	A	B	C	D	E	F
二进制字符	01	1001	101	00	11	1000

当我们接收到 1001010010101001000111100 这样压缩过的新编码时，我们应该如何把它解码出来呢？编码中非0即1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。

当我们接收到1001010010101001000111100时，由约定好的赫夫曼树可知，1001得到第一个字母是B，接下来01意味着第二个字符是A，如下图所示，其余的也相应的可以得到，从而成功解码。