《数据结构与算法分析PPT课件》由会员分享，可在线阅读，更多相关《数据结构与算法分析PPT课件（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法分析沈阳建筑大学沈阳建筑大学 赵明赵明第六章第六章 树和二叉树树和二叉树知识点一知识点一 树的定义和基本术语树的定义和基本术语知识点二知识点二 二叉树二叉树知识点三知识点三 遍历二叉树遍历二叉树知识点四知识点四 线索二叉树线索二叉树知识点五知识点五 树和森林树和森林知识点六知识点六 赫弗曼树及其应用赫弗曼树及其应用知识点一知识点一 树的定义和基本术语树的定义和基本术语内容简介内容简介： 1 1、现实世界中，树型关系的实例、现实世界中，树型关系的实例族谱族谱 2 2、树的定义和特点、树的定义和特点基于例子基于例子 3 3、树的抽象数据类型定义、树的抽象数据类型定义 4 4、树的基本
2、术语、树的基本术语 5 5、小结：树型结构与线性结构的对比、小结：树型结构与线性结构的对比树树是一类重要是一类重要的的非线性数据非线性数据结构结构，是以，是以分分支关系支关系定义的定义的层次结构层次结构 你见过家族谱系图吗？以图形表示从你的祖父起的家族成员关系。你见过家族谱系图吗？以图形表示从你的祖父起的家族成员关系。上列家族谱系图可用如下关系（有序对）表示：上列家族谱系图可用如下关系（有序对）表示： ， ， ， ， ， ， ， 树的定义和基本术语树的定义和基本术语实例导入实例导入 祖父祖父 伯父伯父 父亲父亲 叔父叔父堂兄堂兄 堂姐堂姐 你你 堂弟堂弟侄儿侄儿树树(tree)(tree)是是
3、n n(n=0)(n=0)个结点的个结点的有限集有限集T T，在任意的在任意的非空树非空树中中n有且仅有有且仅有一个特定的结点，称为树的一个特定的结点，称为树的根根(root)(root)n当当n n11时，其余结点可分为时，其余结点可分为m(m0)m(m0)个个互不相交互不相交的的有限集有限集T1,T2,TmT1,T2,Tm，其中每一个集合本身又是一棵树，称为根的其中每一个集合本身又是一棵树，称为根的子子树树( (subtreesubtree) )特点特点：n树中最多只有树中最多只有一个根结点一个根结点n树中各树中各子树子树是是互不相交互不相交的集合的集合树的定义和基本术语树的定义和基本术语
4、树的定义及特点树的定义及特点A只有根结点的树只有根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树树的定义和基本术语树的定义和基本术语树的定义及特点树的定义及特点ADT Tree 数据对象数据对象：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系：若若 D 为为空集空集，则称为，则称为空树空树；若若 D 中仅含中仅含一个数据元素一个数据元素，则关系，则关系R为空集为空集；否则否则 R=H， (1) 在在D中存在中存在唯一唯一的称为的称为根根的数据元素的数据元素 root，它在关系它在关系H下下无前驱无前驱； (2) 当当n1时，其余数据元素可
5、分为时，其余数据元素可分为 m(m0) 个个互不相交的互不相交的(非空非空)有限集有限集 T1,T2,Tm, 其中每一个子集本身又是一棵符合其中每一个子集本身又是一棵符合本定义的树，称为本定义的树，称为根根 root 的子树的子树，每一棵子树的根，每一棵子树的根 xi 都是都是根根 root 的后继，即的后继，即 H,i=1,2,m。树的定义和基本术语树的定义和基本术语树抽象数据类型定义树抽象数据类型定义基本操作基本操作：InitTree(&T); 操作结果操作结果：构造空树：构造空树 T。CreateTree(&T,definition);初始条件初始条件：definition 给出树给出树
6、T的定义。的定义。操作结果操作结果：按：按 definition 构造树构造树 T。DestroyTree(&T);初始条件初始条件：树：树 T 存在。存在。操作结果操作结果：销毁树：销毁树 T。TreeEmpty(T);初始条件初始条件：树：树 T 存在。存在。操作结果操作结果：若：若 T 为空树，则返回为空树，则返回 TRUE，否则返回否则返回 FALSE。TreeDepth(T);初始条件初始条件：树：树T存在。存在。操作结果操作结果：返回：返回T的深度。的深度。树的定义和基本术语树的定义和基本术语树抽象数据类型定义树抽象数据类型定义Root(T); 初始条件初始条件：树：树 T 存在。
7、存在。 操作结果操作结果：返回：返回 T 的根的根Value(T, cur_e); 初始条件初始条件：树：树 T 存在，存在，cur_e 是是 T 中某个结点。中某个结点。 操作结果操作结果：返回：返回 cur_e 的值。的值。Parent(T, cur_e); 初始条件初始条件：树：树 T 存在，存在，cur_e 是是 T 中某个结点。中某个结点。 操作结果操作结果：若：若 cur_e 是是T的非根结点，则返回它的双亲，否则返回的非根结点，则返回它的双亲，否则返回“空空”。LeftChild(T, cur_e); 初始条件初始条件：树：树 T 存在，存在，cur_e 是是 T 中某个结点。中
8、某个结点。 操作结果操作结果：若：若 cur_e 是是T的非叶子结点，则返回它的最左孩子，否则的非叶子结点，则返回它的最左孩子，否则返回返回“空空”。树的定义和基本术语树的定义和基本术语树抽象数据类型定义树抽象数据类型定义RightSibling(T, cur_e); 初始条件初始条件：树：树 T 存在，存在，cur_e 是是 T 中某个结点。中某个结点。 操作结果操作结果：若：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回有右兄弟，则返回它的右兄弟，否则返回“空空”。TraverseTree(T, visit();初始条件初始条件：树：树T存在，存在，visit 是对结点操作的应用函数
9、。是对结点操作的应用函数。操作结果操作结果：按某种次序对：按某种次序对 T 的每个结点调用函数的每个结点调用函数 visit() 一次且至多一次且至多一次。一旦一次。一旦 visit() 失败，则操作失败。失败，则操作失败。Assign(T, cur_e, value); 初始条件初始条件：树：树T存在，存在，cur_e 是是 T 中某个结点。中某个结点。 操作结果操作结果：结点：结点 cur_e 赋值为赋值为 value。ClearTree(&T); 初始条件初始条件：树：树 T 存在。存在。 操作结果操作结果：将树：将树 T 清为空树。清为空树。树的定义和基本术语树的定义和基本术语树抽象数
10、据类型定义树抽象数据类型定义 InsertChild(&T, &p, i, c); 初始条件初始条件：树：树 T 存在，存在，p 指向指向T中某个结点，中某个结点，1ip 所指结点所指结点的度的度1，非空树，非空树 c 与与 T 不相交。不相交。 操作结果操作结果：插入：插入 c 为为 T 中中 p 所指结点的第所指结点的第 i 棵子树。棵子树。DeleteChild(&T, &p, i); 初始条件初始条件：树：树 T 存在，存在，p 指向指向 T 中某个结点，中某个结点，1ip 指结点指结点的度。的度。 操作结果操作结果：删除：删除 T 中中 p 所指结点的第所指结点的第 i 棵子树。棵子
11、树。 ADT Tree树的定义和基本术语树的定义和基本术语树抽象数据类型定义树抽象数据类型定义n结点结点(node)(node)：表示树中的元素，包括数据项及若干指向其子树的分支表示树中的元素，包括数据项及若干指向其子树的分支n结点的度结点的度(degree)(degree)：结点拥有的子树数结点拥有的子树数n叶子叶子(leaf)(leaf)：度为度为0 0的结点的结点n孩子孩子(child)(child)：结点子树的根称为该结点的孩子结点子树的根称为该结点的孩子n双亲双亲(parents)(parents)：是指孩子结点的上层结点是指孩子结点的上层结点n兄弟兄弟(sibling)(sibli
12、ng)：同一双亲的孩子同一双亲的孩子n树的度树的度：一棵树中最大的结点度数：一棵树中最大的结点度数n结点的层次结点的层次(level)(level)：从根结点算起，根为第一层，它的孩子为第二从根结点算起，根为第一层，它的孩子为第二层层n有序树有序树：树中结点的各子树看成从左至右是有次序的（即不能互换）；：树中结点的各子树看成从左至右是有次序的（即不能互换）；否则称否则称无序树无序树 n深度深度(depth)(depth)：树中结点的最大层次数树中结点的最大层次数n森林森林(forest)(forest)：m(mm(m 0)0)棵互不相交的树的集合棵互不相交的树的集合树的定义和基本术语树的定义和
13、基本术语基本术语基本术语ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先树的定义和基本术语树的定义和基本术语树抽象数据类型定义树抽象数据类型定义树型和线性结构的对比树
14、型和线性结构的对比 可见，由于可见，由于线性结构是一个线性结构是一个“序列序列”，元素之间存在的是，元素之间存在的是“一对一对一一”的关系，而的关系，而树是一个层次结构树是一个层次结构，元素之间存在的是，元素之间存在的是“一对多一对多的的关系。关系。线性结构线性结构树型结构树型结构存在存在唯一唯一的没有前驱的的没有前驱的 首首元元素素 存在存在唯一唯一的没有前驱的的没有前驱的 根根结点结点 存在唯一的没有后继的存在唯一的没有后继的 尾尾元元素素 存在多个没有后继的存在多个没有后继的 叶子叶子 其余元素其余元素均存在均存在唯一唯一的的 前驱前驱元素元素 和和唯一唯一的的 后继后继元素元素 其余结点其余结点均存在均存在唯一唯一的的 前驱前驱双双亲亲) )结点结点 和和多个多个 后继后继( (孩子孩子) )结结点点 树的定义和基本术语树的定义和基本术语小结小结
