10.第10节课第6章树

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

好同学们，大家好，今天呢，我们来给大家讲一下数据结构当中。数以及呢二叉树。这样一个部分。那么呢，我们的树结构呢？是一类比较重要的非线性数据结构。那么直观来看呢，数是以分支关系定义的层次结构。树结构呢，在客观世界中呢。广泛存在，比如说人类社会的族谱和各种社会机构组织了，

都可以用数。来形象表示。数在计算机领域中呢，也应用比较广泛，尤其呢，以二叉树最为常用。比如，在操作系统当中，用书来表示文件目录的这样一个组织结构。在编译系统中呢，用书来表示原程序的语法结构。在数据库系统中，数据结构呢，也是信息的重要组成形式之一。我们这节课呢，

主要来讨论一下二叉树它的存储结构及其操作。研究一下树和森林与二叉树的转换关系，最后呢，介绍一下树的应用。呃，我们之前讲过的线性表。债对应串。数组和广义表那么这些呢？债和对立和线性表以及我们的数组广义表呢，它属于我们的线性结构。而我们的这个数呢，和二叉树呢。它是非线性数据结构，比如说它并不是我们的线性结构。我们呢，

来看一下书的定义。包含nn大于零个节点的有穷集合k。且在k中定义了一个关系nn满足以下条件，有且仅有一个结点k0。它对于关系n来说没有前驱称k0呢为数的根结点。除了k0之外，k中每个结点对于关系n来说有且仅有一个前驱。k中的个节点对关系n来说呢，可以有m个后继m大于等于零。也就是说，若n大于零一呢，除根据点之外的其余数据元素呢，被分为m个互不相交的集合t1t2就到TM。其中，每个集合ti本身又是一棵树。

数t1t2 TM呢？称作数，称作根结点的子数。啊，这是我们书的定义。我们来看一下这样一个图。其中呢，图a。是只有根据点的数。只有一个节点，就是我们的根据点。图b呢，就是我们一般情况下的这个数，它有根结点，有后继结点，

有子数。那么指数呢？还有指数。那么，我们来看一下这个数的这个。形式树的根结点呢，它没有前驱节点，且除了根节点之外的所有节点呢，尤其只有一个前驱节点。负节点呢，可以有零个或多个后期节点。数的表示方法呢，有我们的直观表示法，有形式化表示法。直观表示，

法呢，就是我们直接呢。画一张图，那么画出竖的图，那么就可以那么进行表示。那么我们还可以呢。用网易表的方式。来进行表示。那么，这是我们的广义表的方式。根结点呢。作为指数。森林。组成的表的名字。写在左边。

那么，这是我们的。广义表达这样一个形式。这是我们数的表现形式。接下来我们看一下数的常用术语。比如说数的结点，那么什么叫做数的结点呢？包含一个数据元素及若干指向其指数的分支。就是我们的数据节点。那么，4度是什么呢？节点所拥有的子数的个数。称为该节点的度。比如说我们的。a节点。

第一节点呢，它是我们的根结点，它有我们的三个指数。所以说它的数，它就它的度呢，就是它拥有的节点的各拥有的指数的个数。叶子节点是什么呢？就是度为零的点，就是没有指数的节点。比如说我们的k le kl g him。这些呢，都为零的点呢，称为我们的叶子节点。非终端节点呢，就是不是叶子节点的节点，

就是度不为零的节点。孩子是什么呢？孩子节点呢？是节点的子数的根称为该孩。节点的孩子。比如说bcd是a的孩子ef是b的孩子kl是f的孩子。你说节点的指数的根呢？称为该节点的孩子。那么，兄弟是什么呢？同一个双亲的孩子之间呢？不称为兄弟，比如说。bcd它是同一个双亲，它是我们的兄弟之间ef是同一个双亲，

它是我们的双亲之间。hig是我们的同一个双星，他们的节节点，他们的双星呢？是同一个节点，这个时候呢？hig.是兄弟姐妹。节点的主线呢，是从该根到该节点所经分支上的所有节点。那么，这是节点的主线，就是从根到该节点所经分支上的所有节点呢？称为节点的主。先子孙呢，

是以某节点的根的为的子数中任意节点呢，都称为该节点的子孙。那么，这是我们的数的常用术语。那么，层次性是什么呢？从根开始定义树为第一层。跟着孩子呢，为第二层。节点在l层。其子树的根呢？就在l+1层。数的深度是什么含义呢？数中各节点层次的最大值称为该数的深度。这就是我们的数的深度，

也就说数的各节点层次的最大值。称为该数的深度。比如说我们的数的各节点的层次的最大值称为。该数的。深度，比如说我们这样一个图当中。这个数呢？它的深度呢？就是。节俭。层次的最大值就是我们klm这个，这三个节点它其实它它的节点的这样一个层次的最大值。那么四就是我们树的这样一个深度。那么，有序数是什么呢？

有序数将数中各节点的各指数呢？看成从左向右是有次序的。称为该数呢，是有序数。那么，森林是什么呢？森林是m棵互不相交的树构成的有限集合。比如说f=t 1t2 TM，其中呢？ti是树当m=0时f呢？是空森林。对于树中某一个结点而言，其子树的集合呢，就为森林。反过来，

对于另外呢，对于森林，若给森林f1 fttt 2 TM中的每棵树的天节点呢。都赋予一个同一个双清节点，那么就构成了一棵树。那么我们负的。操作的有这样一些操作，比如说以零收。t初始化一个数。root x.求结点x呢，所在处的根结点。它们的tx。求数中结点的x的双清结点。跳的tx I求数中结点x的第I个孩子的结点。

insert tx is把s呢为结点的数呢，插入到数t中作为结点。x的第二个指数。delete tx I在数中删除节点x的tx指数。color thing.travels诶t按某种方式呢？访问。副题中的某个节点，确实每个节点呢，只被访问一次。好，我们接下来再看一下二叉树，二叉树是什么呢？二叉树，它的定义呢？

它是由n个结点构成的集合n呢？大于等于零。当n为零的时候呢。是空数。或者呢？是有一个根结点和两颗分别称为左右指数的互不相交的二叉树构成。也就是说，我们的二叉树呢？要么？是一个空数。要么是一个由。要么是有一个根结点和两科。分别称为左子树和右子树的互不相交的二叉树组成。当p呢，不等于空集的时候呢，

那么t满足一些条件。存在唯一的数据源所r。属于t小二啊，在t中没有直接前驱称为根结点。若t-r不等于空集，则t-r存在划分t1t2t1交上t2并上t2呢？等于t+2 t1，加上t2呢？等于空集且t1t2的均是二叉树，并且呢？命名t1是t的左指数t2呢？是t的右指数，那么这是二叉树的这样一个定义。比如说我们看一下这个图，这个图当中啊，

它就是一棵二叉树。其中呢，这它就是一个二叉树的形式，其中呢a呢，是它的根结点。这方这一部分呢？是它的所指数。右边这一部分呢，是它的右指数。那么，佛子树。当中它根结点的左边这一部分呢，又是卓指数。右边这一部分呢，又是它的业务指数。

这是我们二叉树的这样一个形式。二叉树呢，可以表现出五种基本状态。比如说空树。就是不含任何。节点的这样一个数称为空数。或者说只含根结点的数。那么，只只含根据点来查出。或者说我们的。右子树为空的，空树的这样一个情况。或者说，左指数为空的这样一个情况。第五种呢，

是左右指出了均不为空数的这样一个情况。我们来看一下二叉树的基本性质。在二，它是第I层上。至多有二的I次方减一个结点I呢，大于等于一。也就是说什么意思呢？我们第一层呢，有一个节点。第二层呢，有两个节点。第三层呢，有四个据点。第四层呢，最多有八个节点。

那么就说二叉树的第I层上。至多有二的i- 1次方的结点。那么，这是第一个性质，那么大家要注意，这是第一个性质。那么，第二个性质是什么？深度为k的二叉树。是多含二的k次方减一个结点，那么我们想一下二叉树。当只有第一层的时候呢，它只有一个节点。当它的深度为二的时候呢，就是一个根结点呢，

还有左右两个指数，那么这个时候它的结点数呢是三。当它的深度为三，就是它的左右指数呢？又有它的左右指数的时候呢？这个时候呢它。它的这样一个根节点数呢？是七它的这样一个节点数呢？是七比如说。深度为k的二叉树上的几点数呢？最多为二的零次方加二的一次方一直加到二的k- 1次方。等于我们的二的k次方减一，那么这是它的这样一个节点的部分，节点的个数。那么，

这个性质性质三呢？是我们二叉树当中比较重要的一个性质。大家呢，一定要进行一个掌握，进行一个了解，而这个数字是什么呢？就是对于任何一个二叉树。它若它含有n零个叶子，结点n二个不为二的结点，则b存在关系，是n 0=n二+1。它都有什么样的含义呢？就是说对于任何一棵二叉树。度为二的结点的个数加一等于叶子结点的个数，那么这是它的这样一个关系的，

这样一个形式，大家要记住这样一个概念。那么，怎么证明的呢？我们设二叉树节点总数n。等于度为零的结点，加度为一的结点，加度为二的结点，那么又因为了二叉树上分子总数。b等于度为一的结点，加上两倍的。不为二据点。而b呢，等于n- 1，等于n 0+n一+n二。

减一那么我们把它总结起来呢？就是我们的n零把它整理起来呢，就是n 0=n二+1。那么，这就是我们二叉树它的这样一个关系式，它就要剔除这样一个关系式，这是我们二叉树当中呢？比较重要的一个一个性质，它经常而它比较呢，容易用到什么大家呢？要了解这样一个关系式，要要记住这样一个性质。n度为零的结点的个数等于度为二的结点的个数呢？加一就这个，大家记住这个性质。

那么，我们还有两类特殊的二叉树，一个呢，叫做马二叉树，马二叉树呢，指的是深度为k，且含有二的k次方减一个节点的二叉树。也就是说，满二叉树的概念呢，就是我们二叉树的每一个节点呢，都有左右子树，它的每一层上的这样一个数量啊。都有这样一个数量，比如说我们每一个节点上面的这样的数量都有这样一个节点的个数啊，这是我们满二叉树。

那么，完全二叉树是什么呢？就是树中所含的m个结点和满二叉树编号为一到n的结点呢？一一对应。比如说我们这样一个数怎么样完成了差数？a节点a有它的所有指数ABC，比如a bbc按照哪儿差数呢？我们编号呢？也是ABC这样编号。而b有它的b有它的指数d1按照马二叉树呢，它也是d1进行编号。那么c=fg那么fg呢？也是按我们的马二叉树执行编号，那么是fg那么d有它的左右指数e有它的左指数。按照我们的马二叉树的编号呢，

它也是hig，那么也就说我们马二叉树呢，就是树中含有的n个节点。和马二叉树编号为一到n的节点呢，一一对应，它们是按照这个顺序来进行排列。接下来我们看一下第四个性质。具有n个节点的完全二叉树的深度呢，是以二为底n的对数。向下趋整加一，这就是我们的具有n个节点的完全二叉树的深度，那么大家呢？这个节点呢？大家要记住这样一个概念。具有n个节点的完全二叉树的深度呢是？

以二为底。n的对数向下取整加一，那么就是完全二叉轴的深度。接下来我们再看一下，若对n个结点的完全二叉树呢，从上到下且从左至右进行一到n的编号。且对完全二次，对完全二叉树中任何一个编号为I的区间，若I=1，则该节点呢，是二叉树的根无双清。否则编号。二分之I向下取整的结点呢，为其双清结点，若I大于n，

则该结点呢，无左还是？否则，编号为2I的节点呢？为其左孩子节点，若2 I+1大于n，则该节点呢？为右孩子节点，否则，编号为2 I+1的节点呢？为其右孩子节点。这些概念呢，大家都要进行，都要记住，那么都要掌握，

那么有有可能要使用这样一个概念，那么大家要掌握这些性质。接下来我们看一下二叉树。它的存储表示。大家首先看一下这个成这个语句井号比上max÷s in 100，这是二尔法四的最大结点数。typedef yt element types to be tree Mark besides，这是我们的。定义我们的用户自定义我们的存储类型的名称，这样一个数组的这样一个名称。数组的这样一个部分，那么接下来呢？s qb÷BT那么是定义了一个BT数组。那么有100个节点的这样一个部分，那么我们的二叉树呢？

可以采用线性。我们可以采用顺序存储表示，以及呢，我们采用链式存储表示。那么，顺序层次表示呢？是用一组地址连续的。存储单元的存储数据为了能在存储结结构中呢，反映出节点间的逻辑关系。必须将二叉树这种结点呢，按一定的规律安排在这组单元中，对于完全二叉树呢。只需按从。按根按从根指数，从根按程按程序存储即可，

依次从上而下，自左至右的存储元素。即将完全注释上编号为I的节点呢，存储在一维数组，下标为i- 1的分量中。对于一般二叉树呢，则应将每个节点呢与完全二叉树上的节点对照。存储在一维数组的相应分项中。那么，这是我们的存储方式。那么，这种结构存储结构呢？仅适用于完全二叉树这样最后最。在最不理想的情况下呢，一个深度为k，

且只有k个节点的单质数。却需要长度为二的k次方减一个减一的一维数组，造成了存储空间的几道大会。那么，所以对于一般二叉树呢，更适合采用的是我们的链式存储结构，采用的是链式存储结构。那么，这是二叉树的面试存储结构。我们设计不同的节点结构呢，可构成不同形式的链式存储结构，由二叉树的定义可知，二叉树的结点呢？有一个数据元素和分别指向。其左右指数的两个分支构成则表示，

二叉链表中的节点呢，至少包含。三个域数据域。和左右指针域那么有时候呢，为了便于找到节点的双期。还可以在节点结构中呢，加上一个指向其双亲的。指证据。那比如说我们这样一个部分。包含了实际上其双亲的。双星节点的指针域。啊，是这样一个运用的，这样一个方式。那么，

利用这两种节点结构呢？所得到的二叉树的存储结构呢？分别称为二叉列表。和三叉链表。链表的头指针呢？指向二叉树的根节点。在还有n个节点的二叉列表中呢，有n+1个空间域。那么我们可以呢，在在等在接下来的这样一个内容当中呢，我们可以看到可以利用这些通用域的。存储其他有用信息，从而得到另一种面试存储结构线索链表。那么我们看一下。我们来先看一下这个。

存储的这样一个方式。比如说二叉链表，比如说我们这样一个二叉树，二叉链表呢？它的左指针域。指向他的左孩子。右指针域指向它的右孩子，比如说我们a它的左指针域呢？指向b右指针域呢？指向c。b的左指针域指向d右指针域指向ee的左指针域指向g。又只增加了指向h，这是我们的二叉链表。三叉链表的在节点中呢，增加了一个指向其双清节点的指针域，

比如说。增加了一个指向其双星节点的这样一个指针意义，比如说三叉一秒这样一个部分。那么，我们来看一下二叉链表。表示二叉树的C语言的类型描述还不及范。SBB BT漏斗。TXT AB data.drug BT load信号l child信号r child。BT load星号b tree，那么我们的b tree呢？就是我们这样一个结构体。的这样一个名称，那么星号B区呢，就是我们指向这样一个结构体变量，

这样一个指针的，这样一个部分。那么，我们的节点的结构呢？就是l child。和我们的data以及我们的r child那么这样一个部分。那么我们再看一下三叉链表，表示二叉四的C语言的类型描述还不及在抓的吹。谁提豆的，谁提豆的？ta里面的type data drastic it y load。星号6q的星号8q的。struct treaty load星号parent。treaty load星号。所以处理。

那么这里呢？除以t漏的呢？是我们这样一个结构体，它的这样一个名名称结构体的名称。星号是遗漏的呢，是指向我们结构体的这样一个指针的，这样一个部分。它的节点结构呢，就是我们的l跳的。data parent.parent.our child.接下来我们看一下二叉树的便利。在二叉树的一些应用中呢，常常要求在树中查找某种特征的节点。

或者对数中全部节点进行逐一处理，那么这样呢，就提出了一个便利二叉树的问题。线索尔差数是什么呢？线索尔差数是在第一时次遍历时将结点的前去后继续去保存下来。便于再次遍历二叉树。那么，便利二叉树呢？是指按某一。条搜索路径访问附中的每个节点，使每个节点呢，均被访问一次。而且呢，仅被访问一次。访问呢，

它的这样一个含义呢，比较比较广，可以是对节点呢，做各种处理。包括输出节点的信息，对节点进行运算和修改，便利二叉树呢，是二叉树最基本的操作。也是暗杀出了其他各种操作的基础。便利的实质啊，是对二叉树进行线性化的过程。即便利的结果呢，是将非线性结果中的数据点排成一个线性序列。由于阿卡斯的每个级别呢，都可能有两棵子树，

因而呢，需要寻找一种规律，以便呢。使二叉树上的节点呢，能排在一个线性对列上，从而便利便于便利，那么我们可以呢，从二叉树的定义。从二叉树的递归定义呢？可以知道，二叉树是由三个基本单元组成的根结点，左子树和右子树。因此呢，若能依次遍历这三部分，便是遍历了整个二叉树。

那么，目前呢，有三种情况。称之为先更便利，中更便利和后更便利也。称也称为了。先序中序和后序。便利呢，是任何类型均有的操作。对于线性结构而言，只有一条搜索路径，因为每个节点呢，具有一个后继。而二叉树呢，是非线性结构，

每个节点呢，有两个后继，则存在如何便利呢？即按什么样的搜索路径呢？便利的问题。

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