小乐趣

数据结构：树与二叉树

树是由 $n$ $(n>0)$ 个结点的有限集合。如果 $n=0$，称为空树；如果 $n>0$，则

  1. 有且仅有一个根结点，它没有直接前驱。
  2. 当 $n>1$，除根结点以外的其他结点划分为 $m$ $(m>0)$ 个互不相交的有限集 $T_1, T_2, \cdots , T_m$，其中每个集合本身又是一棵树，并且称为根的子树。

由树的性质可知，树的结构具有递归性。

树的基本概念

基本概念 含义
结点 一个数据元素及其指向结点的分支
度 结点拥有的子树个数
叶结点 度为 $0$ 的节点
子女 结点子树的根
兄弟 同一个结点的子女
祖先 根结点到该结点路径上的所有结点
子孙 某结点为根结点的子树上的任意结点
层 以根结点为第一层，根结点的子女为第二层，以此类推
树的深度 树中结点的最大层数
有序树 树中结点的子树从左向右有序
森林 $m$ $(m \geqslant 2)$ 棵互不相交的树

二叉树

二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上互不相交的左右子树。

二叉树具有以下性质：

  1. 在二叉树的第 $i$ $(i \geqslant 1)$ 层上至多有 $2^{i-1}$ 个结点。
  2. 深度为 $k$ $(k \geqslant 1)$ 的二叉树至多有 $2^{k-1}$ 个结点。
  3. 对任意一个二叉树 $T$，如果其叶结点数为 $n_0$，度为 $2$ 的结点数为 $n_2$，则 $n_0 = n_2 + 1$。
  4. 拥有 $n$ $(n \geqslant 0)$ 个结点的完全二叉树的深度为 $\left[ \log_{2}(n)\right] + 1$

二叉树的存储

  1. 顺序存储
  2. 链式存储
1
2
3
4
5
6
7
8
9

/* ----- 二叉树的链式表示 ----- */
typedef char TreeData;

typedef struct node {
    TreeData data;
    struct node *leftChild; *rightChild;
};

typedef BinTreeNode *BinTree;

二叉树的操作

遍历

按某种次序访问树中所有结点，并且每个结点仅访问一次的操作。

1
2
3
4
5
6

// 访问结点
void visit(BinTreeNode *T) {
    if (T != NULL) {
        printf(T->data);
    }
}

遍历分为广度优先遍历和深度优先遍历两种。

遍历的方式 性质 具体内容
层序遍历 广度优先 逐层从左至右，从上到下访问
先序遍历 深度优先 先访问根结点，再访问左子树，最后访问右子树
中序遍历 深度优先 先访问左子树，再访问根结点，最后访问右子树
后序遍历 深度优先 先访问左子树，再访问右子树，最后访问根结点 
 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

// 先序遍历
void PreOrder(BinTreeNode *T) {
    if (T != NULL) {
        visit(T->data);
        PreOrder(T->leftChild);
        PreOrder(T->rightChild);
    }
}

// 中序遍历
void InOrder(BinTreeNode *T) {
    if (T != NULL) {
        PreOrder(T->leftChild);
        visit(T->data);
        PreOrder(T->rightChild);
    }
}

// 后序遍历
void PostOrder(BinTreeNode *T) {
    if (T != NULL) {
        PreOrder(T->leftChild);
        PreOrder(T->rightChild);
        visit(T->data);
    }
}

获取二叉树的相关信息

二叉树的操作函数基本都是以递归作为执行的核心逻辑。

 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
37
38
39
40
41
42
43
44
45
46
47
48

// 按前序建立二叉树
void CreateBiTree(BiTree* &T) {
    scanf(&ch);
    if (ch == '@') {
        T = NULL;
    }
    else {
        T = (BiTree*)malloc(sizeof(BiTree));
        T->data = ch;
        CreateBiTree(T->leftChild);
        CreateBiTree(T->rightChild);
    }
}

// 计算二叉树结点个数
int cnt = 0;
void NodeCount(BiTree* &T) {
    if (T != NULL) {
        cnt ++;
        Count(T->leftChild);
        Count(T->rightChild);
    }
}

// 求二叉树叶结点个数
int LeafCount(BiTree* &T) {
    if (!T) {
        return 0;
    }
    else if (!T->leftChild && !T->rightChild) {
        return 1;
    }
    else {
        return LeafCount(T->leftChild) + LeafCount(T->rightChild);
    }
}

// 求二叉树高度
int Height(BiTree* &T) {
    if (T == NULL) {
        return 0;
    }
    else {
        int m = Height(T->leftChild);
        int n = Height(T->rightChild);
        return (m>n) ? m+1 : n+1;
    }
}

二叉树的重构

重构：由二叉树的若干遍历序列，复现二叉树的原本结构。

已知遍历 结论
先序 + 中序 可重构
后序 + 中序 可重构
先序 + 后序 不可重构 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 重构二叉树
void BuildTree(BinTreeNode* &T, ElemType PreStart, ElemType PreEnd, 
                ElemType InStart, ElemType InEnd) {
    // 递归终点
    if (PreStart > PreEnd || InStart > InEnd) {
        return;
    }

    T = new BinTreeNode();
    // 当前子树的根结点
    T->data = PreSeq[PreStart];
    T->leftChild = NULL;
    T->rightChild = NULL;

    // 寻找中序遍历的根结点位置
    int root = find(T->data, InSeq, InStart, InEnd);
    // 计算左子树结点数目
    int nL = root - InStart;
    
    // 递归构建左子树
    BuildTree(T->leftChild, PreStart+1, PreStart+nL, InStart, root-1);
    // 递归构建右子树
    BuildTree(T->rightChild, PreStart+nL+1, PreEnd, root+1, InEnd);
}

线索二叉树

线索二叉树中，除根节点外，每个结点都有自己的前驱和后继。

用二叉链表表示的二叉树中，$n$ 个结点的二叉树有 $n+1$个空链域，可利用这些空链域存储结点的前驱或后继。

线索二叉树的结点结构

1
2
3
4
5
6
7
8
9

// PointerTag 为标志
// Link = 0 代表指针，Thread = 1 代表线索
typedef enum {Link, Thread} PointerTag

typedef struct BiThrNode {
    ElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
};

中序线索二叉树

 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
37
38
39
40
41
42
43
44
45
46

/* ----- 建立中序线索二叉树 ----- */
BiThrTree *pre;

bool InOrderThreading(BiThrTree* &Thrt, BiThrTree T) {
    if(!Thrt = (BiThrTree*)malloc(sizeof(BiThrNode))) {
        // 分配空间失败
        return false;
    }
    Thrt->LTag = Link;
    Thrt->RTag = Thread;
    Thrt->rchild = Thrt;    // 头结点右指针回指

    if(!T) {
        Thrt->lchild = Thrt // 二叉树为空，头指针也回指
    }
    else {
        Thrt->lchild = T;
        pre = Thrt;         // pre指向最后一个访问过的结点
        InThreading(T);
        pre->RTag = Thread; // pre指向中序遍历的最后一个结点
        pre->rchild = Thrt; // 最后一个结点的后继为头结点
        Thrt->rchild = pre; // 头结点的右指针指向中序遍历的最后一个结点
    }
    return true;
}

void InThreading(BiThrTree* p) {
    if(!p) {
        InThreading(p->lchild);

        if(!p->lchild) {
            // 建立前驱线索
            p->LTag = Thread;
            p->lchild = pre;
        }
        if(!p->rchild) {
            // 建立后继线索
            pre->RTag = Thread;
            pre->rchild = p;
        }
        // 保持pre为下一结点的前驱
        pre = p;

        InThreading(p->rchild);
    }
}

树与森林

树的存储结构

双亲表示

以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。该方法利用每个结点只有一个双亲的特点，可以很方便地求出结点的双亲，但不方便得到结点的孩子。

树的双亲表示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/* ----- 树的双亲表示 ----- */
#define MAXSIZE 100
typedef int TreeData;

typedef struct {
    TreeData data;
    int parent;
} TreeNode;

typedef TreeNode Tree[MAXSIZE];
孩子表示（多重链表）

将每个结点的孩子作为链表的结点链接在该结点之后，再将所有头结点组成一个线性表。

树的孩子链表表示

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

/* ----- 树的孩子链表表示 ----- */
// 孩子链表
typedef struct CTNode {
    int child;
    struct CTNode *next;
} *ChildPtr;
s
// 孩子链表的头结点
typedef struct {
    TElemType data;
    ChildPtr FirstChild;
} CTBox;

// 孩子链表头结点的线性表
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n;      // 结点数
    int r;      // 根的位置
} CTree;

左子女-右兄弟表示（二叉链表）

任何一棵和树对应的二叉树，其右子树一定为空。

1
2
3
4
5
6
7
8
9

/* ----- 树的二叉链表表示 ----- */
typedef char TreeData;

typedef struct node {
    TreeData data;
    struct node *firstChild, *nextSibling;
} TreeNode;

typedef TreeNode *Tree;

树的二叉链表表示

使用二叉链表可以方便地实现森林与二叉树的转换。

树的遍历

遍历方法 操作 对应二叉链表的遍历
先根次序遍历 当树非空时，先访问根结点，再依次先跟遍历根的各棵子树 前序遍历
后根次序遍历 当树非空时，先依次后根遍历根的各棵子树，再访问根结点 中序遍历

霍夫曼树

路径长度与霍夫曼树的定义

概念 内容
路径长度 连接两结点的路径上的分支数，记为 $PL$
外部路径长度 各叶结点到根结点的路径长度之和，记为 $EPL$
内部路径长度 各非叶结点到根结点的路径长度之和，记为 $IPL$
带权路径长度 各叶结点所带的权值 $w_i$ 与该结点到根结点的路径长度 $l_i$ 的乘积之和，记为 $WPL$

容易知道，$PL=EPL+IPL$

霍夫曼树就是带权路径长度最小的二叉树，也称作最优二叉树。

在霍夫曼树中，权值大的结点离根结点越近。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/* ----- 霍夫曼树的定义 -----*/
const int n = 20;    // 叶结点数，初始给定的权值数量
const int m = 2*n-1; // 结点数，所需的存储数量

typedef struct {
    float weight;   // 权值
    int parent, leftChild, rightChild;
} HTNode;

typedef HTNode HuffmanTree[m];

构造霍夫曼树

由给定的 $n$ 个权值 $\{w_0,w_1,w_2,\cdots,w_{n-1}\}$，构造具有 $n$ 棵二叉树的森林 $F=\{T_0,T_1,T_2,\cdots,T_{n-1}\}$，其中每棵二叉树 $T_i$ 只有一个带权值的根结点，其左右子树均为空。

步骤：

  1. 在 $F$ 中选取两棵根结点权值最小的二叉树，作为左、右子树构造一棵新的二叉树。令新的二叉树根结点的权值为其左右子树上根结点的权值之和。
  2. 在 $F$ 中删去这两棵二叉树。
  3. 把新的二叉树加入 $F$。
 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
37

/* ----- 构造霍夫曼树 ------ */
void CreatHuffmanTree(HuffmanTree T[], float fr[]) {
    // 将各边的权值加入数组中
    for(int i = 0; i<n; i++) {
        T[i].weight = fr[i];
    }
    // 初始化各子树
    for(int i = 0; i<m; i++) {
        T[i].parent = -1;
        T[i].leftChild = -1;
        T[i].rightChild = -1;
    }

    for (int i = 0; i<m; i++) {
        int min1 = min2 = MAXNUM;
        int pos1, pos2;
        for(int j = 0; j<i; j++) {
            if(T[j].parent == -1) {
                // 从所有根结点中查找权值最小的两个
                if (T[j].weight < min1) {
                    pos2 = pos1;
                    min2 = min1;
                    pos1 = j;
                    min1 = T[j].weight;
                }
                else if(T[j].weight < min2) {
                    pos2 = j;
                    min2 = T[j].weight;
                }
            }
        }
        T[i].leftChild = pos1;      // 左子树为第一小的结点
        T[i].rightChild = pos2;     // 右子树为第二小的结点
        T[i].weight = T[pos1].weight + T[pos2].weight;
        T[pos1].parent = T[pos2].parent = i;
    }
}

霍夫曼编码

霍夫曼编码主要用于实现数据压缩。

若按照各个字符出现概率的不同而给予不同长度的编码，可以减少总编码长度。总编码长度正好等于霍夫曼树的带权路径长度。

霍夫曼编码是一种无前缀编码（都由叶结点组成，路径不会重复）。解码时不会混淆。

设给出一段报文：

$$CAST CAST SAT AT A TASA$$

字符集合是{C, A, S, T}，各个字符出现的频度（次数）为 W = {2, 7, 4, 5}

按照各字符出现概率P = {2, 7, 4, 5}为各叶结点上的权值建立霍夫曼树。

霍夫曼编码

左分支赋值0，右分支赋值1，可得霍夫曼编码：A:0 T:10 C:110 S:111

© 2025 - 2026 RunicDolphin806
网站总访客数：Loading

使用 Hugo 构建
主题 Stack 由 Jimmy 设计