计算机软件基础非线性数据结构讲解

1、®教学目标 了解树、二叉树：-基本概念-逻辑结构- 存储结构及实现- 遍历算法- 特殊二叉树的表示及性质教学要求通过本单元的学习，了解、掌握: 树、二叉树的基本概念 树、二叉树的存储结构及实现 二叉树的遍历操作及有关算法 特殊二叉树的表示及性质 树、森林、二叉树的转换本单元涉及的内容第3页2.1 、树的逻辑结构及其运算2.2 、二叉树2.3 树类2.4 森林与二叉树的转换(P57P73)了才攵2/华一、树型结构及其基本概念树形结构基本概念包括的内容：-树的定义-树的基本概念 结点、根、叶、路径、结点度、 树的度 结点的层次、子结点、父结点 有序、无序第5页树形结构田 a/# q树形结

2、构是以分支关系 来定义的层次结构。在 客观世界中树形结构广 泛存在，并应用于：- 人类社会的族谱、 家谱、行政区域划 分管理；- 各种社会组织机构;-在计算机领域中， 用树表示源程序的 语法结构；- 在OS中，文件系统、 目录等组织结构也 是用树来表示的®树的定义 （逻辑结构）田2丈半 树是一种数据结构:Tree= （D, R）其中：D是具有相同特性的数据元素的集合；R是D上逻辑关系的集合，且满足：-D中其余数据元素都有且只有一个前趋;-在D中存在唯一的称为根的数据元素，没 有前趋；-D中所有元素，或有若干个互不相同的后 继（子树），或无后继（叶结点）；则称Tree为树。树的定义 （

3、递归结构）树是一个或多个结点组成的有限集合 T,有一个特定结点称为根，其余结 点分为m （m>0）个互不相交的集合 Tl, T2,每个集合又是一棵树，被称为这个根的子树。树是一种递归结构，可以包含一个结 点，该结点包含不相交的树的指针 （即子树）。房”2人多树结构举例书目录目录树树结构S2. 1 si. 1 si.2S2.11S2.12S2. 2S2. 1. 1 S2. 1. 2S2. 3C3树的表示形式(4)一般形式 嵌套形式入形式广义表形式树的表示(一般形式)AnL(b)(a)只有根结点的树(b)一般的树第11页树的表示(嵌套形式)寰 树的表示（凹入形式）树的表示（广义表形式）第13

4、页第一层第二层八(A ( B ( E (K, L),F),C(G),D( H (M),I, J ) k, /第四层第三层®基本术语. a/# 2 结点、结点度、根、支、叶结点子结点、父结点、兄弟结点 树的度、路径、长度、高度、深度 森林、有序、无序第15页结点(Node)结点包括一个数据元素及若干个指向其它子 树的分支；例如，A, B, C, D等。结点度 根结点支结点 等。叶结点树的度结点拥有的子树数；例如，A的度为3。无前趋结点为根；例如，A结点。度不为。的结点为支结点；如B, C, D无后继结点为叶；如K, L, Mo树中结点的最大度数；上述树的度为3。.$才支丈*基本术语（二

5、） 子结点某结点子树的根为该结点的子结点； 例如，结点A的子结点为B, C, Do 父结点相对于某结点子树的根，称该结点为 子树根的父结点；例如子结点C, B, D的父结 点为A。 兄弟结点同一父亲的孩子之间互为兄弟结点 （Sibling） ； H, I, J互为兄弟。 路径 结点的序列nl, n2,nk（Ql）是一条 路径. 长度长度等于路径中结点数-1.第17页基本术语（三）高度从一结点到叶结点的最长路径为该结点的高度；例如，结点A到M的高度为4。深度从根结点到某结点的路径为该结点的 深度；M的深度为4。森林0棵或多棵互不相交的树的集合。对 树中每个结点而言，其子树的集合即为森林。有序 如

6、果将树中结点的各子树看成从左至 右是有顺序的（即不能互换），则称该树为 有序树。否则，称为无序树。®树的操作了才攵义/小q PARENT (n, T)得到树中n的父亲结点； ROOT ( T) 求树的根，返回树根的位置。 CHILD (T, x, i)求树T中结点x的第i个孩子 结点。 CREATE (x, Tl, T2, .,Tk)生成一个结点x, 下带子树T1,T2,Tk。 DELETE(x, i)删除结点x的第i个子树。 TRAVERSE (T)遍历树T。按次序依此访问树 中各个结点，且使每个结点只能被访问一次。第19页二、二叉树结构二叉树是另一类重要的非线性结构。- 二叉树的

7、定义- 二叉树的性质- 二叉树的存储结构- 特殊二叉树- 二叉树的遍历操作- 表达式树及应用- 树、森林与二叉树的转换®1、二叉树的定义二二叉树是另一种树形结构：Binary_Tree =（ D, R）其中：D是具有相同性质的数据元素的集合；R是在D上某个两元关系的集合，且满足:D中存在唯一称为根的数据元素,没有前趋;- D中其余元素都有且仅有一个前趋；- 每个结点至多只有两个子树；- D中元素,或有两个互不相交后继,或无后继;- 左、右子树分别又是一棵二叉树。第21页5才支义/学二叉树定义（二）定义r n个结点的集合（nNO）T的度 2所有子树都有左、右之分I （次序不能任意到）&

8、#174;二叉树的五种基本形态田。华 二（a） Q空结点 （d）左子树为空"的二叉树（b） °单个结点（e）?右子树为空/的二叉树A左、右子树 非空的二叉 树第23页二叉树与树的区别表达形式（对3个结点）普通树有两种不同形式二叉树(b)有五种不同形式®二叉树与树的区别（二）丈小 Q观念-二叉树是一种特定的树结构，但 不是普通树的特殊情况；-二叉树可以为空；而树则不能为 空；-二叉树的结点的子树分左子树和 右子树，而树则无此区分。第25页2、二叉树的性质“丈 a "，性质一二叉树的第i层上至多有22个结点（i N 1）。利用归纳法证明：- i=l时，只有一

9、个结点，对的；- 假设对所有的j, IV j V i,命题成立， 即在第j层上，至多有2"个结点。- 由归纳假设，第i-1层上至多有20个结点。JJ2由于二叉树的每个结点的度至多为2,故第i层上的最大结点数为第i-1层上的最大 结点数的2倍，即2X2i-2 = 2Mo二叉树的性质（二）性质二深度为k的二叉树上最多含有2、-1个结点(k > 1) o由性质一可见，深度为k的二叉树的最大结点数为:Z （第i层上的最大结点数）i=lL 2i-1i=l第27页验证二叉树的性质该二叉树的第3层有个结点.该二叉树深度为4,最多有24 -1个结点.3、二叉树的存储结构 顺序存储（一维数组）

10、记录数组结构 链式存储结构-二叉链表-三叉链表第29页顺序存储（一维数组） 用数组存放存储描述为：ftdefine MAXSIZE 100；typedef TElemType SBTreeMAXSIZE；SBTree bt； 查找不便。al a2 a3 a4 an田2/华记录数组结构存储结构描述：ftdefine MAXSIZE 100;typedef struct SBNode TElemType data ; int LehiId,Rchild; SBNode;typedef struct (SBNode nodesMAXSIZE;第31页 SBTree;记录数组结构举例田g"

11、二特点：找子方便，找父 结点不便二叉链表存储结构找子易，找父难.第33页三叉链表存储结构田a/#找子、找父都易。田2"4、特殊二叉树满二叉树完全二叉树平衡二叉树二叉排序树若k为二叉树T的深度，且T中共有2仁1个 结点（k之1）,则称T为满二叉树。（a）满二叉树 （b）非满二叉树满二叉树的性质若对满二叉树从第1层开始，自上而下、从左至右 给每个结点从1开始编号的话，则称深度为k的满 二叉树的结点编号满足：-对某结点i （1< i < 2k 1 -1）,其左子树的编号为2*i （偶数），其右子树的编号为2* i +1 （奇数）；（非叶结点）-若i>l,则结点i父结点的编

12、号为i/2 （整除）o根据这一性质，可用一维数组存储满二叉数的结 点数据。知道一个结点的编号，经计算就能求出 左、右子树的根及父结点的编号。第37页满二叉树存储举例 第i个结点就存放在第i个位置上； 第i个结点（i>l）的父结点就存放在第i/2个位置； 第i个结点（达2门1）的左子结点就存放 在第2*i的个位置;右子存放在第2*i+l位置.完全二叉树深度为k的二叉树T,每层结点数目若满足：-第i层(1 4 i 4 k-1)上的结点个数均为(非 叶结点)；-第k层从右边连续缺若干个结点(即只能从右 至左不间断缺少)；称这样的树为完全二叉树。 (a)完全二叉树(b)非完全二叉树特点：叶结点只

13、可能出现在层次最大的两层上./孑攵2/字完全二叉树的性质第39页设完全二叉树的结点总数为n,深度为k,某结点 编号为i (1 <i 4 n ),则有：- 若i>l,则结点i的双亲结点的编号为i /2;- 若2* i 4 n,则结点i的左子结点的编号为2* i,否则，结点i为叶结点；- 若2* i +14 n,则结点i的右子结点的编号为 2*i+l,否则，结点i为叶结点.同理,完全二叉树也可以采用一维树组作为存储 k结构,且方法完全同满二叉树,只不过n <2-1罢了.平衡二叉树二叉树上任一结点的左子树深度减去右子 树深度的差值，称为该结点的平衡因子。任意结点左、右子树的深度之差

14、的绝对值<1 ,这样的树称为平衡二叉树. （a）平衡二叉树（b）非平衡二叉树第41页二叉排序树定义（一）二叉排序树-或者是空二叉树;-或者是：左子树上所有结点的值均小于 根结点的值；右子树上所有结点的值均大于 等于根结点的值；-左、右子树本身又是一棵二叉排 序树。二叉排序树定义(二)加，夫华 /X是二叉排序树T中的一个结点；-所有的左后裔小于X；-所有的右后裔大于等于X；-T可以为空树； T称为二叉排序树。(a)二叉排序树(b)非二叉排序树5K中5、二叉树的遍历历(Traversing)是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。遍历的方法很多，常用的有:-前序法(PreOrder) -中序法(InOrder)-后序法(PostOrder)前序法(PreOrder)方法描述：-从根结点a开始访问,-接着访问左子结点b,-最后访问右子结点c。即：左子一右子第45页中序法（InOrder）方法描述：-从左子结点b开始访问,-接着访问根结点a, -最后访问右子结点C。即