数据结构第6章树和二叉树.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 树和二叉树,6.1 树的类型定义,6.2 二叉树的类型定义和实现,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.5,Huffman,树与,Huffman,编码,1,对比,树型结构,和,线性结构,的结构特点,第一个数据元素,(,无前驱,),最后一个数据元素,(,无后继,),其它数据元素,(,一个前驱、一个后继,),根结点,(,无前驱,),多个叶子结点,(,无后继,),其它数据元素,(,一个前驱、多个后继,),2,6.1 树的类型定义,树,是,n,(,n,0,),个结点的有限集 D，当,n,1 时：,1）有一个特定的结点,root,被称为,根,(结点),;,2）除根以外的结点被分成,m,(,m,0)个,不相交,的有限集T,1,T,2,T,m,，其中每个集合又是一棵树，称为根的,子树,A,B,C,D,E,F,G,H,I,J,M,K,L,3,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素,+,若干指向子树的,分支,分支的个数,树中所有结点的度的,最大值,度为零的结点,度大于零的结点,D,H,I,J,M,树的基本术语,(从根到结点的),路径：,由从根到该结点所经,分支和结点,构成,4,孩子结点：,结点的,子树的根,称为该结点的孩子,双亲结点：,B 结点是A 结点的孩子，则A结点是B结点的双亲,兄弟结点：,同一双亲的孩子之间互称兄弟,堂兄弟结点：,其双亲在同一层的结点互称堂兄弟,祖先结点：,从根到该结点所经分支上的所有结点,子孙结点：,以某结点为根的子树中任一结点都称为该结点的子孙,5,孩子,结点,双亲,结点,兄弟,结点,堂兄弟,结点,祖先,结点,子孙,结点,结点的层次:,树的深度：,A,B,C,D,E,F,G,H,I,J,M,K,L,假设根结点的层次为1，第L层结点的子树的根结点层次为L+1,树中叶子结点所在的,最大层次,6,有序树：,子树之间存在确定的,次序,关系。

最左边子树的根称为,第一个孩子,；,最右边子树的根称为,最后一个孩子,森林：,是m（m0）棵互不相交的树的集合A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,无序树：,不考虑子树的顺序7,任何一棵非空树是一个二元组,Tree=（root，F）,其中：root 被称为根结点,F 被称为子树森林,森林和树之间的联系：,一棵树去掉根后，其子树构成一个森林；一个森林增加一个根结点成为树8,A,B,C,D,E,F,G,H,I,J,M,K,L,(,A,(,B(E,F(K,L),C(G),D(H,I,J(M),),),T,1,T,3,T,2,树根,广义表,树的表示方法：层次结构；,1）,嵌套集合；,2）,广义表；,3）,凹入表示法,9,ADT Tree,数据对象D：,D是具有,相同特性,的数据元素的集合数据关系R：,若 D 为,空集,，则称为,空树,；若 D 中仅含,一个,数据元素，则关系,R为空集,；否则 R=H，(1)在D中存在唯一的称为根的数据元素,root,，它在关系H下,无前驱,；(2)当n1时，其余数据元素可分为 m(m0)个,互不相交,的(非空)有限集 T,1,T,2,T,m,其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 x,i,都是根 root 的后继，即 H,i=1,2,m。

树的抽象数据类型定义如下：,10,基本操作：,结构初始化,InitTree(,操作结果：,构造空树 TCreateTree(,初始条件：,definition 给出树T的定义操作结果：,按 definition 构造树 T销毁结构,DestroyTree(,初始条件：,树 T 存在操作结果：,销毁树 T11,引用型操作,TreeEmpty(T);,初始条件：,树 T 存在操作结果：,若 T 为空树，则返回 TRUE，否则返回,FALSETreeDepth(T);,初始条件：,树 T 存在操作结果：,返回T的深度Root(T);,初始条件：,树 T 存在操作结果：,返回 T 的根12,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 中某个结点操作结果：,若 cur_e 是T的非叶子结点，则返回它的最左孩子，否则返回空,13,RightSibling(T,cur_e);,初始条件：,树 T 存在，cur_e 是 T 中某个结点,操作结果：,若 cur_e 有右兄弟，则返回它的右兄弟，,否则返回“空”。

TraverseTree(T,visit();,初始条件,：树T存在，visit 是对结点操作的应用函数,操作结果：,按某种次序对 T 的每个结点调用函数visit(),一次且至多一次一旦 visit()失败，则操,作失败加工型操作,Assign(,初始条件,：树T存在，cur_e 是 T 中某个结点操作结果：,结点 cur_e 赋值为 value14,ClearTree(,初始条件：,树 T 存在操作结果：,将树 T 清为空树InsertChild(,初始条件：,树 T 存在，p 指向T中某个结点，1i(p,所指结点的度1),非空树 c 与 T 不相交操作结果：,插入 c 为 T 中 p 所指结点的第 i 棵子树DeleteChild(,初始条件：,树 T 存在，p 指向 T 中某个结点，1ip,指结点的度操作结果：,删除 T 中 p 所指结点的第 i 棵子树ADT Tree,15,定义,或为,空树,，或是由,一个根结点,和两棵,互不相交的,左子树、右子树,构成，并且左、右子树本身也是二叉树特性,二叉树中每个结点,最多有两棵子树,；二叉树,每个结点的度小于等于,2,子树有左右之分，不能颠倒,有序树,二叉树是,递归结构,，在二叉树的定义中又用到了二叉树的概念,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,6.2 二叉树的类型定义和实现,16,二叉树与,度为2的树,相同吗？为什么？,答案：二叉树与度为2的树,不相同,；,1.,度为,2,的树不能,为,空树,，,二叉树,可以为,空树,。

2.,度为,2,的树,从形式上看与二叉树很相似，但它的,子树是无序,的，而二叉树是有序的即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在,二叉树中,即使是一个孩子也,有左右之分17,a、b两棵二叉树相同吗？为什么？,A,F,G,E,D,C,B,A,F,C,G,E,D,B,(a),(b),答案：不相同因为，二叉树是有序树，而a和b两棵二叉树的左右子树不同18,二叉树的五种基本形态：,空树,只含根结点,右子树为空树,左子树为空树,左右子树均不为空树,19,二叉树的抽象数据类型定义如下：,ADT BinaryTree,数据对象：,D 是,具有相同特性,的数据元素的集合数据关系：,若D为空集，则称为,空树,否则:,(1)在D中存在唯一的称为,根,的数据元素,root,；,(2)当,n,1时，,其余结点,可分为,2个,互不相交的有限集,T,1,、,T,2,，其中每一棵子集本身又是一棵符合本定义的,二叉树，,T,1,称为根,root,的,左子树,，,T,2,称为根,root,的,右子树,20,基本操作：,初始化操作,InitBiTree(&T),操作结果：,构造空二叉树 TDestroyBiTree(,初始条件：,二叉树 T 存在。

操作结果：,销毁二叉树 T结构销毁操作,CreateBiTree(&T,definition),初始条件：,definition 给出二叉树 T 的定义操作结果：,按 definition 构造二叉树 T21,引用型操作,Root(T),初始条件：,二叉树 T 存在操作结果：,返回二叉树T的根结点Parent(T,e),初始条件：,二叉树 T 存在，e 是 T 中某个结点操作结果：,若e是T的非根结点，则返回它的双亲，,否则返回“空”Value(T,e),初始条件：,二叉树 T 存在，e 是 T 中某个结点操作结果：,返回e的值22,引用型操作（续）,LeftChild(T,e,),初始条件：,二叉树 T 存在，e 是 T 中某个结点操作结果：,返回 e 的,左孩子,若 e 无左孩子，,则返回空RightChild(T,e,),初始条件：,二叉树 T 存在，e 是 T 中某个结点操作结果：,返回 e 的,右孩子,若 e 无右孩子，,则返回空23,引用型操作（续）,RightSibling(T,e,),初始条件：,二叉树 T 存在，e 是 T 中某个结点操作结果：,返回 e 的,右兄弟,。

若 e 是其双亲的,右孩子或无右兄弟，则返回空LeftS,ibling(T,e,),初始条件：,二叉树 T 存在，e 是 T 中某个结点操作结果：,返回 e 的,左兄弟,若 e 是其双亲的,左孩子或无左兄弟，则返回“空”24,引用型操作（续）,BiTreeEmpty(T);,初始条件：,二叉树 T 存在操作结果：,若T为,空二叉树,，则返回 TRUE，否则,返回 FALSEBiTreeDepth(T),初始条件：,二叉树 T 存在操作结果：,返回 T 的,深度,25,引用型操作（续）,PreOrderTraverse(T,Visit,()根左右,初始条件：,二叉树 T 存在，visit 是对结点操作的应用函数操作结果：,先序遍历,T，对每个结点调用函数 visit 一,次且仅一次一旦 visit()失败，则操作失败InOrderTraverse(T,Visit,()左根右,初始条件：,二叉树 T 存在，visit 是对结点操作的应用函数操作结果：,中序遍历,T，对每个结点调用函数 Visit 一次且仅一次一旦 visit()失败，则操作失败26,引用型操作（续）,PostOrderTraverse(T,Visit,()左右根,初始条件：,二叉树 T 存在，visit 是对结点操作的应用函数。

操作结果：,后序遍历,T，对每个结点调用函数 visit 一次且仅一次一旦 visit()失败，则操作失败LevelOrderTraverse(T,Visit,(),初始条件：,二叉树 T 存在，visit 是对结点操作的应用函数操作结果：,层序遍历,T，对每个结点调用函数 visit 一次且仅一次一旦 visit()失败，则操作失败27,加工型操作,InsertChild(&T,p,LR,c,),初始条件：,二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，,非空二叉树 c,与 T 不相交且,右子树为空,操作结果：,根据 LR 为 0 或 1，,插入 c,为 T 中 p 所指结点的左或右子树p 所指结点,原有左或右子树成为 c 的右子树,28,加工型操作,DeleteChild(&T,p,LR);,初始条件：,二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1操作结果：,根据 LR 为 0 或 1，,删除,T 中 p 所指结点的左或右子树29,加工型操作,（续）,ClearBiTree(&T),初始条件：,二叉树 T 存在,操作结果：,将二叉树 T,清为空树,。

ADT BinaryTree,Assign(&T,&,e,value,),初始条件：,二叉树 T 存在。