二叉树的概念和术语

1、2020年7月1日，第6章：树，6.1树和二叉树的概念和术语6.2二叉树的存储结构6.3二叉树的遍历，线索6.4树、二叉树和森林的变换6.5哈夫曼树算法及其应用6.6总结和练习，2020年7月1日，2.6.1树和二叉树的概念和术语，首先提出问题(1)一个家庭的血缘关系：2020年7月1日，3。(2)承德石油学院组织机构图介绍树形结构，2020年7月1日，4。第二，树A树的定义是N (n0)个节点的有限集合。否则，它满足以下两个条件：(1)只有一个特定的节点称为根。(2)除根节点之外的其他节点可以被分成m(m 0)个不相交的子集T1、T2和Tm，其中每个子集T1本身是一棵树，并且被称为根的子树。

2、在2020年7月1日，下图显示了一个有10个节点的树，即T=A，B，C，I，J。节点A是树T的根节点，除了根节点A之外的其他节点被分成两个不相交的集合：T1=B，D，H，I，J和T2=子树T2以C为根节点，并且可以被分成集合T21=F，G。这样，您可以继续划分成更小的子树，直到每个子树只有一个根节点。在2020年7月1日，6日，树具有以下两个特征：(1)树的根节点没有前置节点，除了根节点之外的所有节点只有一个前置节点。(2)树中的所有节点可以有零个或多个后续节点。从这个特征可以看出，右边的图形不是树形结构。2020年7月1日，7日，3日。树的相关术语节点：一个数据元素和指向其子树的几个分支。节

3、点度：一个节点拥有的子树的数量称为节点度。树的度：树中节点的最大度。下图中，节点B、C和D的度数为2；树的度数是2。叶节点：0度的节点称为叶节点或终端节点。分支节点：度不为0的节点称为分支节点或非终端节点。图中的节点H、I、J、F和G是叶节点。节点a、b、c、d和e是分支节点。2020年7月1日，8，子节点、父节点和兄弟节点：树中节点子树的根称为节点的子节点。因此，该节点被称为子节点的父节点。父母相同的孩子被称为兄弟。祖先和后代：从根节点到树中某个节点的分支上的所有节点都称为该节点的祖先。相反，子树中以节点为根的任何节点都称为该节点的后代。2020年7月1日，9，节点数：规定树根节点数为1，其

4、他节点数等于其父节点数加1。树的深度：树中所有节点的最大层数称为树的深度或高度。在图中，节点A有1层，节点B和C有2层，节点H、I和J有4层，树深度为4。父母在同一级别上是表亲，例如，节点d、e、f和g是表亲。2020年7月1日，10，有序树和无序树：如果树中节点的子树是从左到右排序的，那么该树称为有序树；否则，它被称为无序树。后面提到的二叉树是有序树。森林：m(m0)个不相交的树的集合称为森林。2020年7月1日，11，4。二叉树1的定义和性质。定义：二叉树是一个有限的节点集，它或者是空的，或者是由一个根节点加上两个不相交的二叉树组成的，这两个二叉树叫做左子树和右子树。确定下列树是否是二叉树

5、。理解二叉树的特点：节点度2。2020年7月1日，12，2。二叉树的五种基本形式，2020年7月1日，13，属性1如果二叉树的级别从1开始，在二叉树的I级中最多有2i-1个节点。(i 0)证明：(递归方法)性质2中高度为k的二叉树最多有2k-1个节点。(k 1)证明：n=20 21 22 2k-1=2k-1，2020年7月1日，14，属性3对于任何二叉树，如果叶节点数为n0，非叶节点数为n2，则N0=N2 1证明：如果有n个节点的度数为1(其中：1如果边的总数为e，根据二叉树的定义，有以下公式：n=n0n 1n 2e=2n n1=n-1。应用数学的知识证明，在2020年7月1日，如果二叉树的高

6、度是h，如果二叉树的每一层都到达节点，如果除了h层以外的所有层(1 h-1)的节点数都达到最大，则h层从右到左连续缺少几个节点，构成一棵完整的二叉树(如下图(b)所示)。在2020年7月1日，16日，在属性4中具有n个节点的完全二叉树的高度是“log2n”1。证明了当完全二叉树的高度为h时，以下公式成立：2h-1-1 n 2h-1或2h-1 n 2h。取对数，得到h-1 log2n h，即h= 17，性质5如果一棵完整的二叉树有n个节点，在同一层从上到下，从左到右连续编号(1，2，n-1，n)，那么树中的节点按照这个节点编号依次存储在一维数组中，编号为I的节点简称为节点i (1in)。有以下关

7、系：(1)如果我=1，我没有父母；(2)如果我大于1，那么我的父母是1/2；(3)如果2in，I的左子为2i；如果2i 1n，则I的右子为2i 1；2020年7月1日，18，6.2。二叉树的存储结构，1。顺序存储结构(数组方法)存储原理一组具有连续地址的存储单元用于从上到下、从左到右依次存储完整二叉树上的节点元素。这非常适合完全二叉树和完全二叉树。2020年7月1日，19日，根据二叉树的性质5，一维数组中节点的相对位置暗示了节点之间的关系，因此从数组中节点的下标I中可以方便地找到它们的父节点i/2或左右子节点2i 2i 1。在2020年7月1日，如果二叉树不是一个完整的二叉树，就应该补充为一个

8、完整的二叉树(如下图所示)。2020年7月1日，21，存储功能存储方法很简单，但它需要严格的空间和连续的空间。当二叉树不完整时，会浪费更多的空间。例如，深度为4且只有右子树的二叉树需要分配15个数据存储空间。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15，2020年7月1日，22，链式存储结构(二叉树的第二种存储结构)存储原理二叉树是用不连续的存储单元存储的，二叉树的逻辑结构应该保持不变。存储类型 (1)二进制链表：节点，左指针(指向左子)，右指针(指向右子)；(2)三链表：节点，左指针(指向左子节点)，右指针(指向右子节点)，父指针(指向节点的父节点)，2020年7月

9、1日，23，节点结构：typedef结构节点 elementtype data结构节点*leftChild，* rightChild BinTNode，2020年7月1日，24，存储功能链式存储结构的特点是使用数据字段来表示节点，使用指针字段来指向它们的子代和父代，并使用不连续的存储空间来存储。2020年7月1日，25日，建立二叉树的二叉链表算法思想对于任何二叉树，首先根据全二叉树对其节点进行编号。设置一个辅助向量p来存储指向节点的指针，例如pi中编号为I的节点的指针(地址)。每次输入一对数据，都会生成一个新的节点s，节点指针保存在pi中。当i=1时，它是根节点，当i1时，它的父节点是j=i/

10、2。如果我是一个偶数，让pj-lchild=s，否则让p j-rchild=s。这样，每个节点都与其父节点相连，从而建立一个二进制链表。，2020年7月1日，26，算法实现 BtNode *Creat_Bt() printf(“输入顶点及其编号”)；Scanf (%d% c ，图解说明，2020年7月1日，2020年6月3日，遍历二叉树，提示问题：为什么要遍历二叉树？1.问题介绍：树和二叉树是典型的层次结构(即一对多关系)。如果你想详细了解和研究这个结构，并对它执行各种操作，你必须处理由它形成的节点。例如，要在树或二叉树中找到具有一定特征的节点，或者要逐个处理所有的节点，就需要查询结构中的特定

11、节点，因此引入了二叉树的遍历操作。2020年7月1日，28。二叉树的遍历1。二叉树的遍历是按照一定的顺序访问二叉树中的节点，并且只需要访问每个节点一次。2020年7月1日，29日，2。二叉树的遍历(以先左后右的顺序遍历为例，其他三种都相似)(1)遍历VLR算法流程否则，访问根节点；首先遍历左边的子树；首先遍历右子树。算法示例如右图所示，预序遍历的结果是：- a * b-c d/e f，2020年7月1日，30，预序遍历-算法实现 (I)递归算法void预序1 (bin tnode * bt)/*递归预序遍历以bt为根/*访问根节点*/preorder 1(Bt-lchild)；/*遍历左子树*

12、/preorder 1(Bt-archild)；/*遍历右子树*/*前序1 */，2020年7月1日，31，(2)遍历LVR(Inorder Traversation)算法过程(递归算法)如果二叉树为空，则为空；否则，按中间顺序遍历左边的子树；访问根节点；以中间顺序遍历右子树。算法示例如上图1中的二叉树，根据该方法以中间顺序遍历它，结果是：a b * c-d-e/f，2020年7月1日，32，算法实现: (I)递归算法Void inorder1(BinTNode *bt) /*以中间顺序*的bt为根遍历二叉树。/*按顺序遍历根节点*/printf(Bt-datd)；/*访问根节点*/order

13、 1(Bt-archild)；/*以中间顺序遍历右子树*/，2020年7月1日，33，(ii)非递归算法(通过堆栈实现)无效于顺序2(bint node * Bt) p=Bt；top=0；而(p|top) if(p) /*二叉树不为空*/ stop=p；顶部；p=p-lchild。其他-top；p=s顶部；printf(p-data)；p=p-r child；)，图形演示，2020年7月1日，34，(3)后顺序遍历LRV(算法过程)(递归算法)如果二叉树是空的，它将是空操作；否则，按顺序遍历左子树；按顺序遍历右子树；访问根节点。算法示例如上图1中的二叉树所示，结果是：a b c d-* e f

14、/-，2020年7月1日，35。示例：从预排序序列ABCDEFGH和中间排序序列CBEDAGGHF恢复二叉树：方法：预排序序列ABCDEFGH(注意：a是根)，中间排序序列CBEDAGGHF。思考问题：从节点序列中恢复二叉树，2020年7月1日，36；从左子树先行序列构造左子树：BCDE和左子树中间生成序列：CBED；类似地，从右子树先行序列构造右子树：FGH和右子树中间基因序列GHF:2020年7月1日，37。6.4树、二叉树和林的转换1。树1的存储结构。父代表示存储特征:一组连续的空间用于存储树的节点。为了表示它们之间的关系，每个节点都添加了一个指示符来指示其父节点在链表中的位置。这种存储

15、方法对于节点的父节点来说很方便，但是对于子节点来说却很麻烦。，2020年7月1日，38。这种存储结构使用一维数组来存储通用树，如上图所示，因为每个节点(除了根节点)只有一个父节点。在这种结构中，当查找节点的父节点时，您可以通过访问其父字段来找到其父节点的存储位置；但是要找到一个节点的子节点，需要遍历整个数组。2020年7月1日，39日，2。子表示存储特征:一组空间用于存储节点和节点的子节点。由于子字段的数量，可能有一个或多个，因此可以使用多个指针字段来指示。node definition (1)子节点的定义# define maxsize 100 typedef结构节点 int childstruct CTNode * next * ChildPtr，2020年7月1日，40，(2) typedef结构 elementtypedataChildPtr firstchildCTBox。(3)Typedef结构 CTBox节点MAXSIZE；int n，r；携程；2020年7月1日，41，森林与二叉树之间的转换，2020年7月1日，42，6.