06 - Data Structure(4) - BW(东北大学计算机软件基础).ppt

1计算机软件技术基础第 6 讲 2014 年 3 月 2 3. 数据结构 树与二叉树?树(tree ): 一种非线性的数据结构–家谱–组织机构–操作系统中的文件目录结构–程序的调用关系?树的定义–是由 n≥0个结点组成的有限集合 T–有且仅有一个结点称为根( root ) –其余( n-1 )结点构成 m个互不相交的集合 T 1, …,Tm –每个集合 Ti 又构成一颗树,称为“当前根”的子树–树的定义是一个递归定义 3 3. 数据结构 树与二叉树?树的基本概念–结点( node) :树中的元素由两部分组成: ?数据域?若干指向其子树分支的指针域–结点的度( node ’ s degree) :结点拥有的子树的个数–树的度( tree ’ s degree) :树中结点度数的最大值–叶子( leaf) :度为 0 的结点–分支结点( branch node) :度≠ 0 的结点–孩子( childern) :除 root 外,每个结点都是其前趋结点的孩子–双亲( parents) :孩子结点的上层结点–兄弟( slbling) :同一双亲的孩子–结点的层次( level) :根为第一层,其它任何结点的层次是其双亲结点的层次+ 1 –树的深度/高度(depth) :树中结点的最大层次数–森林( forest) :m棵互不相交的树的集合(m≥ 0) –有序树:兄弟结点间有先后次序的树,不能互换;否则,称为无序树 4 3. 数据结构 树与二叉树?树的存储–可有多种存储结构–只讨论最常用的链式存储方式?树的链式存储–树是多分支的非线性表–需采用多重链表结构,即:每个结点除了包含结点的数据外,还包含有多个指针域,每一个指针域指向其孩子结点(一棵子树的根结点) 5 3. 数据结构 树与二叉树?树的链式存储–同构存储(定长结点) ?所有结点的指针域的数目都一样,都等于树的度?所有结点的长度一致?运算方便,浪费空间(树的度越大浪费越严重→二叉树浪费最小) –异构存储(不定长结点) ?结点的指针域个数取决于有几个孩子,有几个孩子就有几个指针域?结点的长度有所不同?节省空间,运算复杂–为了使用同构存储方式,可以把树转化为二叉树,这样运算简单,而且节省存储空间 6 3. 数据结构 树与二叉树?二叉树–是每个结点最多有两个子树的有序树–两个子树分别称为: 左子树、右子树?二叉树的存储–采用具有 2 个指针的链式存储方式–每个结点由数据域和 2个指针域构成?一个指针域指向其左孩子?另一个指针域指向其右孩子 L child Data R child 7 3. 数据结构 树与二叉树?二叉树的性质?二叉树的第 i 层上至多有 2 i - 1 (i≥ 1)个结点?深度为 h 的二叉树中至多含有 2 h– 1 个结点?在任意二叉树中,若有 n 0个叶子结点, n 2个度为 2 的结点,则必有: n 0=n 2 + 1 请见 P54 自学 8 3. 数据结构 树与二叉树?几种特殊形式的二叉树–满二叉树:深度为 h 且含有 2 h– 1 个结点的二叉树?非叶子结点都有 2 个孩子结点?结点编号:由上至下、从左到右 9 3. 数据结构 树与二叉树?几种特殊形式的二叉树–完全二叉树:编号与满二叉树的编号一致?但不要求“非叶子结点都有 2 个孩子结点”?一个结点没有左孩子,就不能有右孩子完全二叉树非完全二叉树 10 3. 数据结构 树与二叉树?几种特殊形式的二叉树–平衡二叉树: ?所有结点的左子树和右子树的深度之差的绝对值≤1 ?平衡因子:一个结点的左子树深度-(减去) 其右子树深度的差?所有结点的平衡因子只可能是– 1, 0, 1