[计算机软件及应用]数据结构第6章

《[计算机软件及应用]数据结构第6章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构常静Email:yifeng925@126.com第六章树和二叉树二叉树6.2树的定义和基本术语6.1遍历二叉树和线索二叉树6.3树和森林6.4第六章树和二叉树树的定义和基本术语6.1树的例子（1）：第一节树的定义树的例子（2）：第一节树的定义1．树的定义树(Tree)是n(n≥0)个有限数据元素的集合。(1)当n＝0时，称这棵树为空树。在一棵非空树T中：(2)在n>0时，有且仅有一个特殊的数据元素称为树的根结点，根结点只有后继结点，没有前驱结点。(3)若n>1，除根结点之外的其余数据元素被分成m(m>0)个互不相交的集合T1，T2，…，Tm，其

2、中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。ACGT2DHIT3JMBELKT1F空树仅有根结点的树第一节树的定义下面列出一些树结构和非树结构的示意图：第一节树的定义2.树的表示方法1)直观表示法（a）树的直观表示法是以倒着的分支树的形式表示。2)嵌套集合表示法(b)3)凹入表示法(c)4)广义表表示法(d)（a）（b）（d）（c）第一节树的定义对比树型结构和线性结构的结构特点第一节树的定义~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后

3、一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)结点（node）：树中的每个元素及指向其子树根的分支。结点的度（degreeofnode）：一个结点的子树个数。终端结点（terminalnode）(叶子（leaf)）：度为0的结点。非终端结点（nonterminalnode）（分支结点）：度不为0的结点。树的度（degreeoftree）：树内各结点的度的最大值。结点的层次（level）：根为第一层，依次类推。树的深度（depth）（高度（height））：树中结点的最大层次有序树：树中结点

4、的子树是有次序的。无序树：树中结点的子树是无次序的。第二节基本术语在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子（child）和双亲（parent）：结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。兄弟（sibling）：同一个双亲的孩子之间互为兄弟。堂兄弟：双亲在同一层的结点互为堂兄弟。祖先（ancestor）：从根结点到该结点路径上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。第二节基本术语任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林（Fores

5、t）：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLFADTTree{数据对象：D是具有相同特性的数据元素的集合。数据关系：　　若D为空集，则称为空树；　　若D中仅含一个数据元素，则关系R为空集；　　否则R={H}，(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)当n>1时，其余数据元素可分为m(m>0)个互不相交的(非空)有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root的后继，即H,i=1,2,…,m。第三

6、节树的抽象数据类型基本操作：{结构初始化}InitTree(&T);操作结果：构造空树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。　　　操作结果：按definition构造树T。{销毁结构}DestroyTree(&T);初始条件：树T存在。　　　操作结果：销毁树T。第三节树的抽象数据类型TreeEmpty(T);初始条件：树T存在。　　　操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。　　　操作结果：返回T的深度。Root(T);初

7、始条件：树T存在。　　　操作结果：返回T的根。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的非叶子结点，则返回它的最左孩子，否则返回"空"。RightSibling(T,cur_e);初始条件：树

8、T存在，cur_e是T中某个结点。　　操作结果：若cur_e有右兄弟，则返回它