12.第12节课第6章树

罗泽兵 · 发表于 2024-4-15 09:17:36

啊，我们来看一下树的森林，这样一个部分，那么在大量的应用中呢？人们曾使用多种形式的存储结构来表示数，那么我们来看一下有三种表示方法，一个呢？是双亲表示法一个呢？是孩子表示法一个呢？是我们的孩子兄弟法。首先我们来看一下数的定义，数的定义是什么呢？数是n个元素的有限集合。d若d为空集，则为空数。

否则，在d中存在唯一的称为根的元素root，当n大于一时，其余节点呢，可分为m个互不相交的有限集t1t2，一直到TM。其中，每一棵树子集本身呢，又是一个符合本定义的数，称之为root的子树。书的基本操作呢，有查找类的操作，插入类的操作和删除类的操作，查找类的操作呢，有root t求数的根结点value tq e求当前。

节点的元素值parent t current e求当前节点的双亲节点left child t current e求当前节点的最左孩子。rights s sibling t current e求当前节点的右兄弟。除以mtt。判定treet数是否为空数tree depth。t求树的深度traverse t traverse TT。便利。插入列的操作呢？有你，你需要treet初始化空数create tree。t definition定义按定义构造数assign t current e value结合给当前结节点的赋值。那么，我们还有删除掉的操作clear treet，将树清空destroy treet销毁树的结构。我们来看一下。这棵树那么树根呢？

就是a它有三个孩子，一个呢左孩子一它有三个孩子。bcd三个。那么b呢，又是一个指数的根结点，那么c也是一个指数的根结点d也是一个指数的根结点，那么b呢，又有两个孩子c呢，有一个孩子d呢，又有这样一个结指数结点的部分。那么我们看一下森林森林呢，是m棵互不相交的树的集合，任何一棵非公树呢，就是一个二元组除以等于root f。其中呢，

被称为根结点f呢，被称为指数森林啊，比如说我们旁，我们这个部分呢，就是一个。子树的这样一个部分。就是一个森林的这样一个部分，那么它有一个根，那么就是这样一个a，那么一个a的这样一个根节点的部分。那么我们再看书的申请的存储结构，刚才我们讲过，有我们的双星表示法，孩子表示法，以及呢，

孩子兄弟表示法。首先我们看一下双星表示法。双星表示法呢？呃呃，双星表示法呢？那么在我们的这样一个部分当中呢？是一种一种连续的存储单元。存储数的节点，每个节点除了数据域data外，还复设一个parent域，也只是双击节点的位置。啊，比如说那么我们这里呢a。它的这样一个节点呢？那么。

它的双曲线呢是？那么，它是在第零层。在第零号位置，那么b的双星节点呢？b是一的这样一个。顺顺序的这样一个部分，那么这样一个这个数量的部分，那么它的双击节点呢？是a那么就是零那么bcd呢？它的双击节点呢？都是a那么一的双击节点呢是？c而f的双星节点呢，也是CG的双星节点呢，是五那么这是我们的双星表示法，

那么这种存储结构呢，利用了每个节点。除了根以外，只有唯一双性的性质在这种存储结构下求节点的双性呢，非常方便，也很容易呢，求树的根。但求节点的孩子时呢，需要遍历整个结构。好吧，我们看一下它的C语言的类型描述defy井号defy max tree size 100结构data parent。type defy struct PT node edit dat aint parent双击位置域PT node定义一个这样一个结构体类型的名称，那么PT node。树结构呢，是p trap defy struct PT node nodes，

maps size tree size。int.rn树根节点的位置和节点个数p除以，那么这是定义一个结构体类型的名称，那么这是我们定义的这样一个类型部分。那么我们再看一下孩子，表示法。孩子表示，法呢，是使用多重链表每个。节点呢，有多个指针域，其中呢，每个指针指向一棵指数的根节点。多重链表的多重链表的节点是同构的，

低位数的度，那么这是它的这样一个节点的，这样一个部分。还有多重样本技能是不同构的好吧。第二，为节点的度。那么，这是我们的孩子链表法的这样一个结构的，这样一个部分，我们来看一下孩子链表那么与双亲节点表示法相相反，孩子表示法呢，便于设计孩子的操作实验。但不如适合呢，搞双星的操作，我们可以呢，

把孩子表示法和双星表示法结合起来，那比如说我们的这样一个。这样一个孩子表的孩子表示法的这样一个部分，那么这是我们的这样一个表的这样一个表的这样一个类型。那么说a的这个节点呢？有bcd三个孩子，这样一个节点那么b呢？没有这个指数。c呢，也没有指数。c呢有指数c有ef两个指数，那么d没有指数e没有指数那么f呢有一个孩子有一个这样一个指数一个这样一个节点那么g呢没有孩子没有没有孩子没有这个节点。那么我们看一下C语言描述type defy struct CT no de inter child struct CT node信号list。星号敲的ptr那么这是定义孩子界的这样一个结结构体的类型的，这样一个名，

这样一个指针的，这样一个名称。那么，还有一个双星节点结构type defy struct element data child ptr first child孩子念的头指针。city box那么就是定义一个结构体类型的这样一个名称。那么，树结构呢？是type defy struct city box nodes max tree size in tn啊节点树和根的这样一个位置。ctree那么定义一个结构体的这样一个类型的名称。那么，又与双星表示法相反，孩子表示法呢，便于实现孩子的操作实现，但不适合来找双星的操作，我们可以呢，

把孩子表示法和双星表示法呢结合起来。那么，在这样一个的这样一个类型部分当中呢？那么，这样的是一个数据域，一个first child。那么，这样一个第一个孩子，这样一个域的，这样一个纸上的，这样一个部分。那么这样呢，每个节点呢？每个节点呢，当中呢，

有它的这样一个孩子的这样一个部分，那么指向他孩子的这样一个部分，那么也也有这样一个。将双星表示法和孩子表示法表示结合起来呢，就是把双星表示和孩子链表那么合在一起。那么这样呢，我们就就就能够呢？那么能看到这样一个双星，表示和孩子链表的这样一个表示的这样一个方式。那么接下来呢？我们再看一下数的二叉链表，也就说孩子兄弟存储表示法，用一看二叉链表来表示数。链表中的结点的两个指针域分别是该节点的第一个孩子和下一个兄弟，那么我们来看一下，

首先呢，是根结点a。a呢？它有。它的这样一个。两个指针域，那么第左边的这个左指针域呢？指向它的第一个孩子，右指针域呢？指向它的下一个兄弟啊，比如说他第一个孩子呢是b，那么左指针域呢？就指向b。b呢它没没没有指数，没有孩子，

没有指数，那么就左指针余额为空，那么它的右指针余额指向它的下一个兄弟，那么就是c。c的c的下一个右右指针的域呢，指向它的下一个兄弟也是d那么c呢，它还有两个孩子，它左指针呢，指向第一个孩子e。右指针呢，那么一的右指针呢，实际上它的第一个下一个兄弟ff呢，它的左指针呢，指向它的左数g左指数g，那么这就是我们的数的二叉链表，

还是兄弟表示法？那么，我们来看一下。那么，这个节点的结构呢？是有是有，我们的。data以及呢？next.next.sporting sib d.simply type defy struct CS node element.data struct.CS node.信号。

first child.星号next si。sibling CS node，信号CS tree，那么这是定义了。我们。这样一个数据结构，那么这样一个结构体类型的，这样一个名称，它的这样一个类型，以及呢，指向这样一个结构体，它的这样一个指针。那么，数如何转换为二叉树呢？

它的方法呢？就是在所有的兄弟间连一条线，对于每个节点，除了保留其长子的连线外，去掉该节点，与他孩子，与其他孩子的连线。比如说我们这里呢？a.它的左边呢，就连接BB的右边呢，连接c右的c的右边呢，连接db的右边呢，连接ee的右边呢，连接f那么这是我们的数转换成二叉树的这样一个方式。

那么，森林转换成二叉树，什么怎么怎么样的方式呢？森林转换成二叉树，它的方法呢？是f=t1t二一直到tm是森林，可以把这样一个森林呢转换为二叉树的这样一个方式，就是按这样一个规则将森林转。你看二叉树blbrb，若f为空，即m=0，则b为空数。若f非空，则m不等于零。b的根就为森林中的第一棵树的这样一个根。

t1b的左指数lb是t1中根结点的指指数森林f1转换成了二叉树。dttt 1t一二t1n，其柚子树rb是从森林f1飘七二。那么，一直到TM转换成了一二叉树BT 2，一直到TM，那么这是我们申请转换成二叉树的方式。那么我们看一下这个部分，首先呢，森林转换，这是我们一个森林，我们要将它转换成首先，首先将它转换成二叉树，那么a呢？作为根结点b呢，

作为它的这样一个左指数。那么，作为他第一个孩子，那么作为他的左指数，那么c呢？作为b的右指数d呢？作为b的c的右指数，那么e呢？作为b的左指数f呢？作为be的右指数。那么，同样的把g呢？这个这个数呢？转换为我们的二叉树。那么ghi以及呢，

一个单一个单一单一，这样一个根结点g，那么接下来呢，再把我们的。这样的。二叉树呢，把把它把加各个数对应的二叉树呢，给它转化为这样一个森，这样一个对应的，这样一个结合。联系了这样一个二叉树。实现了这个二叉树的这样一个运用的这样一个部分，完了之后a的右结点呢？右子树呢是。右结右孩子了，

是这样一个。GG的u孩子了，是这样一个g那么。同样那么g呢，它的左指数呢，就是h这样一个根据点，这样一个。开始的这样一个部分，那么这样呢，我们就将森林呢转换成了二叉树。那么，二叉树如果转换为森林呢？它的方法呢？是如果bro ot lb rb是一个二叉树，那么只可按这样的规则来转换为森林ft 1t2就到TM若b为空则f为空。

若b非空，则f中的第一个数。t1的根root t1则为二叉树b的根root t1中的根结点的子树森林f1则是。由b的左指数。lb转换成了森林。f中除t1之外的其余数呢？组成的森林fe飘teth到TM是由。b的右子树。rb转化为神的森林，那么这是我们二叉处呢？转化为森林的，那么这样一个方式。那么我们看一下，首先呢a。bcd.

ef转换为一个数，然后呢？ghi转换一个数那么g呢？转换一个数那么这样呢？就转换为了森林。那么，我们就将我们的二叉树呢，转换为了森林。那么，接下来我们看一下树和森林的便利。那么数的变利呢？有三条搜索路径，一个呢是先续便利，先跟便利。一个呢是后跟便利，

还有一个呢是层次便利。树的先根遍地呢，那么就是若树不空，则先访问根结点，然后依次先跟访问遍地各棵子树。后跟便利呢，就是若数不空，则先依次后跟便利后各指数后，然后访问根节点。层次便利呢，就是若数不空，则自上而下，自左至右，访问数中的每个节点。那么，

我们首先看一下，先跟变利时的次序abe FC d。ghijk那么这是先跟。便利。顶点时的。先跟便利时间内的访问次序，那我们再看一下后跟便利零点时的次序呢ef BC。ijk hg da那么这是后跟便利时的这样一个访问次序，那么我们看一下层次便利呢？层次便利就是abcdefg。hi JK，那么这是我们层次便利时顶点的访问次序，那么我们再看一下森林的便利森林呢？由三部分组成。森林中第一个树的根结点，

森林中第一个树的指数，森林和森林中其他树构成的森林。那么，先驱遍历呢？是若森林不空，则访问森林中第一个数的根结点。先序遍历森林中第一个数的指数。森林先序遍历森林中除第一个数之外，其余数构成的森林。那么也就是说，依次呢，从左至右对森林中的每一棵树呢，进行先耕便利，那么中序便利呢，就是说森林不空则中序便利，

森林中第一棵指数的指数森林。访问森林中第一棵树的根结点中续便利。森林中除第一棵树之外，其余树构成的森林，也就是说我们从左至右对森林的每一棵树呢，进行后跟便利。那么，接下来我们看一下数的遍历和二叉树的对应的关系。树呢，它的先跟便利。对应于森林的先续便利，对应于转换成二叉树的这样转换后的二叉树的先续便利，那么这个大家要记住。而树的后跟便利呢？对应于森林的中序便利，

对应于转换后的二叉树的中序便利，这个大家要记住，也就是说。树的先驱便利，对于森林的先驱便利，对于转换后二叉树的先驱便利，而树的后跟便利，对于森林的中序便利，对于转换后的二叉，树的中序便利。那么，接下来我们看一下哈弗曼术进行运用，那么首先我们来看一下哈弗曼术，那么这样一些概念，那么从什么是路径长度，

从一个节点？到另一个结点的分支数称为这对节点间的路径长度，树的路径长度呢，是从树的根到每一节点的路径长度之和。那么，比如说我们。节点的路径长度，那么n的路径长度呢？那么是n节点的路径长度呢？是从根节点到该节点的路径上所包含的边的数目。那么，比如说n的路径长度呢？那么就等于四。树的内路径长度呢，就除了业绩点外，

从根到树中其他节点路径长度之和。树的外路径长度呢，是从叶根的，是从根结点到树中所有叶子结点的路径长度之和。那么，树的路径长度呢？用PL表示，那么比如说这里树的路径长度，那么就一+1。加二+2。那么再加二那么再加二的这样一个部分呢？那么等于十，这就是数的路径，长度数的路径，长度呢？

用po表示，比如说我们这样一个数的路径，长度是十，那么这样一个路径，长度呢？是零一零+1。加一+2+2+3+3，那么等于12那么这样一个路径长度呢？等于12。那么这样呢，结点的带全路径长度呢，是从该结点到树根之间的路径长度与结点上全的神级。那么，树的带全路径长度呢？那么，

称之为wpl树中叶子结点带全路径长度之和，那么，这wpl呢？那么，我们看这个图当中wpl呢？等于七×2+5。五×2+2×2+4×2=36。数的代全路径长度呢？记住wpo=sigma k=1到nw kl k，其中呢？wk为每个叶子节点的。全lk呢，为每个叶子节点呢，到根的路径长度那么比如说我们这wpo呢，那么就等于这样一个每个叶子节点的全来乘以每个叶子节点到根的路径长度，

然后呢，把它们加起来。得到了我们的代数的代权，路径长度，而代数的代权路径长度最小的二叉树呢，就称为最优二叉树或者哈弗曼树。那么，哈夫曼数呢？就是加权路径长度最小的二叉树，那么就是哈夫曼数那么公式呢？w7幺等于k点一到nw k ok，比如说我们这样一个哈夫曼，这样一个。二叉树呢？它的这样一个。

代权路径长度呢是36这样一个代权路径长度呢是46，那么这样一个二叉树，它的代权路径的长度是35。那么我们看一下如何构造最优数哈弗曼数的这样一个算法好吧，给根据给定的n个全值w1w2一直到wn。构造n颗二叉树的集合f=t 1t二，一直到tn，其中每棵二叉树呢，均含有均只含有一个代全值，为WI的根节点。且左右指数为空数，那么接下来第二步呢？是在f中选取其根结点的全值为最小的两棵二叉树。分别做左右指数构造一棵新的二叉树，并将这棵二叉树呢根节点的全值。

设为即，即为设为。左右跟指指数根结点全值的，这样节点的全值之和也就是说我们在f中呢，选择两个根结点的全值最小的。二叉树分别作为左右指数来构造一个新的二叉树，并将这棵新的二叉树的树根的根节点的全值呢？那么作把它把它作为把它把它把它设为。把它把它把它写为这样一个写左右指数跟进的全值之后，把它记为我们左右指数，把它算为我们计算成我们左右指数树根的这样一个全值之和。那么第三步呢，是从f中删除这两棵树，同时呢，加入新生成的新树，

那么重复之前的这两个方法呢？直到f中只含有一棵树为止，我们来看一下这个过程。已知全值w等于五六二九七，首先呢，我们找到两颗最全值最小的，那么就是五和二，那么五和。五和二呢，那么构作为我们的左右指数，构造出一个新数，那么它的根结点的值呢，那么就是我们的七。根结点的值呢，就是我们的七，

那么接下来呢，我们把五和二呢，从当中呢去掉，把七呢加入到这样一个组，这样一个。这样一个范围，这样一个组，组合当中，那么接下来呢？我们找到。全值最小的两棵树，两棵树。六和七。那么这个时候呢？我们把六和七作为左右指数，

构造出一棵新的树，那么得到的根结点的全值呢？是13，那么接下来呢？我们把六和七呢？从这样一个。部分当中删除，那么把13呢加入到其中，那么接下来呢？我们。再从这个范围当中呢，找到根据点的全值，最小的两个数，那么找到的呢是七和九，那么这个时候呢，

我们把七和九呢作为左右指数，那么构造出一个新的数。那么，构造出了新的数的这样一个跟进人的全值呢？就是16。那么，接下来我们把七和九呢从这个组合当中删这个。部分当中删除，那么把16呢加入其中，那么接下来呢，再从这个集集合当中呢，找到全根节点，全值最小的两棵树，那么就是13和16，那么这个时候呢，

我们再把这两棵树呢，作为它的左右指数呢？构造出一个新的数，那么它的全值呢？就为29那么这样呢？我们采取这样的方式就构造出了我们这样一个哈弗曼数。那么我们再看一下哈佛号码编码的问题，就是不等长串的编码，假设电文中只使用abcdef 6种字符，那么现在要发送以下电文BD的acdbf de那么简单方式呢？就是等长编码用。abcdef依次编码了零零一零零一零一零零一零零一一零零一零一，那么只要这样一个电文对应的编码呢？是这样一个部分，那么这样一个编码的总长度呢？

是30位那么？一般情况呢l=I=1 sigma I=1点ncioi，其中n为字符总数I。ci和li为字符对应的频率和编码长度，那么就是我们的这样一个编码的，这样一个。的行的学习的这样一个啊，编码的这样一个运行的这样一个那么这样的有这样一个编码了，那么就是说我们编码的这样一个。z连接的这样连续的这样一个连连续的这样一个长度的这样一个部分，我们采用不逞强编码，让在电文中出现的次数频率高的字符呢都有点短的编码。所以传送的总长度呢，将缩短，比如说对上面的电文呢，

采用这样一个编码a是零零零b，是1c是零一零d，是0e是一零零f，是一零一，那么这样的编码的总长度呢，就要少少少一些这样一波。少一些，但是这样的编码当一到零一零时呢，将产生二义性d的编码是AC编码的前缀b的编码呢，是ef的前缀，因此呢，若要进行不等长编码。所以要求任意一个字符编码呢，都不是另一个字符编码的前缀，这种编码呢，

称为前缀编码，那么如何得到总长最短的前缀编码呢？我们就可以采用哈弗曼书的这样一个构造的形式呢，来来。得到我们这样一个。需要需要需要使用需要得到的，这样一个需要运用的，这样一个前缀编码，我们是需要得到这样一个总长最短的前缀编码，那么我们设电文中出现的字符种类为n个WI和li的，分别为第I个字符在电文中。出现的频率和其编码长度则电文长总长呢，为l=sigma I=ewili，那么从上面的公式呢，要看l总长最短，

要是l呢最小了就可以。如果把n个字符看成一棵树的n个叶子节点WI作为第I个节点的全值，一作为看成从根到节点I的路径长度。则问题呢，转化为求n个字符的哈弗曼数。那比如说我在这样一个图当中呢，我们的字符集s tae I，它出现的频度呢，分别为五六二九七，那么我们呢，可以用构造哈弗万数的这样一个方式呢？来进行，我们可以用构造。哈夫曼说的这样一个方式呢，来来找到它的这样一个。

前缀编码那找到这样一个前长度最小的，这样一个前缀编码，那么就是说我们这样一个形式，那么所以说我们的编码我们我们按，并且呢，我们并且呢，我们得到这样一个have数的这样一个编码的这样一个情况。然后呢？我们按照左分支，按照左分支是左左指数的，这样一个分支呢是零编码为？这样一个字符为零，又又指出了这样一个又分这样一个分值呢？右边的分值呢？为一来进行这样一个编码的方式，

那么就是说。那么等于说构造哈弗曼数之后呢？求哈弗曼编码的主要方式呢？由叶子为那么那么去进来进行这样一个编码，那么这样呢？我们可以呢？就是说构造了哈弗曼数之后，我们求哈弗曼数的主要编码呢？主要方式呢？就是这样一个按分支呢？赋予零和一这样一个编这样一个符号呢？来进行编码的这样一个方式，那么也就是说，构造哈夫曼数之后呢？求哈夫曼主要编码的方式呢？

那么就是说，这样一个。实现的用到这样一个。实现联系，那么就是这样一个。运用的这样一个实验方式，那么就是采取了这样一个。运用的这样一个编码的这样一个形式，那么左分支呢？设置为零，右分支呢？设置为一，那么六呢？这里就是零零七呢？就是零一，

那么二呢？就是一零零五呢？就是一零一。那么11呢？就是一一那么就是这样呢？我们找到了这样它的这样一个编码，那么这样呢？采取这样的构造，哈夫曼数的方式呢？我们就找到了这些。字符的这样一个哈弗曼编码，也就是说它是长度最长度最小的，这样一个前缀编码，那么我们就可以采用这样的方式呢？得到我们的哈弗曼编码。

那么，符合前缀编码的规则呢？才能按唯一性进行一码啊？好同学们，那么今天呢？我们给大家讲了这样一个。数和二叉树那么这样一个部分，那么接下来我们进行一个总结，那么数和二叉树呢？是一类具有层次关系的非线性数据结构。那么二叉树呢？是一种常用的树形结构。二叉树呢？具有一些特殊的性质，大家要注意，

我们二叉树就是满二叉树的性质。以及呢，完全二叉树的性质，以及呢，二叉树那么它的这样一个一一般情况下，它的这样一些性质部分，它这样一些性质。那么二叉树呢？有两种存储表示顺序存储和链式存储顺序存储呢？就是把二叉树所有的节点呢？按照层次顺序呢？存储到连续的存储单元中，这种存储呢？更适合于完全二叉树。链式存储了就就清二叉链表，

每个节点呢，包括两个指针，分别指向其左孩子和右孩子。链式存储呢，是二叉树常用的数据结构。数的存储呢，有三种双亲表示，孩子表示和孩子兄弟表示孩子兄弟表示法呢，是常用的表示法，任何一棵树呢都能通过孩子兄弟表示法呢，转换成二叉树进行存储。声明和二叉树之间呢，也存在相应的转换方式。通过这些转换呢，可以利用二叉树的操作解决，

一般树的有关问题，二叉树的遍历算法呢，是其他运算的这样一个基础。通过遍历得到二叉树中节点访问的这样一个线性序列，实现了非线性结构的线性化。那么，根据节点访问的次序不同，可得到三种便利，先序，中序和后序。直线复杂度呢，均都是这样一个on在线索二叉树中呢，利用二叉链表的2 n+1个空链域呢来存放某种便便利词语下的前句节点和后句节点的指针。这些附加的指针呢，就称为线索通过了引入二叉线索数的目的呢，

是加快查找节点前驱和后驱的这样一个速度。那么，哈佛曼数呢？在通信编码基础上，有广泛的应用，那么只要构造了哈弗曼数按分支情况呢？在左路径上，代码写一右路径上写代码一，然后呢，从上到下。相应路径的代码序列就是该页节点的这样一个前缀码，就是我们的就是我们的最优前缀码，就是我们的哈弗曼。哈弗曼编码。那么这个时候最后呢？

大家要掌握我们数的便利以及呢？森林的便利和我们转化成了二叉树的便利的这样一个对应关系，树的便利呢是？是先更便利，对应于森林的先更便利，对应于转换后二叉树的先更便利。树的后跟便利呢，对应于森林的中序便利，对应于转换后二叉树的这样一个中序便利，那么大家要记住这样一个，记住这样一些部分。那么那么我们大要求，我们希望呢？那么大家呢？要掌握二叉树的性质和存储结构。

熟要掌握二叉树的前中后续便利算法，以及呢，掌握线索化二叉树的基本概念和构造方法，以及呢，掌握哈夫曼树。以及哈夫曼编码的构造方法，以及呢，利用数的孩子兄弟表示法将一般的数结构转换为二叉树来进行存储，以及呢，掌握森林和二叉树之间的相互转换方法。那么大家下来之后呢？那么再看一下这些部分进行一个了解和熟悉好，我们今天的课呢，就讲到这里好，谢谢大家。

		自动登录	找回密码
密码			立即注册