大学数据结构课件--第6章 树和二叉树

1、1，F 6.1树定义和基本术语F 6.2二叉树F 6.3二叉树和线索二叉树F 6.4树和树F 6.6霍夫曼树及其应用程序，特性：非线性结构，一个或多个直接前驱(1: n)，第6章树和二叉树，2，1。树定义，注意：树定义是递归的，即树中有树。由一个或多个(n 0)节点组成的有限集合。在任何非空树t中，有：(1)，只有一个节点称为根。(2) n1中，剩下的节点是不相交的m(m 0)的有限集合T1，T2.分割为TM。每个集合本身都是此根的一棵树，称为子树。6.1树的定义和基本术语，3，A，仅具有根节点的树，根，子树，6.1树的定义和基本术语，4，树的抽象数据类型定义，d是具有相同特性的数据元素的集合

2、。ADT Tree ，Tree，数据对象D:数据操作p2:数据关系r1:如果d为空集，则称为空树；/n=0如果允许d仅包含一个数据元素，则r为空集。在其他情况下，r具有二进制关系。根唯一/根的说明 DJ 8/dk=/子树不相交的说明./数据元素的说明，/至少15个，6.1树定义和基本术语，5，图形表示嵌套集合表示广义表表示凹面表示(目录表示)，树表示，6.1树定义和基本术语，6，图形表示：6.1树定义和基本术语，多个术语，根到根节点(无前体)树系-不相交的m树集合，有序树-节点每个子树从左到右排列，不可互换(左侧是第一个)无序树-节点每个子树可交换位置， 双亲-上层的节点(直系祖先)ie-下层

3、的子树的根(直系后裔)同级-同一父项下的同一层次节点(彼此称为同级)堂兄弟-父项位于同一层次的节点(不是同一父项)祖先-所有从根经过该节点的节点后代-该节点的子代节点-树的数据元素节点数-节点拥有的子树数(有几个直接后缀)节点层次结构-从根到该节点的级别数(根节点为第一层)、叶-度为零的点(终端节点)分支节点-度非零的点(非终端节点)、树的度-。 可以证明，所有树都可以转换为唯一对应的二叉树，而不会丢失一般性。1 .二叉树的定义2。二叉树的特性3。二叉树的存储结构，6.2二叉树，12，1，二叉树的定义，每个节点最多两个子树(不存在的节点2或更多)；左右子树顺序不能颠倒(排序的树)。基本特征：基

4、本形式：具有三个节点的二叉树可以有几种不同的形式？普通的树呢？6.2二进制树-定义，13，2，二进制树的特性，特性1:二进制树的I层最多包含2i-1节点(i0)。问：第I层是否至少有一个节点？特性2:深度为k的二进制树最多包含2k-1节点(k0)。特性3:对于任何二进制树，如果图2中的节点数为N2，叶节点数为n0，则n0=n2 1。，6.2二进制树-特性，14，证明特性3:-二进制树中的所有节点数n=n0 n1 N2(叶数1的连接度为2的节点数)，或/二进制树中的所有节点数n=B 1(总分支数根节点)，(根节点除外)，每个节点，特征：每个层的节点数是最大节点数。您可以连续编号充满二叉树的节点。

5、整个二进制树：具有k深度和n个节点的二进制树，仅当每个节点与具有k深度的整个二进制树的编号为1到n的节点一一对应时，才称为整个二进制树。特征： (1)叶节点只能出现在两个最大的层上。(2)对于节点，如果右分支下的最大下级级别为h，则左分支下的最大下级级别数为h或h 1。6.2二进制树-在特殊情况下为16，6.2二进制树-对于特殊的二进制树为17，对于特殊的二进制树，具有特性4: n节点的完整二进制树的深度为log2n 1。如果属性5: n为具有节点的完整二叉树(深度为log2n 1的节点)的序号，那么对于任意节点I(1In)，例如：1 I=1，节点I就是没有父节点的二叉树的根。如果为I1，则父

6、parent(i)为节点I/2。2)如果为2in，则节点I没有左侧的孩子(节点I为叶节点)。否则，左边的孩子lchild(i)是节点2i。3)如果是2i 1n，则节点I没有右侧的孩子。否则，右边的孩子rchild(i)为节点2i 1。6.2二进制树-特性，18，1，顺序存储结构，3，二进制树存储结构，使用连续地址存储设备集自上而下，从左到右存储二进制树的节点元素。a，b，c，d，e，f，g，h，I，a，f，仅适用于完整的二进制树，对于不完整的二进制树：对每个层次结构中空缺的所有“虚拟节点”进行补充，其内容为0，缺点：缺点插入，删除不方便，6.2二进制树-存储结构，19，2，链存储结构，具有2个

7、指针域的二进制链接表。通常，从根节点开始保存。为了便于查找、节点的父节点，可以添加另一个父域指针，将二进制列表替换为三级列表。关联列表的头指针指向二进制树的根节点。6.2二进制树-存储结构，20，例如，空指针数：2 * n0 1 * n1 0 * N2=2n0 n1=n0 n1 N2 1=n 1，6.2二进制树-存储结构，2 1、1、1、2通过树访问每个节点一次，按搜索路径访问树中的每个节点一次。由根、左子树和右子树组成的二进制树限制了六种遍历方案：根左、根右、左右、右、右、右、右根左、右左、右、右、左、右、右、左、右左、右、左、右、左、右、左、左、左、左、左、左、左、左、右、左、左、左、左、

8、左、左、左、左B、f、h、I、g、C、A，示例1:6.3表示二进制树和线索二叉树，23，1，1，第一次遍历，2，中间遍历，3，下一次遍历， 24，例如，已知二进制树的中间顺序和后顺序序列分别为BDCEAFHG和DECBHGFA。请画这个二叉树。，讨论：如果预序(或后序)和中间序序列已知，是否可以恢复相应的二进制树？分析：子顺序遍历功能，根节点应位于子顺序尾部(即A) 中间顺序遍历功能，根节点应位于其间，左侧部分应全部为左子树的后代(BDCE)，右侧部分应全部为右子树的后代(fhg)。然后，下一步顺序6.3遍历二叉树和线索二叉树，25，已知的中间顺序：B D C E A F H G遍历d e c

9、 b h g f a，A，(D C E)，A，A，B，B，C，6.3遍历二叉树和线索二叉树。26、已知的第一顺序遍历顺序是ABDCEF，6.3通过二进制树和线索二进制树，27，第二，线索二进制树，普通二进制树只能找到节点左右子女的信息，该节点的直接前缀和直接后缀只能在遍历过程中获得。之前和之后保存后遍历如果适用，可以从第一个节点开始快速遍历整个树。例如，中间顺序遍历结果：A/B*C*D E实际上将二叉树转换成线性数组，具有唯一的前缀和唯一的后缀。如何存储这些信息？添加2个域：前体指针，n 1个空链域，6.3遍历二叉树和线索二叉树，28，规定：1)节点有左子树时，lchild指向左孩子。否则，l

10、child直接指向灯泡(线索)。2)节点具有右子树时，rchild指向右孩子。否则，rchild将直接指向后缀(线索)。规则：标记字段为零表示孩子的情况。标记字段为1表示线索情况。6.3交叉二叉树和线索二叉树，29，线索链接列表：由上述节点组成的二进制链接列表线索：前兆和后续节点的指针线索二叉树：添加了线索的二叉树(图形样式)线索：以某种顺序通过二叉树成为线索二进制树的过程，线索过程是遍历过程中修改空指针的过程。将空lchild更改为节点的直接前兆；将空rchild更改为节点的直接后缀。非空指针是？6.3表示二进制树和线索二进制树，30，例如hdibe a fcg，nil，nil，nil，ni

11、l，6.3表示二进制树和线索二进制树，31，树存储结构2。福雷斯特和二叉树切换3。树和树系遍历、6.4树和树系、33、1和树存储结构以及树有三种常见的存储方法。双亲标记孩子标记孩子兄弟标记，1，带双亲标记的存储方法：将树的节点存储为连续空间集合，每个节点都有连接的指示符，指示父节点在连接的表中的位置。6.4树和树系-树存储，34，示例1:双亲标记，双亲标记，缺点：查找节点孩子时必须通过整个结构，A -1，B 0，C 0，D 1，E 1，F 4，G 4，H 0 1 2 3 4 5 6 7，6.4树和森林，-存储树，36，标记有双亲的孩子，parentdata，a b c d e f g h，-1

12、 0 1 4，d d d e f g h，-6.4树和森林，-存储树，37，孩子兄弟表达，6.4树和树林，-树存储，38，2，森林和二叉树切换，过渡阶段：节点的第一个孩子是左边的孩子节点的右边相邻的兄弟是右边的孩子，A，二叉树，1，树和二叉树的切换，6.4树和树林转换阶段：每棵树应先转换为二叉树，依次连接到以前二叉树的右侧子树，A，E，G，6.4树和林-林和二叉树的转换，41，3，遍历树和林，1，遍历树，第一次遍历，第一次遍历子树没有左右，所以树没有中间遍历。6.4树和林-树遍历，42，2，森林遍历，中间顺序遍历，第一棵树的根节点第一棵树的根节点第一棵树的根节点依次遍历第一棵树的根节点子树林，

13、依次遍历第一棵树后剩下的树组成的森林，访问中间顺序树林树林第一棵树的根节点，访问中间顺序遍历第一棵树后剩下的树a、b、c、d、e、f、g、h、I、j、b、c、d、a、f、e、h、j、I、g、6.4树和树系路径长度：路径中的分支数。树的路径长度：从根到每个节点的路径长度总和。权重路径长度：节点到根的路径长度乘以节点的权重。树的权重路径长度：树中所有叶节点的权重路径长度总和。霍夫曼树：路径最短的树。6.6 hurfman树及其应用，44，例如，三个二叉树中的四个叶节点a、b、c和d分别具有权重7、5、2和4，相应的权重路径长度是？ wpl=7 * 2 5 * 2 * 2 4 * 2=36， wpl=7 * 3 5 * 3 2 * 1 4 * 2=46， wpl=7 * 1 5 * 2.，n，构成n树的n树集F=T1，T2，Tn，其中n. 2)在f中，通过选择两个根节点权重最小的树