树形结构是一类非常重要的非线性数据结构,它是以分支关系定义的层次结构。树形结构在现实世界中广泛存在,在计算机领域中也有广泛应用。

是由$n(n≥0)$个节点组成的有限集合(记为$T$)。其中:

  • 如果$n=0$,它是一棵空树,这是树的特例
  • 如果$n>0$,这$n$个节点中存在(且仅存在)一个节点作为树的根节点,简称为根节点(Root),其余节点可分为$m(m>0)$个互不相交的有限集$T1,T2,…,Tm$,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树

image-20210109160515110

image-20210109160616058

树的表示

树形表示法

树形表示法是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。

image-20210109160754374

文氏图表示法

文氏图表示法是使用集合以及集合的包含关系描述树结构。

image-20210109160850950

凹入表示法

凹入表示法是使用线段的伸缩描述树结构。

image-20210109160931971

括号表示法

括号表示法是将树的根节点写在括号的左边,除根节点之外的其余节点写在括号中并用逗号间隔来描述树结构。

image-20210109161029898

树的基本术语

节点的度与树的度

树中某个节点的子树的个数称为该节点的。树中各节点的度的最大值称为树的度,通常将度为$m$的树称为$m$次树

image-20210109161324493

分支节点与叶节点

度不为零的节点称为分支节点或非终端节点度为零的节点称为叶节点或终端节点。在分支节点中,每个节点的分支数就是该节点的度。如对于度为$1$的节点,其分支数为$1$,被称为单分支节点;对于度为$2$的节点,其分支数为$2$,被称为双分支节点,其余类推。

路径与路径长度

对于任意两个节点$k_i$和$k_j$,若树中存在一个节点序列$k_i,k_,k_,…,k_,k_j$,使得序列中除$k_i$外的任一节点都是其在序列中的前一个节点的后继,则称该节点序列为由$k_i$到$k_j$的一条路径,用路径所通过的节点序列$(k_i,k_,k_,…,k_j)$表示这条路径。

路径长度等于路径所通过的节点数目减$1$(即路径上分支数目)。

image-20210109163059422

孩子节点、双亲节点和兄弟节点

在一棵树中,每个节点的后继,被称作该节点的孩子节点(或子女节点)。相应地,该节点被称作孩子节点的双亲节点(或父母节点)

具有同一双亲的孩子节点互为兄弟节点。进一步推广这些关系,可以把每个节点的所有子树中的节点称为该节点的子孙节点

从树根节点到达该节点的路径上经过的所有节点被称作该节点的祖先节点

image-20210109171624237

节点的层次和树的高度

树中的每个节点都处在一定的层次上。节点的层次从树根开始定义,根节点为第$1$层,它的孩子节点为第$2$层,以此类推,一个节点所在的层次为其双亲节点所在的层次加$1$。树中节点的最大层次称为树的高度(或树的深度)

image-20210109171926281

有序树和无序树

若树中各节点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树

森林

$n(n>0)$棵互不相交的树的集合称为森林。把含有多棵子树的树的根节点删去也就成了森林。反之,只要给$m(m>1)$棵独立的树加上一个节点,并把这$m$棵树作为该节点的子树,则森林就变成了树。

image-20210109172140022

树的性质

  • 树中的结点数等于所有结点的度数之和加$1$
  • 度为$m$的树中第$i$层上最多有$m^(i≥1)$个结点。
  • 高度为$h$的$m$次树最多有$\frac{m^h-1}$个结点
  • 具有$n$个结点的$m$次树的最小高度为$\lceil log_m(n(m-1)+1) \rceil$

树的基本运算

树的遍历

树的遍历运算是指按某种方式访问树中的每一个节点且每一个节点只被访问一次

有以下三种遍历方式:

  • 先序遍历(或先根遍历):若树不空,则先访问根节点,然后再按照从左到右的顺序依次先序遍历根结点的各棵子树。
  • 后序遍历(或后根遍历):若树不空,则按照先从左到右的顺序依次后序遍历根结点的各棵子树,然后再访问根节点
  • 层次遍历:若树不空,则从根结点开始按从上到下从左到右的次序访问树中每个节点。

先序和后序遍历算法都是递归的。

image-20210109173833439

  • 先序遍历的节点访问次序:A B E F C D G H I J K

  • 后序遍历的节点访问次序:E F B C I J K H G D A

  • 层次遍历的节点访问次序:A B C D E F G H I J K

树的存储结构

双亲存储结构

这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有节点,同时在每个节点中附设一个伪指针指示其双亲节点的位置。

image-20210109174423416

双亲存储结构的类型声明如下:

#define ElemType int
#define MaxSize 10
typedef struct
{
    ElemType data;  // 节点的值
    int parent;     // 指向双亲的位置
} PTree[MaxSize];

孩子链存储结构

这种存储结构是一种链式存储结构,可按树的度(即树中所有节点度的最大值)设计链式节点中孩子节点指针域的个数。

image-20210109175052368

孩子链存储结构的节点类型声明如下:

#define MaxSons 3
typedef struct node
{
    ElemType data;              // 节点的值
    struct node *sons[MaxSons]; // 指向孩子节点
} TSonNode;

MaxSons为最多的孩子节点个数。

孩子兄弟链存储结构

这种存储结构是一种链式存储结构,为每个节点设计三个域:

  • 数据元素域
  • 该节点的第一个孩子节点指针域
  • 该节点的下一个兄弟节点指针域

image-20210109175832235

typedef struct TNode
{
    ElemType data;      // 节点的值
    struct TNode *hp;   // 指向兄弟
    struct TNode *vp;   // 指向孩子节点
} TSBNode;

每个节点固定只有两个指针域。

二叉树

二叉树是有限的节点集合,这个集合或者是空的,或者是由一个根节点和最多两棵互不相交的称为左子树右子树的二叉树组成。

二叉树的定义是一种递归定义。

二叉树的五种基本形态:

image-20210109182712208

二叉树的基本术语

满二叉树

在一棵二叉树中,如果所有分支节点都有左孩子节点和右孩子节点,并且叶节点都集中在二叉树的最下一层,这样的二叉树称为满二叉树

image-20210109183119035

完全二叉树

若二叉树中最多只有最下面两层的节点的度数可以小于$2$,并且最下面一层的叶节点都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树

image-20210109183314653

二叉树的性质

  • 非空二叉树上叶结点数等于双分支结点数加$1$(即:$n_0=n_2+1$)
  • 非空二叉树上第$i$层上至多有$2^$个结点$(i≥1)$
  • 高度为$h$的二叉树至多有$2^h-1$个结点$(h≥1)$

![image-20210109184641248](../../../Library/Application Support/typora-user-images/image-20210109184641248.png)

  • 完全二叉树中编号为$i$的结点$(1≤i≤n,n≥1,n为结点数)$有:
    1. 若$i≤ \lfloor n/2 \rfloor$,即$2i≤n$,则编号为$i$的结点为分支结点,否则为叶子结点
    2. $n$为奇数:则每个分支结点均有左、右孩子结点。n为偶数:则编号最大的分支结点(编号为$n/2$)只有左孩子结点,没有右孩子结点,其余分支结点都有左、右孩子结点
    3. 若编号为$i$的结点有左孩子结点,则左孩子结点的编号为$2i$,若编号为$i$的结点有右孩子结点,则右孩子结点的编号为$2i+1$
    4. 除树根结点外,若一个结点的编号为$i$,则它的双亲结点的编号为$\lfloor i/2 \rfloor$
  • 具有$n$个$(n>0)$结点的完全二叉树的高度为$\lceil log_2n+1 \rceil$或$\lfloor log_2n \rfloor +1$

image-20210109185340046

二叉树与树、森林之间的转换

树转换成二叉树

  • 加线:在兄弟之间加一连线

  • 抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的关系

  • 旋转:以树的根结点为轴心,将水平线顺时针旋转45°

image-20210109191431515

树转换成的二叉树其右子树一定为空

森林转换成二叉树

  • 将各棵树分别转换成二叉树
  • 将每棵树的根结点用线相连
  • 以第一棵树根结点为二叉树的根,再以根结点为轴心,顺时针旋转,构成二叉树型结构

image-20210109192342510

二叉树转换成树

  • 加线:若$p$结点是其双亲结点的左孩子,则将$p$的右孩子,右孩子的右孩子,……沿分支找到的所有右孩子,都与$p$的双亲用线连起来
  • 抹线:抹掉原二叉树中双亲与右孩子之间的连线
  • 调整:将结点按层次排列,形成树结构

image-20210109192613532

二叉树转换成森林

  • 抹线:将二叉树中根结点与其右孩子连线,及沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树
  • 还原:将孤立的二叉树还原成树

image-20210109192739736

二叉树的存储结构

顺序存储结构

二叉树的顺序存储结构就是用一组地址连续的存储单元来存放二叉树的数据元素。

节点的存放次序是:对二叉树中每个节点进行编号,其编号从小到大的顺序就是节点存放在连续存储单元的先后次序。

image-20210109193359645

一般的二叉树先用空节点补全成为完全二叉树,然后对节点编号。

image-20210109193500363

链式存储结构

二叉链表是二叉树的链式存储结构,节点的结构如下:

typedef struct Node
{
    ElemType data;
    struct Node *lchild, *rchild;
} BTNode;

其中,data表示值域,用于存储对应的数据元素;lchildrchild分别表示左指针域和右指针域,分别用于存储左孩子节点右孩子节点(即左、右子树的根节点)的存储地址

image-20210109193835854

image-20210109193928511

二叉树的基本运算

建立二叉树

ch扫描采用括号表示法表示的二叉树字符串strA(B(D(,G)),C(E,F))

分以下几种情况:

  • ch == '(':则将前面刚创建的节点作为双亲节点进栈,并置k=1,表示其后创建的节点将作为这个节点的左孩子节点
  • ch == ')':表示栈顶节点的左右孩子节点处理完毕,退栈
  • ch == ',':表示其后创建的节点为栈顶节点的右孩子节点,置k=2
  • 其他情况:只能是单个字符,需要创建一个节点P存放该节点的值,且
    1. k == 1时,表示P节点作为栈顶节点的左孩子节点
    2. k == 2时,表示P节点作为栈顶节点的右孩子节点

如此循环直到str处理完毕。

// 建立二叉树
void createBTree(BTNode *&b, char *str)
{
    BTNode *St[MaxSize], *p = NULL;
    int top = -1, k, j = 0;
    char ch;
    b = NULL;               // 建立的二叉树初始时为空
    ch = str[j];
    while (ch != '\0')      // str未扫描完时循环
    {
        switch (ch)
        {
            case '(':
                top++;
                St[top] = p;
                k = 1;      // 为左孩子节点
                break;
            case ')':
                top--;
                break;
            case ',':
                k = 2;      // 为孩子节点右节点
                break;
            default:
                p = (BTNode *) malloc(sizeof(BTNode));
                p->data = ch;
                p->lchild = p->rchild = NULL;
                if (b == NULL) b = p;   // p为二叉树的根节点
                else                    // 已建立二叉树根节点
                {
                    switch (k)
                    {
                        case 1:
                            St[top]->lchild = p;
                            break;
                        case 2:
                            St[top]->rchild = p;
                            break;
                    }
                }
        }
        j++;
        ch = str[j];
    }
}

算法中使用一个栈St保存双亲节点,top为栈顶指针,k指定其后处理的节点是双亲节点(保存在栈中)的左孩子节点(k == 1)还是右孩子节点( k == 2)

image-20210109195850271

销毁二叉树

f(b)的功能是释放为二叉树b​中的所有节点分配的空间,其递归模型为:

  • f(b)=不做任何事情 (若b=NULL)
  • f(b)=f(b->lchild); f(b->rchild); 释放b所指节点; (其他情况)
// 销毁二叉树
void destroyBTree(BTNode *&b)
{
    if (b != NULL)
    {
        destroyBTree(b->lchild);
        destroyBTree(b->rchild);
        free(b);
    }
}

查找节点

采用递归算法查找值为x的节点。找到后返回其指针,否则返回NULL

// 查找节点
BTNode *findNode(BTNode *b, ElemType x)
{
    BTNode *p;
    if (b == NULL) return NULL;
    else if (b->data == x) return b;
    else
    {
        p = findNode(b->lchild, x);
        if (p != NULL) return p;
        else return findNode(b->rchild, x);
    }
}

image-20210109201712047

查找孩子节点

// 查找左孩子节点
BTNode *lchildNode(BTNode *p)
{
    return p->lchild;
}

// 查找右孩子节点
BTNode *rchildNode(BTNode *p)
{
    return p->rchild;
}

求二叉树高度

求二叉树的高度的递归模型f(b)如下:

  • f(b)=0 (b=NULL)
  • f(b)=MAX{f(b->lchild),f(b->rchild)}+1 (其他情况)
// 获取二叉树高度
int getHeight(BTNode *b)
{
    int lchildH, rchildH;
    if (b == NULL) return 0; // 空树的高度为0
    else
    {
        lchildH = getHeight(b->lchild);
        // 求左子树的高度为lchildH
        rchildH = getHeight(b->rchild);
        // 求右子树的高度为rchildH
        return (lchildH > rchildH) ?
               (lchildH + 1) : (rchildH + 1);
    }
}

遍历二叉树

二叉树的遍历是指按照一定次序访问树中所有节点,并且每个节点仅被访问一次的过程。它是最基本的运算,是二叉树中所有其他运算的基础。

一般使用三类遍历方式:

  • 先序遍历(NLR、NRL)
  • 中序遍历(LNR、RNL)
  • 后序遍历(LRN、RLN)

采用先序遍历的方式打印二叉树:

// 打印二叉树
void printBTree(BTNode *b)
{
    if (b != NULL)
    {
        printf("%c", b->data);
        if (b->lchild != NULL || b->rchild != NULL)
        {
            printf("(");
            printBTree(b->lchild);  // 递归处理左子树
            if (b->rchild != NULL) printf(",");
            printBTree(b->rchild);  // 递归处理右子树
            printf(")");
        }
    }
}

哈夫曼树

二叉树具有$n$个带权值的叶子节点,那么从根节点到各个叶子节点的路径长度与相应节点权值的乘积的和,叫做二叉树的带权路径长度(WPL)
$$
WPL=\sum_
^n w_i l_i
$$
其中$n$表示叶子节点的数目,$w_i$和$l_i$分别表示叶子节点$k_i$的权值和根到$k_i$之间的路径长度(即从叶子节点到达根节点的分支数)。

image-20210110204612905

具有最小带权路径长度的二叉树称为哈夫曼树(Huffman Tree)

根据哈夫曼树的定义,一棵二叉树要使其$WPL$值最小,必须使权值越大的叶子节点越靠近根节点,而权值越小的叶子节点越远离根节点。

构造一棵哈夫曼树的方法如下:

  1. 给定的$n$个权值${W_1,W_2,...,W_n}$构造$n$棵只有一个叶子节点的二叉树,从而得到一个二叉树的集合$F={T_1,T_2,...,T_n}$
  2. 在$F$中选取根节点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树,这棵新的二叉树根节点的权值为其左、右子树根节点权值之和
  3. 在集合$F$中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到集合$F$中
  4. 重复2、3两步,当$F$中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树
image-20210110205309611

在哈夫曼树中,一定没有度为$1$的结点,因此有$n$个叶子结点的哈夫曼树,一定有$2n-1$个结点。

为了实现构造哈夫曼树的算法,用ht[ ]数组存放哈夫曼树,哈夫曼树中每个节点的类型如下:

typedef struct
{
    char data;       // 节点值
    float weight;    // 权重
    int parent;      // 双亲节点
    int lchild;      // 左孩子节点
    int rchild;      // 右孩子节点
} HTNode;

其算法思路是:

  1. $n$个叶子节点(存放在ht[0]ht[n-1]中)只有dataweight域值,先将所有$2n-1$个节点的parentlchildrchild域置为初值$-1$。
  2. 处理每个非叶子节点ht[i](存放在ht[n]ht[2n-2]中):从ht[0]ht[i-1]中找出根节点(即其parent域为$-1$)最小的两个节点ht[lnode]ht[rnode],将它们作为ht[i]的左右子树,ht[lnode]ht[rnode]的双亲节点置为ht[i],并且ht[i].weight = ht[lnode].weight + ht[rnode].weight
  3. 如此这样直到所有$n-1$个非叶子节点处理完毕。
// 建立哈夫曼树
void createHT(HTNode ht[], int n0)
{
    int i, k, lnode, rnode;
    float min1, min2;
    for (i = 0; i < 2 * n0 - 1; i++)        // 所有节点的相关域置初值-1
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    for (i = n0; i < 2 * n0 - 1; i++)       // 构造哈夫曼树
    {
        min1 = min2 = 32767;
        lnode = rnode = -1;
        for (k = 0; k <= i - 1; k++)
            if (ht[k].parent == -1)         // 未构造二叉树的节点中查找
            {
                if (ht[k].weight < min1)
                {
                    min2 = min1;
                    rnode = lnode;
                    min1 = ht[k].weight;
                    lnode = k;
                }
                else if (ht[k].weight < min2)
                {
                    min2 = ht[k].weight;
                    rnode = k;
                }
            }
        ht[lnode].parent = i;
        ht[rnode].parent = i;
        ht[i].weight = ht[lnode].weight + ht[rnode].weight;
        ht[i].lchild = lnode;
        ht[i].rchild = rnode;
    }
}
image-20210110205920130