数据结构第六章(公共邮箱).ppt

《数据结构第六章(公共邮箱).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第六章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和搜索二叉树6.4树和森林6.6赫夫曼树及其应用6.1树的定义和基本术语树的定义树是由n(n0)个结点组成的有限集合.如果n=0,称为空树;如果n>0，则称为非空树。在一棵非空树中：有且仅有一个称为根(Root)的结点，它只有直接后继，但没有直接前驱；当n>1时，除根以外的其它结点可划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，每个集合本身又是一棵树，并且称之为根的子树(SubTree)。每棵子树的根结点有且仅有

2、一个直接前驱，但可以有0个或多个直接后继。1层2层4层3层height=4ACGBDEFKLHMIJA只有根结点的树T1={B,E,F,K,L}T2T3T1T11={E,K,L}T12={F}树的抽象数据类型定义：ADTTree{数据对象D：数据关系R：基本操作：}ADTTree若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树,称为根root的子树

3、。D是具有相同特性的数据元素的集合。基本术语结点:数据元素+若干指向子树的分支结点的度:分支的个数树的度:树中所有结点的度的最大值叶子结点:度为零的结点分支结点:度大于零的结点从根到结点的路径:由从根到该结点所经分支和结点构成。孩子结点双亲结点兄弟结点祖先子孙ACBDEACGBDEFKLHMIJ1层2层4层3层ACGBDEFKLHMIJ结点的层次:假设根结点的层次为1,第L层的结点的子树根结点的层次为L+1堂兄弟：双亲在同一层的结点互为堂兄弟。树的深度：树中叶子结点所在的最大层次数。有序树：树中结点

4、的子树从左到右是有次序的。无序树：森林：是m（m≥0）棵互不相交的树的集合任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林ACGBDEFKLHMIJCGBDEFKLHMIJ基本操作查找插入删除查找（8）Root(T);Value(T,cur_e);Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);TreeEmpty(T);TreeDepth(T);TraverseTree(T,Visit(

5、));特定查找按关系查找按树的特性查找插入（4）InitTree(&T);CreateTree(&T,definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);在P结点下面插入一棵以c为根的子树，作为P结点的第i棵子树赋值删除（3）ClearTree(&T);DestroyTree(&T);DeleteChild(&T,&p,i);删除p结点的第i棵子树树形结构和线性结构的比较线性结构树结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元

6、素(无后继)多个叶子结点(无后继)其它数据元素树中其它结点(一个前驱、一个后继)(一个前驱、多个后继)（a,b,c,d,e,f）ACBDEF树的表示法P120树型表示法文氏图法广义表法（嵌套括号）凹入法ACBDEFABCDEHIFJG二叉树:每个结点至多只有两棵子树(每个结点的度不大于2),而且两棵子树有左右之分,其次序不能任意颠倒。6.2二叉树(BinaryTree)左子树右子树二叉树是有序树二叉树的五种基本形态：LRLRLR二叉树的主要基本操作：查找Root(T);Value(T,e);Pare

7、nt(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());先序遍历中序遍历后序遍历层序遍历插入InitBiTree(&T);A

8、ssign(T,&e,value);结点e赋值value。CreateBiTree(&T,definition);InsertChild(T,p,LR,c);为结点P插入子树C，如果LR等于0，那么插入的子树C作为P的左子树，如果LR等于1，则插入的子树C作为P的右子树。删除：ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);清空二叉树T销毁二叉树T删除结点p的左(右)子树二叉树的重要特性：性质1：在二叉树的第