数据结构第六章ppt.ppt

《数据结构第六章ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6哈夫曼树及其应用6.8树的计数本章小结习题定义：树(tree)是n(n≥0)个结点的有限集，在任一棵非空树中：1）有且仅有一个特定的称为树根(root)的结点；2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。例如：特点：1）在非空树中至少有一个结点—根2）树中各子树是互不相交的集合6.1树的定义和基本术语例如:A(a)ABCDEFGHIJMKL(b)只有根结点

2、的树根子树有子树的树基本术语：树：无向树（无环的无向连通图）有向树（要不考虑孤的方向时是一棵无向树）根树（有且只有一个入度为0的结点（根），其余结点入度为1。我们书上讲的为根树根树根根的子树ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D中仅含一个数据元素，则关系R为空集；　　否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠⌽，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0),即对于

3、任意的j≠k(1≤j,k≤m)有Dj∩Dk=⌽，且对任意的i=1,2,…,m。惟一存在数据元素xi∈Di,有∈H；抽象数据类型树的定义如下：(3)对应于D-{root}的以上划分，H-{,,…,}有惟一的一个划分H1,H2,H3,…,Hm(m>0),即对于任意的j≠k(1≤j,k≤m)有Hj∩Hk=⌽，且对任意的i(1≤i≤m),Hi是Di上的二元关系，（Di，Hi）是一棵符合本定义的树，称为根root的子树。基本操作：15种基本操作，P119}//tree基本术语

4、：结点:表示树中的元素，包括数据项及若干指向其子树的分支结点的度:分支个数（结点拥有的子树个数）。树的度:树中所有结点的度的最大值叶子结点:度为零的结点分支结点:度大于零的结点从根到结点的路径：由从根到该结点所经分支和结点构成孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点ABEFKLCGDHIJM树的深度：树中叶子结点所在的最大层次假设根结点的层次为1,根的孩子就在第2层,一个结点在第l层，则其子树的根结点在l+1结点的层次:是m（m≥0）棵互不相交的树的集合森林：任何一棵非空树是一个二元组Tree=（root，F）其中：ro

5、ot被称为根结点，F被称为子树森林P121。有向树：……有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。根树：……InitTree(&T)//初始化置空树DestroyTree(&T)//销毁树的结构CreateTree(&T,definition)//按定义构造树ClearTree(&T)//将树清空Root(T)//求树的根结点Value(T,cur_e)//求当前结点的元素值LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟Tree

6、Empty(T)//判定树是否为空树TreeDepth(T)//求树的深度Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树Parent(T,cur_e)//求当前结点的双亲结点TraverseTree(T,Visit())//遍历DeleteChild(&T,&p,i)//删除结点p的第i棵子树树的表示形式：P1201）树型表示2）嵌套集合法3）广义表法4）凹入表示法~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结

7、构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素（无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)对比树型结构和线性结构的结构特点：6.2二叉树6.2.1二叉树的定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成（递归定义）特点：1）每个结点至多有二棵子树(即不存在度大于2的结点)2）二叉树的子树有左、右之分，且其次序不能任意颠倒ABCFED例左图所示是一棵二叉树：二叉树的五种基本形态：空树只含根结点

8、右子树为空树左子树为空树左右子树均不为空树抽象数据类型二叉树的定义：P121二叉树的主要基本操作（20种）：P121-123InitBiTree(&T);DestroyBiTree(&T);BiTreeEm