资源描述：
《树与二叉树中文讲课稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、树与二叉树中文6.1.1树的定义与表示树的定义：树的逻辑结构可以这样描述：树是包含N(N>0)个节点的有穷集合D，且在D上定义了一个关系R，关系R满足以下条件：(1)有且仅有一个节点e0D，它对于关系R来说没有前驱，节点e0称作树的根。(2)除节点e0外，D中的每个节点对于关系R来说都有且仅有一个前驱。(3)除节点e0外的任何节点eS，都存在一个节点序列(e0,e1,…,em)，其中e0就是树根，且em=e，有序对R（1≤i≤m）。这样的节点序列称为从根到节点e的一条路径。树的递归定义：树是由一个或多个节点组成的有限集T，它满足下面两个条件：(1
2、)有一个特定的节点称之为根;(2)其余的节点分成m(m≥0)个互不相交的有限集T1，T2，…，Tm，其中每个集合本身又是一棵树，称T1，T2，…，Tm为根的子树。递归是树的固有属性树的表示：体现树形结构中分支和层次的特性。本书中描述树形结构的方式6.1.2树的基本术语节点节点的度叶子或终端节点非终端节点或分支节点内部节点树的度孩子双亲兄弟祖先子孙节点的层次树的深度或高度有序树无序树森林6.1.3树的ADTADTTree{数据对象为D:D是具有相同特性的数据元素的集合数据间的关系R:(1)若D为空集,则称为空树;(2)若D为非空集且仅含有一个数据元素,则R为空集,树只包含
3、一个根节点;允许空树（即树中没有一个节点的树）存在(3)若D为非空集且含有不止一个数据元素,则R={H},H是同时满足如下条目的二元关系:(3.1)D中存在唯一的一个称为根的数据元素r,它在关系H下无前驱;(3.2)D-{r}Ф,存在D-{r}的一个划分D1,D2,…,Dm(m>0),对任意jk(1≤j,k≤m)有Dj∩Dk=Ф,且对任意的i(1≤i≤m),惟一存在数据元素xi∈Di有∈H;(3.3)对应于D-{r}的划分,H-{,,…,}有惟一的一个划分H1,H2,…,Hm(m>0),对任意jk(1≤j,k≤m)有
4、Hj∩Hk=Ф,且对任意的i(1≤i≤m),Hi是Di上的二元关系,(Di,{Hi})是一棵符合本定义的树,称为根r的子树。几种基本操作:treeCreate(&tree)treeDestroy(&tree)treeClear(&tree)treeEmpty(tree)treeWidth(tree)创建一棵树tree销毁一棵已有的树tree创建一棵树tree判树是否为空求树的度treeDepth(tree)treeRoot(tree)treeInsert(&tree,elem)treeDelete(&tree,elem)求树的高度(深度)求树的根在树tree中,按照某种
5、规则将元素elem插入到树中合适位置在树tree中,按照某种规则将树中元素elem删除treeTraverse(tree,visit)treeGetParent(tree,elem,&parent)treeGetChild(tree,parent,order,&child)遍历树tree各元素，并用visit代表的操作处理元素数据在树tree中求节点elem的父节点，并将结果放入parent中说明:在树tree中求节点parent的第order个子节点，并将结果放入child中treeSetChild(tree,parent,order,child)}在树tree中设置
6、节点parent的第order个子节点，待设置的值已经放入child中6.2二叉树6.2.1二叉树的定义与基本运算二叉树是一个集合T；它可以是空集，也可以是一个由节点组成的有限集。同时，集合T具有下列的性质：(1)如果T是空集，则称T是空的二叉树。(2)如果T是有限集，则T由一个特定的、称之为根的节点，以及称为该根的两个互不相交的左子树和右子树构成，同时这两棵子树亦是二叉树。递归定义二叉树可以有5种基本形态，二叉树的基本运算与树的基本运算相类似详见二叉树的ADT说明6.2.2二叉树的性质性质(1)：在二叉树的第i层上至多有2i-1个节点（i≥1）。性质(2)：深度为k的
7、二叉树至多有2k-1个节点（k≥1）。性质(3)：对任何一棵二叉树T，如果其叶节点数为n0，度为2的节点数为n2，则n0=n2+1。特殊形态的二叉树：完全二叉树和满二叉树。满二叉树：一棵深度为k且有2k-1个节点的二叉树。特点：每一层上的节点数都达到了最大节点数。完全二叉树：（1）叶子节点只可能在层次最大的两层上出现；（2）对任一节点，若其右分支下的子孙节点的最大层次为k，则其左分支下的子孙的最大层次不小于k。满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。完全二叉树的两个重要特性：性质(4)：具有n个节点的完全二叉树的深度为log
