第五章:树与二叉树(数据结构)

数据对象 D ：D 是具有相同特性的数据元素的集合

数据关系 R ：若 D 为空集，则称为空树；

否则：

（ 1 ）在 D 中存在唯一的称为根的数据元素 root ，

（ 2 ）当 n> 1 时，其余结点可分为 m （ m > 0 ）个互不相交的有限集𝑇1  ,𝑇2, .…, 𝑇𝑚, 其中每一棵子集本身又是一棵符合本定义的树，称为根 root 的子树。

查找类:引用型  插入类:加工型  删除类:加工型

查找类:

Root(T); //求树的根结点

Value(T, cur_ e); //求当前结点的元素值

Parent(T, cur_ e); //求当前结点的双亲结点

LeftChild(T, cur_ e); //求当前结点的最左孩子

RightSibling(T, cur_e); // 求当前结点的右兄弟

TreeEmpty(T); //判定树是否为空树

TreeDepth(T); //求树的深度

TraverseTree( T, Visit() ); // 遍历

插入类:

InitTree(&T); 1初始化置空树

Create' Tree(& T, definition); 1按定义构造树

Assign(&T, cur_ e, value);/给当前结点赋值

InsertChild(&T, &p, i, c);//将以c为根的树插入为结点p的第i棵子树

删除类:

ClearTree(&T); //将树清空

DestroyTree(&T); // 销毁树的结构

DeleteChild(&T, &p, i);//删除结点p的第i棵子树

有向树：

（ 1 ）有确定的根，

（ 2 ）树根和子树根之间为有向关系。

有序树:

子树之间:确定的次序关系。

无序树:

子树之间 - 确定的次序关系。

度为0的结点为叶子结点

5.1二叉树

二叉树的定义:

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

特点：1）每个结点的度≤2；2）是有序树

若干术语

根——即根结点(没有前驱)

叶子——即终端结点(没有后继)

森林—指m棵不相交的树的集合

(例如删除A后的子树个数)

有序树——结点各子树从左至右有序，不能互换(左为第一)

无序树——结点各子树可互换位置。

双亲——即上层的那个结点,也叫父节点(直接前驱)

孩子——即下层结点的子树的根(直接后继)

兄弟——同一双亲下的同层结点(孩子之间互称兄弟)

堂兄弟——即双亲位于同一层的结点（但并非同一双亲)

祖先——即从根到该结点所经分支的所有结点

子孙——即该结点下层子树中的任一结点

度大于0的结点称为分支结点 度为0的结点称为叶子结点

五种形态

二叉树的五种不同的形态

定义1 满二叉树(Full Binary Tree)

定义2 完全二叉树(Complete Binary Tree)

若设二叉树的深度为h，则共有h层。除第h层外，其它各层

(0~h-1)的结点数都达到最大个数，第h层从右向左连续缺若干

结点，这就是完全二叉树。

在二叉树中,叶子节点比度为2的结点多1的

𝑛₂=𝑛₀-1

叶字节点\(\lceil \frac{n+1}{2}\rceil\)

5.1.1 二叉树的性质

性质1 若二叉树的层次从1开始, 则在二叉树的第 i 层最多有 2ⁱ⁻¹个结点。(i ≥1)

[证明用数学归纳法]

性质2 深度为k的二叉树最多有 2^𝑘-1个结点。(k ≥1)

[证明用求等比级数前k项和的公式]

性质3 对任何一棵二叉树, 如果其叶结点个数为 n₀ , 度为2的非叶结点个数为 n₂ , 则有

n₀＝n₂ ＋1

n=n0+n1+n2 n=n1+2n2+1

两种方法:

方法一:总结点数=度为0结点+度为1的结点+度为2的结点

方法二:总结点数=1×度为1的结点+2×度为2的结点+1个根结点

性质4 具有n个结点的完全二叉树的深度为

⌊log₂n⌋ +1

证明：设完全二叉树的深度为k，则有

2^k−1 -1<n < 2^k - 1

2^k−1 <n < 2^k 

取对数 k-1 ≤ log₂n <k

因为k为整数，所以k =⌊log₂n⌋ +1

说明：常出现在选择题中

性质5 如果将一棵有n个结点的完全二叉树的结点按层序(自顶向下，同一层自左向右）连续编号1, 2, …, n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中, 并简称编号为i的结点为结点i (1 ≤ i ≤ n)。则有以下关系：

①若i == 1, 则 i 是二叉树的根，无双亲

②若i > 1, 则 i 的双亲为⌊i /2⌋

③ 若2*i ≤ n, 则 i 的左孩子为2*i，否则无左孩子

④若2*i+1 ≤ n, 则 i 的右孩子为2*i+1，否则无右孩子

⑤ 若 i 为偶数, 且i != n, 则其右兄弟为i+1

⑥若 i 为奇数, 且i != 1, 则其左兄弟为i-1

 i 所在层次为⌊log ₂i⌋ +1

5.2二叉树的存储结构

1、顺序存储结构（数组表示）

存树的数据和关系才能还原这棵树.

①连续②编号法存储③空间有浪费的(一般二叉树)

左分支和右分支相比,右分支更浪费,右编号大

2.链式存储模式

typedef struct BiTNode{ //二叉链表的定义
  TElemType data;
  Struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

逻辑结构(a)存储计算机形成存储结构(b) ,三叉链表指向双亲的指针(C)

5.3二叉树的遍历(Traversing Binary Tree)

所谓树的遍历，就是按某种次序访问树中的结点，要求每个

结点访问一次且仅访问一次。

遍历的结果：产生一个关于结点的线性序列。

设访问根结点记作 D

遍历根的左子树记作 L

遍历根的右子树记作 R

则可能的遍历次序有

先序 DLR DRL 逆先序

中序 LDR RDL 逆中序

后序 LRD RLD 逆后序

void PostOrder(BiTree T){
        InitStack(S);
        BiTree p=T;
        r=NULL;     //记录最近访问过的结点
        while(p||!IsEmpty(S)){
            if(p){              //走到最左边
                push(S,p);
                p=p->lchild;
            } else {        //遍历完左子树,向右
                GetTop(S,p);    //取栈顶结点
                if(p->rchild&&p->rchild!=r){ //如果右子树存在,且未访问过
                    p=p->rchild;    //转向右
                    push(S,p);   //压入栈
                    p=p->lchild; //再走到最左
                } else {           //否则弹出结点并访问
                    pop(S,p);   //将结点弹出
                    visit(p->data);   //访问该结点
                    r=p;        //记录最近访问过的结点
                    p=NULL; 
                }
            }  //else
        }  //while
    }

5.3.1先序遍历 (Preorder Traversal)

先序遍历二叉树算法的框架是

n 若二叉树为空，则空操作；

n 否则

u 访问根结点 (D)；

u 访问根结点 (D)；

u 先序遍历左子树 (L)；

u 先序遍历右子树 (R)。

Status PreOrderTraverse(BiTree T) {
	if (T == NULL)return OK;//空二叉树
	else {
		visit(T);//访问根结点
		PreOrderTraverse(T->lchild);//递归遍历左子树
		PreOrderTraverse(T->rchild);//递归遍历右子树
	}
}

遍历结果（前缀表达式）

遍历结果（前缀表达式）

- + a * b - c d / e f

5.3.2中序遍历 (Inorder Traversal)

遍历结果（中缀表达式）

Status lnOrderTraverse(BiTree T) {
	if (T == NULL)return OK; // 空二叉树
	else {
		InOrderTraverse(T->lchild);//递归遍历左子树
		visit(T);//访问根结点;
		InOrderTraverse(T->rchild);//递归遍历右子树
	}
}

遍历结果（中缀表达式）

a + b * c - d - e / f

5.3.3后序遍历 (Postorder Traversal)

1.后序遍历二叉树算法的框架是

n 若二叉树为空，则空操作；

n 否则

u 后序遍历左子树 (L)；

u 后序遍历左子树 (L)；

u 后序遍历右子树 (R)；

u 访问根结点 (D)

Status PostOrderTraverse(BiTree T) {
	if (T == NULL) return OK;//空二叉树
	else {
		PostOrderTraverse(T->lchild);//递归遍历左子树个
		PostOrderTraverse(T->rchild);//递归遍历右子树
		visit(T);//访问根结点
	}
}

2.算法与数据结构的关系

遍历结果（后缀表达式）

a b c d - * + e f / -

由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。例, 先

序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下：

后缀表达式,符号优先级

5.3.4层次遍历

算法思想:

1)初始将根入队并访问根结点，然后出队;

2)若有左子树，则将左子树的根入队;

3)若有右子树，则将右子树的根入队;

4)然后出队，访问该结点;

5)反复该过程直到队列空为止。

void LevelOrder(BTNode *b) {
	BTNode* p; SqQueue *qu;
	lnitQueue(qu);
	// 初始化队列
	enQueue(qu，b);
	//根结点指针进入队列
	while (!QueueEmpty(qu)) {
		// 队不为空，则循环
		deQueue(qu，p);//出队结点p
		printf("%c "，p->data);
		//访问结点p
		if (p->lchild != NULL)enQueue(qu，p->lchild);
		//有左孩子时将其进队
		if (p->rchild != NULL)enQueue(qu, p->rchild);
		//有右孩子时将其进队
	}
}

5.4线索二叉树.

线索 (Thread): 指向结点前驱和后继的指针

若结点有左孩子，则lchild指示其左孩子，否则lchild中存储该结点的前驱结点的指针；

(Threaded Binary Tree)

若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针

实质：对一个非线性结构进行线性化操作，使每个结点（除第一和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。

说明：在线索树中的前驱和后继是指按某种次序遍历所得到的序列中的前驱和后继

线索二叉树及其线索链表的表示

ltag = 0, lchild为左孩子指针

ltag = 1, lchild为前驱线索

rtag = 0, rchild为右孩子指针

rtag = 1, rchild为后继指针

带表头结点的中序穿线链表

后续线索化如上

有左右孩子将标志置为0,没有左右孩子,将标志置为1.

5.5,哈夫曼树

路径长度 (Path Length)：两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各结点到根结点的路径长度之和。

具有不同路径长度的二叉树

具有不同带权路径长度的扩充二叉树

从(a)可以看出满二叉树不一定是哈夫曼树

从(c)(d)看出具有相同带权结点的哈夫曼树不惟一

结论:

哈夫曼树的结点的度数为0或2，没有度为1的结点。

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点

包含n个叶子结点的哈夫曼树中共有2n- 1个结点。

带权路径长度达到最小的二叉树即为赫夫曼（最优二叉树）。

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

赫夫曼树的构造过程

5.5.1赫夫曼编码

主要用途是实现数据压缩。

设给出一段报文：

CAST CAST SAT AT A TASA

字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。

若给每个字符以等长编码

A: 00 T : 10 C : 01 S : 11

则总编码长度为 ( 2+7+4+5 ) * 2 = 36.

若按各个字符出现的概率不同而给予不等长编，可望减少总编码长度。

因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18}。

化整为 { 2, 7, 4, 5 }，以它们为各叶结点上的权值，建立赫夫曼树。左分支赋 0，右分支赋 1，得赫夫曼编码(变长编码)。

A: 0 T : 10 C : 110 S : 111

它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。

总编码长度正好等于赫夫曼树的带权路径长度WPL。

赫夫曼编码是一种无前缀的编码。解码时不会混淆。

5.5.2．哈夫曼树的构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别

设为 w 1 ,w 2 ,…,w n ,则哈夫曼树的构造规则为：

(1) 将w 1 ,w 2 ,…,w n 看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、

右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得

的哈夫曼树。

下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，

则构造哈夫曼树过程如图根据构造过程：n 个权值构造哈夫曼树需n-1次合并，每次合并，森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。

5.6树和森林

5.6.1 树的存储结构

1,双亲表示法

它是以一组连续的存储单元来存放树中的结点，每个结点有两个域：

一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位

置(指针)。

该结构的具体描述见图5-21。

2.孩子表示法

将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述，具体描述参见图5-22

图 5-22树的孩子表示法(图6-2 1(a)中树)示意图

3.双亲孩子表示法

将第1、2两种方法结合起来，则得到双亲孩子表示法，具体参见图5-23

图 5-23 树 的 双 亲 孩 子 表 示 法 示 意 图

4.孩子兄弟法

类似于二叉链表，但第一根链指向第一个孩子，第二根链指向下一

个兄弟。将图5-21(a)的树用孩子兄弟表示法表示，见图5-24

5.6.2 树、森林和二叉树的转换

1．树转换成二叉树

可以分为三步：

（1） 连线

指相邻兄弟之间连线。

（2） 抹线

指抹掉双亲与除左孩子外其它孩子之间的连线。

（3） 旋转

只需将树作适当的旋转。

具体实现过程见图5-25。

图 5-25 树 转 换 成 二 叉 树 示 意 图

2.森林转换成二叉树

（1） 将森林中每一棵树分别转换成二叉树这在刚才的树转换成二叉树中已经介绍过。

（2）合并

使第n棵树接入到第n-1棵的右边并成为它的右子树，第 n-1 棵二叉树接入到第n-2 棵的右边并成为它的右子树，…，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止

3．二叉树还原成树或森林

(1) 右链断开

将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子

树的二叉树。

具体操作见图5-27(b)。

（2） 二叉树还原成树

将（1）中得到的每一棵二叉树都还原成树（与树转换成二叉树的步骤

刚好相反）。

具体操作步骤见图5-27(c)。

图5-27(c) 二叉树还原成树或森林

5.6.3 树和森林的遍历

在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它

们的中序遍历， 即树和森林只有先序遍历和后序遍历。

1．树的遍历

\(\color{green}{树的遍历} \begin{equation}\begin{cases}     \color{blue}{深度优先遍历,}   \color{red}{(先根,后根)}\\     \color{blue}{广度优先遍历. } \color{red}{(层次)}\\ \end{cases}\end{equation}\)

树没有中序遍历（因子树不分左右）

例如：

先根序列：a b c d e 后根序列：b d c e a

讨论：树若采用“先转换，后遍历”方式，结果是否一样？

先序遍历：a b c d e 中序遍历：b d c e a 后序遍历：d e c b a 树的先根序列：a b c d e 树的后根序列：b d c e a

结论：

1.  树的先根遍历与二叉树的先序遍历相同；

2. 树的后根遍历相当于二叉树的中序遍历；

3. 树没有中序遍历，因为子树无左右之分。

2.森林的遍历

\({\color{green}{\textbf{森林的遍历}}} \begin{equation}\begin{cases}     {\color{peru}{\textbf{深度优先遍历,}}}   \color{red}{(先根,中根)}\\      {\color{peru}{\textbf{广度优先遍历. }}} \color{red}{(层次)}\\ \end{cases}\end{equation}\)

例如：

先根序列：A B C D E F G H I J 中根序列：B C D A F E H J I G

讨论：若采用“先转换，后遍历”方式，结果是否相同？

先序序列：A B C D E F G H I J 中序序列：B C D A F E H J I G

结论：森林的先根和中根遍历在两种方式下的结果相同。

遍历序列关系