[计算机软件及应用]数据结构课件

《[计算机软件及应用]数据结构课件》由会员分享，可在线阅读，更多相关《[计算机软件及应用]数据结构课件（173页珍藏版）》请在金锄头文库上搜索。

1、第6章树和二叉树第6章树和二叉树非线性结构，一个直接前驱，但可能有多个直接后继（1:n）6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.6 赫夫曼树及其应用6.1 树的定义和基本术语r 2.若干术语3.逻辑结构4,存储结构5.树的运算1,树的定斗片 百 Z r e e)是n 个(n )结点组成的有限集合T。在任何一棵非空树中：1(1)有且仅有一个结点称为根(r o o t);(2)当n l时，其余的结点可分为m(m 0)个的 有 限 集 合，Tmo其中，每个集合本身又是一棵树，被称作这个根的 子 树(S u bT r e e)。注1:过去许多书籍中都定

2、义树为n N L 曾 经 有“空树不是树”的说法，但现在树的定义已修改。注2:树的定义具有，即树的定义中还有树。只有根结点的树有子树的树D是具有相同特性的数据元素的集合。若D为空集，则称为空树；允许n=0若D中仅含一个数据元素，则R为空集;否则R=H,H是如下二元关系：在D中存在唯一根元素ro o t,在H下无前驱若D.root*,贝|存在对D.root的一个划分，对任意j r k,有DiADk=,且v H.J 对应于D-root的划分，有唯一一个划分，对任意j r k,有HjnHk=O。(DjJHj)至少有15个Root(T)/求树的根结点Value(T,cur e)求当前结点的元素值Par

3、ent(T,cur_e)求当前结点的双亲结点LeftChild(T,cur_e)1 1求当前结点的最左孩子RightSibling(T,cur_e)求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树TreeDepth(T)求树的深度TraverseTree(T,Visit()/遍历 卜 七 浦育Iniree(&T)初始化置空树CreateTree(&T5 definition)/按定义构造树Assign(T5 cur_e,value)给当前结点赋值InsertChild(&T5&p,i,c)/将以c为根的树插入为结点p的第i棵子树ClearTree(&T)1 1 将树清空Destro

4、yTree(&T)销毁树的结构DeleteChild(&T,&p,i)删除结点p的第i棵子树丁 西 表 示 羊 嵌套集合表示法 广义表表示法这些表示法的示意图 凹入表示法 左孩子-右兄弟表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)由子树森林组成的(K,L),F),C(G),D朝百兄弟表示法;(B(EK(H(M),l,J)若干术语 吃 艮 结 点（没有前驱）即终端结点（没有后继）指m棵不相交的树的集合（例如删除A后的子树个数）结点各子树从左至右有序，不 能 互 换（左为第一）结点各子树可互换位置。即上层的那个结点（直接前驱）即下层结点的子树的根（直接后继）同一双亲下的同层

5、结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点2.若干术语（续）即树的数据元素及其分支结百、挂接的子树数（有 几Ci个直接后继就是几度。）从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）所有结点度中的最大值（Max 各结点的度）指所有结点中最大的层数（Max 各结点的层次）问：右上图中的结点数=1 3;树的度=3;树的深度=4，结点A的度：3结点B的度：2，点M的度：0结点A的孩子：B,C,D结点B的孩子：E,F叶子：K,L,F,G,M,I,J树的度:结点I的双亲：D结点A

6、的层次:结点M的层次:14结点F,G为堂兄弟结点A是结点F,G的祖先3:树希夏藏构c l L,cl 1：7：一对多（l:n）,有多个直接后继（如家谱_ _ 树 目录树等等），但只有一个根结点，且r 子树之间互不相交。4.树的存储结构讨论1:树是非线性结构，该怎样存储？-仍然有顺序存储、链式存储等方式。一：树的顺序存储方案应该怎样制定？,K I寻树的结点依次存入内存o/复原困难（不能唯一复原就没有实用价值）。树的链式存储方案应该怎样制定？一个前驱指针，个后继指针。树中结点的结构类型样式该如何设计？即应该设计成？等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。5

7、.树 的 运 算1.普 通 树（即多叉树）若不转化为二叉树，则运算很难实现。2.二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在的基础上！（指每个结点都被访问且仅访问一次，不遗漏不重复）。7：线性结构第厂个数据元素（无前驱）最后一个数据元素（无后继）其它数据元素（一个前驱、一个后继）零=三三三三三三树型结构根 结 点（无前驱）多个叶子结点（无后继）其它数据元素（一个前驱、多个后继）6.2二叉树为何要重点研究每结点最多只有两个“叉”的树？/二文树的结构最简单,规律性最强；,可 以 证 明，所有树都能转换为唯一的一棵二叉树与其对应,不失一1般性。6.2.1二 叉树的定义6.2

8、.2二 叉树的性质6.2.3 二叉树的存储结构定 义 是n （）个结点的有限集合，由一个也结点以及两棵互不相交的、分别称为的二叉树组成。逻辑结构：一 对 二（L 2）基本特征：每个结点最多可有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒（有序树后空 树篇&砌 的五种基本形态:只 含 根 结 点左 右 子树 均 不为 空 树右 子 树 为 空 树左 子 树 为 空 树二叉树的抽象数据类型定义ADT BinaryTree 二 D是具有相同特性的数据元素的集合。若=，则R=0;若D#，则区=11;存在二元关系：root唯一DDr=0 基本操作P:至少有：ADT BinaryTree关

9、于根的说明关于子树不相交的说明关于二元关系的说明二叉树的主要基本操作:查 找 类产 插 入 类产 删 除 类QEllRoot(T);Value(T,e);Parent(T5 e);LeftCMd(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrder Traversed Visit();InOrderTraverse(T5 Visit();PostOrderTraverse(T5 Visit();LevelOrderTraverse(T,V isitQ);己In

10、itBiTree(&T);Assign(T5&e,value);CreateBiTree(&T5 definition);InsertChild(T5 p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);讨论k第；层的结点数至多是多少？L （利用二叉树的特性可轻松求出）_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _在二叉树的第i层上至多有2 1个结点（i 0）。提问：第i层上至少有 1个结点?讨论

11、2：深度为k的二叉树，至多有多少个结点？L（利用二叉树的特性可轻松求出）深度为k的二叉树至多有2k-l个结点（k 0）。提问：深度为k时 至 少 有k 个结点?数 和 度iE lL二一对于任何一棵二叉树，若2度的结点数有1个，则 叶 子 数（n0）必定为由+1 （00=1 12+1）证明：二叉树中全部结点数=o+/+2（叶子数+1度结点数+2度结点数）二叉树中全部结点数胃=B+1（总分支数十根 结 点）（除根结点外，每个结点必有且仅有一个直接前趋，即一个分支进入）总分支数5=%+22（1度结点必有1个直接后继，2度结点必有2个）+勺+2=n1+2 n2+1,即 n0=n2+1叶子数=2度结点数

12、+1层可下杲度为k且有2卜-1个结点的二叉树。/Z a t型 及、：每 层 都“充满”了结点）7 二采度为A的，有个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至的结点一一对应。深度为4的满二叉树这其实是顺序二叉树的含义。在图论概念 中 的“完全二叉树”是指%=0的情况。为何要研究这两种特殊形式？因为它们/顺序存储方式下可以复原！深度为4的完全二叉树复习讨论/二叉树是不是树的特殊情况？答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树驮结构，舁非一般树的持面L它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。：满二叉树和完全二叉树有什么区别？答：满二叉树

13、是每一层都是满的二叉树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。课堂练习：A）高度 B）层次C）深度 吵 度A)2 9B)首C)9 性 质4:I有 个结点的完全二叉树的深度为 L log2nj+l证明：设完全二叉树的深度为k则根据第二条性质得2左右n 2k即 k-1 log2n ，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若 2计7 小 则该结点无右孩子结点，否则，编号为2计7 的结点为其右孩子结点。TJTJTJTJTJ123456789rLrLrLrLrLrLrLrLrL6.2.3二叉树的存储结构一、顺序存

14、储结构问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2 i,其右孩子的下标值必为2i+l（即性质5）例如，对应的两个孩子必为 4和 5,即B的左孩子必是D,右孩子必为E。二叉树的顺序存储表示#deHne MAX_TREE_SIZE 100typedef TElemTypeSqBiTreeMAX_TREE_SIZE;SqBiTree bt;占N吉虚”，其内容为空。讨论：不是完全二叉树怎么办？答：一律转为完全二叉树！方法缎简单，将各层空缺处统统补上1 2 3 4 5 6 7 8 9缺点：浪费空间；插入、删除

15、不便1610 1 2 3 4 5 6 7 8 9 10 11 12 13A B DCEF式存储结构4用二叉链表即可方便表示。一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。1、二叉链表2、三叉链袤3、线索链表A结点结构:Ichild data rchild讨卷n个结点二叉树的二叉链表有多少空链域?2*n-(n-1)=n+12*no+ni=n0+n1+n2+l=n+1/C语言的类型描述如下：typedef struct BiTNode 结点结构TElemType data;struct Bi

16、TNode*lchild,*rchild;I 左右孩子指针 BiTNode,*BiTree;结点结构：Ichild data rchild三叉链表结点结构:AA BA C AAparent Ichild data rchildADC1E AA F AA DC语言的类型描述如下：f-typedef struct TriTNode 结点结构TElemType data;struct TriTNode*lchild,*rchild;/左右孩子指针struct TriTNode*parent;双亲指针 TriTNode,*TriTree;Ichilddatarchild6.3遍历二叉树和线索二叉树指按某条搜索路线遍访每个结点且不重复（又称周游）。它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。牢记一种约定，对每个结点的查看都 是“”。二叉树由根、左子树、右子树构成，定义为D、L、R3D、L、R的组合定义了六种可能的遍历方案：DLRJDR,LRD,DRL,RDL,RLD:若限定先左后右,则有三种实现方案:DLRLDRLRD先（根）序遍历中（根）序遍历 后（根）序遍