数据结构第六章1.ppt

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

1、6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5树和等价问题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)只有根结点的树根子树有子树的树ADTTree{数

2、据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D中仅含一个数据元素，则关系R为空集；　　否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠⌽，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0),即对于任意的j≠k(1≤j,k≤m)有Dj∩Dk=⌽，且对任意的i=1,2,…,m。惟一存在数据元素xi∈Di,有∈H；抽象数据类型树的定义如下：树：无向树（无环的无向连通图）有向树（若不考虑孤的方向时是一棵无向树）根树（有且只有一个入度为0的结点根）

3、，其余结点入度为1。书上讲的为根树基本术语：(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）其中：root被称为根结点，F被称为子树森林P121。有向树：……有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。根树：……InitTree(&T)//初始化置空树DestroyTree(&T)//销毁树的

5、结构CreateTree(&T,definition)//按定义构造树ClearTree(&T)//将树清空Root(T)//求树的根结点Value(T,cur_e)//求当前结点的元素值LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树Parent(T,cur_e)//求当前结点的双亲结点Tr

6、averseTree(T,Visit())//遍历DeleteChild(&T,&p,i)//删除结点p的第i棵子树树的表示形式：P1201）树型表示2）嵌套集合法3）广义表法4）凹入表示法线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)对比树型结构和线性结构的结构特点：6.2二叉树6.2.1二叉树的定义二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成（递归定义）特点：1）每个结点至多有二棵子树(

7、即不存在度大于2的结点)2）二叉树的子树有左、右之分，且其次序不能任意颠倒ABCFED例左图所示是一棵二叉树：二叉树的五种基本形态：只含根结点右子树为空树左子树为空树左右子树均不为空树空树抽象数据类型二叉树的定义：P121二叉树的主要基本操作（20种）：P121-123InitBiTree(&T);DestroyBiTree(&T);BiTreeEmpty(T);CreateBiTree(&T,definit