《EF结点I的双亲.ppt》由会员分享，可在线阅读，更多相关《EF结点I的双亲.ppt（135页珍藏版）》请在金锄头文库上搜索。
1、6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 Huffman树及其应用,第六章 树与二叉树,树形结构是一种非线性结构，应用十分广泛。 如：行政机构、家谱、磁盘目录等,磁盘目录,根-根结点 分枝-分枝结点 叶-叶结点,6.1 树（Tree）的定义和基本术语,树的定义：树是n（n=0）结点的有限集，任意非空树： (1) 有且仅有一个特定的结点称为根（Root）的结点 (2) 当n1时，其余的结点可分为m个互不相交的子集 T1, T2, , Tm, 每个子集又都是树，称为根的子树（Sub tree）.,6.1 树（Tree）的定义和基本术语,树
2、的定义具有递归性,树是一种层次结构 （hiberarchy）,1,2,3,4,5,6.1 树（Tree）的定义和基本术语,Tree=(D, R) D=Book, C1, C2, C2, S1.1, S1.2, S2.1, S2,2, S2.3, S2.1.1, S2.1.2 R=, , , , , , , , , ,Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2,Chapter,Section,Section,例6.1,6.1 树（Tree）的定义和基本术语,术语主要来源于家谱和树： 双亲、子女（Parent, Child）：若a,b
3、R，则称a是b的 双亲，b是a 的子女(孩子). 结点度（Degree）：结点的子女数； 树的度：最大的结点度； 层（Level）：根在第1层，其它任一结点所在的层是其双亲的 层加1； 叶（Leaf）：度为0的结点； 分枝结点（Branch node）：度大于0的结点； 兄弟（Sibling)：具有同一双亲的结点互称兄弟；,6.1 树（Tree）的定义和基本术语,堂兄弟（Cousin）：在同层的非兄弟结点互称堂兄弟； 深度（Depth）：最大层数；或称为高； 路径（Path）：如果有结点序列n1,n2,n3,nk，并且前1个结 点是后1个结点的双亲；它的长度是k-1; 祖先、后代（ancest
4、or）：一个结点是它所有子树中的结点 的祖先，这些结点是它的后代； 有序树（Ordered tree）：每个结点的子女由左到右是有次 序的；否则是无序树；,6.1 树（Tree）的定义和基本术语,结点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的祖先,T1,T2,T3,T4,T5,T6,6.1 树（Tree）的定义和基本术语,森林（Fore
5、st）：是m(m 0)棵互不相交的树的集合,(例如删除树根后的子树构成一个森林),任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点，F 被称为子树森林,抽象数据类型树的定义：,6.1 树（Tree）的定义和基本术语,ADT Tree,数据对象D：D是具有相同特性的数据元素的集合。,数据关系R：若D为空集，则称为空树；,若D仅含一个数据元素，则R为空集，否则R=H，H是如下二元关系：,(1) 在D中存在唯一的称为根的数据元素root，它在关系H下 无前驱；,(2) 若D-root ，则存在D-root的一个划分D1，D2， ，Dm，(m0)，对任意jk(1
6、j,km)有DjDk= , 且对任意的i(1im)，唯一存在数据元素xiDi， 有H；,(3) 对应于D-root的划分，H， 有唯一的一个划分H1,H2，Hm(m0)，对任意jk(1j，km) 有HjHk= ,且对任意i(1im),Hi是Di上的二元关系,(Di,Hi)是一棵符合本定义的树,称为根root的子树.,基本操作: InitTree(&T)； 操作结果：构造空树T。 DestroyTree(&T)； 初始条件：树T存在。 操作结果，销毁树T。,CreateTree(&T，definition)； 初始条件：definition给出树T的定义。 操作结果：按definition构造树
7、T。 ClearTree(&T)； 初始条件；树T存在。 操作结果：将树T清为空树。 TreeEmpty(T)； 初始条件：树T存在。 操作结果：若T为空树，则返回TRUE，否则FALSE。 TreeDepth(T)； 初始条件：树T存在。 操作结果；返回T的深度。,基本操作:,Root(T)； 初始条件：树T存在。 操作结果：返回T的根。 Value(T，cur_e)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。 Assign(T，cur_e，value)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。 Par
8、ent(T，cur_e)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若our_e是T的非根结点，则返回它的双亲，否则函数值为“空”。,基本操作:,LeftChild(T，cur_e)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。 RightSibling(T，cur_e)； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。,基本操作:,InsertChild(&T，&P，i，c)； 初始条件：树T存在,p指向T中某个结点，1i
9、p指结点的度+1，非空树c与T不相交。 操作结果：插入c,成为T中p所指结点的第i棵子树。 DeleteChild(&T，&p，i)； 初始条件：树T存在，p指向T中某个结点，1ip指结点的度 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree(T，Visit()； 初始条件；树T存在，Visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数Visit()一次且至多一次。一旦Visit()朱败，则操作失败。 ADT Tree,基本操作:,树的表示方法： 1. 树形表示：,6.1 树（Tree）的定义和基本术语,2. 括号表示(广义表表示)：,(A(B(E
10、)(C(F)(D(G(H)(I)(J),T1,T3,T2,树根,3. 凹入表表示(目录表示法)：,6.1 树（Tree）的定义和基本术语,4. 文氏图表示(集合表示):,6.1 树（Tree）的定义和基本术语,二叉树是另一种树形结构。 6.2.1 二叉树的定义 二叉树：是n（n=0）结点的有限集，在任意非空树中： (1) 有且仅有一个特定的结点称为根（Root）的元素; (2) 当n1时，其余的结点最多分为2个互不相交的子集 T1, T2, 每个又都是二叉树，分别称为根的左子树和右子树. 注意：二叉树不是树，它是另外单独定义的一种树形结构，并非一般树的特例。它的子树有顺序规定，分为左子树和右子
11、树。不能随意颠倒。,6.2 二叉树（Binary Tree）,例,6.2.1 二叉树的定义,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,1 空,二叉树的5种基本形态：,2 只有根,3 右子树空,4 左子树空,5 左、右子树非空,具有3个结点的二叉树可能有几种不同形态？,抽象数据类型二叉树的定义： ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D= ，则R= ， 称Binary为空二叉树； 若D ，则R=H，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-root ，则存在D
12、-root的一个划分Dl，Dr，且DlDr= ； (3) 若Dl ,则Dl中存在唯一的元素x1, H, 且存在Dl上的关系HlH,若Dr ,则Dr中存在唯一的元素xr, H,且存在Dr上的关系HrH;H=,Hl,Hr (4)(Dl,Hl)是一颗符合本定义的二叉树，称为根的左子树 (Dr,Hr)是一颗符合本定义的二叉树，称为根的右子树,6.2.1 二叉树的定义,二叉树不是有序树,基本操作: InitBiTree( 初始条件：definition给出二叉树T的定义。 操作结果：按definition构造二叉树T. ClearBiTree(&T)； 初始条件：二叉树T存在。 操作结果：将二叉树T清为
13、空树。,BiTreeEmpty(T)； 初始条件：二叉树T存在。 操作结果：若T为空二叉树，则返回TRUE，否则FALSE. BiTreeDepth(T)； 初始条件：二叉树T存在。 操作结果：返回T的深度。 Root(T)； 初始条件:二叉树T存在。 操作结果：返回T的根。 Value(T，e) 初始条件：二叉树T存在，e是T中某个结点。 操作结果；返回e的值。,Assign(T，&e，value)； 初始条件；二叉树T存在，e是T中某个结点。 操作结果：结点e赋值为value。 Parent(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：若e是T的非根结点，则返回它的双
14、亲，否则返回“空”。 LeftChild(T，e)； 初始条件：二叉树T存在，是T中某个结点。 操作结果：返回e的左孩子。若e无左孩子，则返回“空”。 RightChild(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右孩子。若e无右孩子，则返回“空”。,LeftSibling(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。,Rightsibling(T，e)； 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。 Insert
15、Child(T，p，LR，c)； 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c 与T不相交且右子树为空。,操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。 P所指结点的原有左或右子树则成为c的右子树。,DeleteChild(T，p，LR)； 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。,PreOrderTraverse(T，Visit()； 初始条件：二叉树T存在，Visit()是对结点操作的应用函数。 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。 一旦vis让()失败，则操作失败。,InOrderTraverse(T，Visit()； 初始条件：二叉树T存在，Visit()是对结点操作的应用函数。 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。 一旦Visit()失败，则操作失败。 PostOrderTraverse(T，Visit()； 初始条件：二叉树T存在，Visit()是对结点操作的应用函数。 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦Visit()失败，则操作失败。,LevelOrderTraverse(T，Visit()； 初始条件：二叉树T存在，Visit()是对结
