抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

🔑数据结构_第五章:树与二叉树

第五章、树与二叉树

(一)树的基本概念

1、基本概念

是n(n>0)个结点的有限集。

当n=0时,称为空树。在任意一棵空树中应满足:

  • 有且仅有一个特定的称为根的结点。
  • 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树

显然,根的定义是递归的,即在树的定义中又用到了其自身,树是一种递归的数据结构。

树作为一种逻辑结构,同时又是一种分层结构,具有以下两个特点:

  • 树的根结点没有前驱,其它所有结点有且只有一个前驱。
  • 树中所有结点都可以有0个或多个后继。

树有n个结点,那它就有n-1条边。

2、基本术语

  • 结点之间的关系描述

    image6dc349e8b1e54d7f.png

    祖先结点:从“你”出发到根结点的路径上所经过的所有结点都称为“祖先结点”。

    子孙结点:“你”后面的所有结点都可称为子孙结点。

    双亲结点——即父节点——即直接前驱。

    孩子结点——直接后继。

    兄弟节点——同一层的结点。

    唐兄弟节点——双亲在同一层的结点。

  • 结点、树的属性描述

    路径:自上而下的某两个节点之间的所有结点构成的序列,同一双亲的两个孩子之间不存在路径。

    路径长度:路径上所经过的边的个数。

    结点的层次/深度:从上往下数在第几层。

    结点的高度:从下往上数。

    树的深度/高度:总共多少层。注:深度默认从1开始算,但不排除有些题目指明从0开始!

    结点的度:孩子/分支/直接后继的个数,是个数字。非叶子节点的度>0,叶子节点的度=0。

    树的度:各结点的度的最大值MAX{结点A的度,结点B的度,结点C的度,...,结点N的度}

  • 有序树、无序树

    • 有序树:树中结点的各子树从左到右是次序的,不能互换。

      常见有哈夫曼树(俗称最优二叉树)、族谱(不能交换每一层老大老二老三等的位置)等。

    • 无序树:树中结点的各子树从左到右是次序的,可以互换。

    总之,需要用结点的左右位置关系来反映某些逻辑关系的话就是有序树,否则为无序树。

  • 森林

    森林是m(m≥0)棵互不相交的树的集合。

    image28cd59f5811c9f53.png

3、树的常考性质

  • 常见考点一:结点数 = 总度数 + 1

  • 常见考点二:度为m的树m叉树的区别。

    image3aa7cad67beb25cd.png
  • 常见考点三:度为m的树i层至多有**mi-1**个结点(i≥1)。

    若层数从0开始,则结点数为**mi**个。

    image281f8c2a3981f5d7.png
  • 常见考点四和五:高度为h的**m叉树**结点个数的上下限问题。

    最多:

    image9b4c220a030e9383.png $$ 最多为:\frac{m^h-1}{m-1} $$ 涉及到的是等比数列求和公式: $$ a+aq+aq^2+...+aq^{n-1} = \frac{a(1-q^n)}{1-q} $$

    最少:

    有h个结点:

    imagee0b06932d6044893.png
  • 常见考点六:具有n个结点的m叉树的最小高度为:

    image38f8006782740aca.png $$ 前h-1层最多最多结点数 < n \le 前h层最多最多结点数\\ \frac{m^{h-1}-1}{m-1} < n \le \frac{m^h-1}{m-1}\\ m^{h-1}

(二)二叉树的概念

1、基本概念

二叉树是n个结点的有限集合。(n=0时称为空树)

由一个根结点和两个互不相交的被称为跟的左子树和右子树组成,左子树和右子树又分别是一棵二叉树。

  • 特点:

    每个结点最多有两棵子树;

    左右子树不能颠倒——二叉树是有序树!

image139bbe5dd3f415ad.png
  • 二叉树的五种形态:

    空树、只有左子树、只有右子树、只有根结点、完整二叉树。

2、几个特殊的二叉树:

(1)满二叉树
  • 高度为h,且含有2h-1个结点的二叉树

  • 特点:

    • 只有最后一层有叶子结点。
    • 不存在度为1的结点。
    • 按层序从i=1开始编号,结点i的左孩子编号为2i,右孩子为2i+1;结点i的父结点为[i/2](向下取整)(如果有的话)。
(2)完全二叉树
  • 定义:当且仅当其每个结点都与高度同样为h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树

  • 特点:

    • 只有最后两层可能有叶子节点。

    • 最多只有一个度为1的结点。

    • 同上。

    • 总结点数为n的完全二叉树中,编号i≤[n/2](向下取整)的结点为分支节点,i>[n/2](向下取整)则为叶子节点。

      换句话说:一半是分支节点另一半是叶子结点,n为奇数时多出来的一个一定是叶子结点。

imageb3b7463b908906a0.png
(3)二叉排序树

满足以下特点的树称为二叉排序树:

①左子树上所有结点的数据均小于根结点存储的数据;

②右子树上所有结点的数据均大于根结点存储的数据;

③左子树和右子树又各满足以上条件。

image13e6b31770630ac0.png
(4)平衡二叉树

定义:树上任一结点的左子树和右子树的深度之差不超过1。

平衡二叉树是为了解决排序二叉树成链状的情况的。

imageee35112bcb27f1df.png

3、二叉树常考性质

常见考点1

设非空二叉树中度为0、1、2的结点的个数分别为n0、n1、n2,则有:
$$
n_0 = n_2 + 1
$$
即——叶子节点总比二分之结点多一个。

image086079e5df60537e.png
常见考点2

二叉树第i层至多有**2i-1**个结点(i≧1)。

m叉树第m层至多有**mi-1**个结点(i≧1)。

image2ae18ce16a8a7878.png
常见考点3

高度为h的二叉树至多有2h-1个结点(满二叉树)。

高度为h的m叉树至多有mh-1/m-1个结点。

imagedf6251a28b12c19d.png
完全二叉树的常见考点

常见考点1:

完全二叉树的结点数为n(n>0),那么高度h为[log2(n+1)](向上取整)或[log2n]+1(向下取整)。

image7013d0283d3de9aa.png image94b4f7b93d86eb58.png

常见考点2:

对于完全二叉树,可以由总结点数n推出度为0、1、2的结点个数n0、n1、n2

imagef2f08583f6cee67f.png

4、二叉树的存储结构

(1)顺序存储

只适合存储完全二叉树!

用数组存储,每个数组元素就是一个结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# include<stdio.h>

#define MAXSIZE 100
struct TreeNode {
ElemType value; //节点中的数据元素
bool isEmpt; //结点是否为空
};


int main(){
//初始化数组
TreeNode t[MAXSIZE];
for (int i=0; i<MAXSIZE; i++){
t[i].isEmpt = true;
}
}
imagef7e40c3054757262.png

几个重要常考的基本操作:

  • 判断是否有并找出指定结点i的左孩子、右孩子、父结点、i所在层次。
(2)链式存储

对于非完全二叉树采用链式存储——也称为“二叉链表”。

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
//二叉树链式存储
//定义数据域
struct ElemType{
int value;
};
//定义结点
typedef struct BitNode{
ElemType data; //数据域
struct BitNode *lchild ,*rchild; //左右孩子指针
}BitNode, *BiTree;

int main(){
//定义一棵空树
BiTree root = NULL;
//插入根结点
root = (BiTree)malloc(sizeof(BitNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;
//插入新结点
BitNode *p = (BitNode *)malloc(sizeof(BitNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;
}
image8e0e12f9523ac2a6.png

在该类二叉链表中,由某一结点开始寻找子节点很容易,但是寻找父结点就只能循环遍历了。

当然我们还可以给每个结点多附加一个指向父结点的指针使其成为“三叉链表”,不过考研考的是不带父指针的情况。。。(该遍历害得遍历)

对于有n个结点的二叉树,共有2n个指针域,除去根结点外每个结点头上都有一个指针指向它,所以共有n-1个非空指针,那么空指针就有2n-(n-1)=n-1个。

这些空指针域我们可以用来构造线索二叉树

(三)二叉树的遍历与线索二叉树

1、根据二叉树的递归特性制定遍历规则

  • 二叉树的递归特性:

    • 要么是个空二叉树;
    • 要么就是由“根结点+左子树+右子树”组成的二叉树。
  • 对于非空二叉树有三种遍历方式:

    • 先序遍历:根左右NLR

      1
      2
      3
      4
      5
      6
      7
      void PreOrder(BiTree){
      if(T != NULL){
      visit(T); //根
      PreOrder(T->lchild); //递归遍历左子树
      PreOrder(T->rchild); //递归遍历右子树
      }
      }
    • 中序遍历:左根右LNR

      1
      2
      3
      4
      5
      6
      7
      void InOrder(BiTree){
      if(T != NULL){
      InOrder(T->lchild); //递归遍历左子树
      visit(T); //根
      InOrder(T->child); //递归遍历右子树
      }
      }
    • 后序遍历:左右根LRN

      1
      2
      3
      4
      5
      6
      7
      void PostOrder(BiTree){
      if(T != NULL){
      PostOrder(lchild); //递归遍历左子树
      PostOrder(rchild); //递归遍历右子树
      visit(T); //根
      }
      }

eg:

image22d11689c39caa02.png imagef3199a163c70a626.png imagedbb54ffb128328b8.png

这种递归调用的时间复杂度为:O(h)(h为树的高度)。

  • 求树的深度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int treeDepth(BiTree T){
    if(T == NULL){
    return 0;
    }
    else{
    int l = treeDepth(T->lchild);
    int r = treeDepth(T->rchild);
    //树的深度 = MAX(左子树深度, 右子树深度) + 1;
    return l>r ? l+1 : r+1;
    }
    }

2、二叉树的层序遍历

层序遍历,即按层级从上到下、从左到右依次遍历。

代码实现过程中还需借助一个辅助队列。

image01e1e4d506267e56.png imagea5526ed33255fc16.png
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
//定义二叉树结点
typedef struct BiTree{
char data;
struct BiTree *lchild, *rchild;
}BiTree, *BiTree;

//定义链式队列结点
typedef struct LinkNode{
BiTNode * data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;//队头队尾
}LinkQueue;

//层序遍历
void LevelOrder(BiTree T){
LinkQueue Q; //声明队列Q
InitQueue(Q); //初始化Q
BiTree p; //声明指针p
EnQueue(Q, T); //根结点入队
while(!IsEmpty(Q)){ //队列不空则循环
DeQueue(Q, p); //队头结点出队
visit(p); //访问出队节点
if(p->lchild != NULL)
EnQueue(Q, p->lchild); //刚出队结点的左孩子入队
if(p->rchild != NULL)
EnQueue(Q, p->rchild); //刚出队结点的右孩子入队
}
}

3、由遍历序列构造二叉树

不同二叉树可能得出同一个遍历结果(前、后、中、层序遍历都是如此),而由一个遍历序列可以产生不同的二叉树:

image872870125b706c3b.png

因此我们说,不能仅通过前、中、后、层序遍历系列中的某个序列确定一个二叉树。

但如果给出中序遍历加其他任意一个序列的话,我们可以凭这两个序列确定一个唯一的二叉树:

PS:必须有有中序遍历序列!

image7b92769067ab407f.png

eg:

image426d0579a255d11d.png image77893c5746c2968a.png

总结:

image51a45cbb81d360be.png

考试考法:给出中序遍历序列和其他一种序列,让我们求二叉树。

4、线索二叉树

(1)概念及原理

我们把那些左右指针为空的结点加以改造利用起来,使其原本为空的指针域指向它遍历顺序的前、后结点,这样子该二叉树要比原来访问起来(找前驱后继)方便很多。

下图为中序遍历方式生成的线索二叉树:

image704b10bd3fd28c4b.png image9d1a72b94d7ad787.png

代码层面:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//原来的结点结构
typedef struct BiTree{
ElemType data; //数据域
Struct BiNode *lchild, *rchild; //左右孩子指针域
}BiNode, *BiTree;

//加以改造
typedef struct ThreadNode{
//数据域和指针域不变
ElemType data;
struct ThreadNode *lchild, *rchild;
//添加tag标识,用于标记说明该结点的左右指针指向的它的左右孩子结点、还是前驱和后继
//tag=0,指向左右孩子结点;tag=1,指向前驱后继。
int ltag = 0, rtag = 0;
}ThreadNode, *ThreadTree;

先序线索二叉树同样如此:

20dc1e08cef5cbd0208960103a2506e6.jpg

后序线索二叉树同样如此:

9f8026ca62edb436c416f72f4c1fd9ac.png

总结:

image6f41ec8e5b7bfa6e.png
(2)代码实现——二叉树的线索化
①中序线索化
imagef2b1605954414a5f.png image.png
②先序线索化
imagec391af28a5f484ae.png imageeaf2782cdd6be498.png
③后续线索化
imagecfa5b72c5283aba5.png imagefe03ed5a1537527e.png
(3)在线索二叉树中寻找前驱和后继

中序线索二叉树:

在中序二叉树中找某个结点*p的中序后继next

①若p->rtag == 1,则next = p->rchild

②若p->rtag == 0,则遍历寻找后继结点。

image7ad6c959ae5a47ee.png

同理,找前驱也是如此:

①若p->ltag == 1,则pre = p->lchild

②若p->ltag == 0,则遍历寻找前驱结点。

image7ca792a72824e9b2.png

先序线索二叉树:

imagef1296338982e07df.png

在先序线索二叉树中无法用该方法实现找某个节点的先序前驱!除非能找到其父结点并且:

image4105feb8bd8db072.png

后序线索二叉树:

image5ca3ccaac3dd6083.png

同样,在后序线索二叉树中无法用传统方法找某个节点的后序后驱!除非能找到其父结点并且:

image6b6d58990f0da15e.png

(四)树、森林

回顾:树的逻辑结构

image9cb347717d17a271.png

1、双亲表示法(顺序存储)

用顺序存储的方式存储每个数据元素,每个结点都有数据域和一个存储父结点位置的”指针“:

1
2
3
4
5
6
7
8
9
10
11
//定义节点
typedef struct{
ElemType data; //数据域
int parent; //父结点位置域
}PTNode;

//定义树
typedef struct{
PTNode nodes[MAX_TREE_SIZE]; //
int n; //树的结点总数
}PTree;
imageb623e4438ad5d785.png
  • 增删改查:
    • 增:直接在表的末尾增加结点即可。
    • 删:叶子结点随便删,但是非叶子结点就不好删了!
    • 改:找到结点即可。
    • 查:查某个元素的父结点很容易,但要查子节点就只能遍历了。

2、孩子表示法(顺序+链式)

imaged62dcd107d5991da.png

*讲师没有过多赘述,,,。

3、孩子兄弟表示法(链式)——二叉树与树的转化

最常用!最常考!!!

本质上是二叉链表,不同的是,每个结点的两个指针,一个指向兄弟结点,另一个指向其第一个孩子节点,如下图:

image4cc887e0c1b6f2a1.png

这样存储的结果便是将一棵任意的树转化成了二叉树,实现了二者的转化!

1
2
3
4
5
6
typedef struct CSNode{
//数据域
ElemType data;
//指针域,前者指向第一个孩子,后者指向兄弟
struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

4、森林和二叉树之间的转换

同理,森林不过是多个树而已,而多个树的根结点我们又可以看作是同一层的兄弟结点,这样子就可以把整片森林存储为一个二叉树!

  • 森林转化为二叉树:

    image2949333d30e5bffc.png
  • 二叉树转化为森林:

    image2e79da4690f97d1b.png

其实本质上还是用二叉链表存储森林。

(五)树、森林的遍历

  • 树的遍历有:
    • 先根遍历
    • 后根遍历
    • 层序遍历
  • 森林的遍历有:
    • 先序遍历
    • 中序遍历

1、树的先根、后根、层序遍历

树的先根、后根、层序遍历在逻辑上与二叉树的遍历一毛一样!

imageb6ed551f28e55a9f.png

树的先根遍历的结果序列,与把它转化为二叉树的先序遍历序列结果,是一样的,后根遍历序列又对应中序遍历序列,即:

先根——先序,树后根——二叉树中序,二者属于深度优先遍历。

而层次遍历属于广度优先遍历:

image70c13f0fe028a0be.png

2、森林的遍历

(1)先序遍历

挨个树进行先根遍历,最后依次连起来:

  • 访问森林中第一棵树的根结点;
  • 先序遍历第一棵树中根节点的子树森林;
  • 先序遍历除去第一棵树后剩余的树构成的森林。
image940a2a5272fc4cfd.png

或者转化为二叉树进行先序遍历,序列结果一样。

(2)中序遍历

挨个树进行中序遍历,最后依次连起来:

  • 中序遍历森林中第一棵树的根结点的子树森林。
  • 访问第一棵树的根结点。
  • 中序遍历除去第一棵树之后剩余的树构成的森林。
image66c3a45c5727ed7d.png

或者转化为二叉树进行中序遍历,序列结果一样。

(六)哈夫曼树

1、哈夫曼树的定义

  • 我们给结点赋予一个新的属性——权值,节点的权是具有某种现实含义的数值(如表示结点的重要性等)。

  • 结点的带权路径长度:从树的根结点到该结点的路径长度(经过的边数)与该结点权值的乘积。

  • 树的带权路径长度:树中所有叶子结点的带权路径长度之和(WPL,Weighted Path Length)。

image757d1b8ed0ea73d5.png

定义:在含有n个带权结点的二叉树中,其中带权路径长度最小的二叉树称为哈夫曼树,也称最优二叉树、赫夫曼树。

2、哈夫曼树的构造

给定n个不同权值的结点,构造哈夫曼树:

  • 将这些单独的结点看作只有根节点的二叉树,它们构成森林F

  • 从F中选择两个权值最小的树,作为新的根结点的孩子,构成一个具有新的权值的二叉树;

  • 从F中删除刚才选出的两棵树,同时将新得到的树加入到F中。

  • 重复上述步骤,直到F中只剩一棵树为止。

image7993e6dd9ae2403c.png
  • 每个初始给定的结点最终都成为构造的哈夫曼树的叶子结点,且权值越小的结点到根结点的路径长度越大;
  • 哈夫曼树的结点总数为2n - 1
  • 哈夫曼树中不存在度为1的结点;
  • 哈夫曼树并不唯一,但WPL必然相同且为最优。

3、哈夫曼编码

  • 固定长度编码:每个字符都采用相同长度的二进制位表示。
  • 可变长度编码:允许对不同字符采用不等长的二进制位表示。
  • 在一套可变长度编码中,若任意字符的编码都不是其它任意字符编码的前缀,那么我们称这一套编码为前缀编码
  • 哈夫曼编码:由哈夫曼树得到——字符集中的每个字符作为一个叶子结点,各个字符出现的频度作为叶子结点的权值,由此构造出哈夫曼树。
image288d7042f475d6cd.png

评论