资源描述：
《树和二叉树第六章树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第六章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用6.1树的定义和基本术语树(Tree)：是n(n>=0)个结点的有限集。在任意一个非空树中：⑴有且仅有一个特定的称为根(Root)的结点；⑵当n>=1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中Ti是一棵树，称为根结点子树例:(a)是只有一个根结点的树.(b)是有13个结点的树，A是根，其余结点分成三个互不相交的子集：T1=(B,E,F,K,L);T2=(C,
2、G);T3=(D,H,I,J,M).T1,T2,T都是根A的子树，本身也是一棵树AAFLDJGEBIKHMC(a)只有根结点的树T1T2T3(b)一般的树A是根，T1,T2,T3是三棵子树ADTTree{数据对象D:D是具有相同特性的数据元素的集合.数据关系R:若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H},H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；抽象类型树的定义(2)若D-{root}=φ，则存在D-{root}的一个划分D1D2
3、,…,Dn(m>0),对任意j=k(1<=j,k<=m)有Dj∩Dk=φ,且对任意的i(1<=i<=m),唯一存在数据元素xi∈Di，有∈H;⑶对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1,H2,…,Hn(m>0),对任意的j=k(1<=j,k<=m)有Hj∩Hk=φ，且对任意i(1<=i<=m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。基本操作P:InitTree(&T);操作结果：
4、构造空树TDestroyTree(&T);初始条件：树T存在操作结果：销毁树T树的基本操作CreatTree(&T,definition);初始条件：definition给出树T的定义操作结果：按definition树构造树TClearTree(&T)初始条件：数T存在操作结果：将树T清为空树TreeEmpty(T);初始条件：树T存在操作结果：若T为空树，则返回TRUE，否则FALSETreeDepth(T);初始条件：树T存在操作结果：返回T的深度Root(T);初始条件：树T存在操作结果：返回T的
5、根Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：返回cur_e的值Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点操作结果：结点cur_e赋值为valueParent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e是T的非叶子结点，则返回
6、它的最左孩子，否则返回“空”RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”InsertChild(&T,&P,i,c);初始条件：树T存在，P指向T中某个结点，1<=i<=P所指结点的度+1,非空树c与T不相交操作结果：插入c为T中p指结点第i棵子树DeleteChild(&T,&P,i);初始条件：树T存在,p指向T中某个结点，1<=i<=P指结点的度操作结果：删除T中P所指结点的第i棵子树T
7、raverseTree(T,Visit());初始条件：树T存在,Visit是对结点操作的应用函数操作结果：按某种次序树对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败}ADTTree树的逻辑表示形式(a)树型结构(b)嵌套集合(c)广义表(d)凹入表(目录表示法)ACFEBDABCDEF(b)(a)(A(B(E),C(F),D)(C)ABECFD(d)凹入表度：结点拥有的子树数称为结点的度叶子（终端结点）：度为0的结点非终端结点（分支结点）：度不为0的结点树的度是
8、树内各结点的度的最大值结点的子树的根称为该结点的孩子该结点称为孩子的双亲(parent)深度：树中结点的最大层次树的基本术语AFLDJGEBIKHMC例下图，D是A的子树T3的根，则D是A的孩子，而A则是D的双亲，同一个双亲的孩子之间互称兄弟。结点的层次从根开始定义起，根为第一层，根的孩子为第二层。T3T2T1有序树：将树中结点的各子树看成从左到右是有次序的（不能互换），称该树为有序树。无序树：将树中结点的各子树看成从左到右是无次序的（不能
