第六章 树和二叉树课件.pptVIP

第六章树和二叉树树的存储结构(孩子兄弟表示法)孩子兄弟表示法A∧B∧CD∧∧E∧∧F∧G∧ABCEFGD第六章树和二叉树森林与二叉树的转换转换原则按孩子兄弟表示法进行转换。树与二叉树的转换DE第六章树和二叉树森林与二叉树的转换第六章树和二叉树树和森林的遍历树的遍历ABCDEFGABECDFG先序遍历先访问树的根结点，然后依次先根遍历根的每棵子树；ABEFCDG (二叉树先序)后序遍历先依次后根遍历根的每棵子树，然后访问树的根结点EFBCGDA (二叉树中序)第六章树和二叉树森林的遍历先序遍历：访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除第一棵树外剩余的树构成的森林；举例：ABCDEFGHIJ中序遍历中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除第一棵树外剩余的树构成的森林举例：BCDAFEHJIG第六章树和二叉树6.5树的等价问题第六章树和二叉树集合的查找与合并集合的运算find(x)判断元素x属于哪个集合Merge(Si,Sj)将集合Si和Sj合并集合的数据结构有多种实现方法位图法O(1)有序表方法O(n)树型结构表示集合采用的结构取决于集合大小和所进行的操作第六章树和二叉树树的存储结构:双亲表示法ABCDEFG^001033０123456ABCEFGD存储方法：使用顺序结构#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;}PTNode;/*节点的存储结构*/typedefstruct{/*顺序存储结构*/PTNodenodes[MAX_TREE_SIZE];intr,n;/*根位置和节点数*/}PTree;优点：简单，紧凑，易于寻找双亲节点缺点：查询某节点的孩子效率低第六章树和二叉树树型结构表示集合采用双亲表示法，存储一个森林typePTreeMFSet;intfind_mfset(MFSetS,inti){if(i0||i=S.n)return-1;for(j=i;S.nodes[j].parent=0;j=S.nodes[j].parent);returnj;}Statusmerge_mfset(MFSetS,inti,intj){if(i0||i=S.n||j0||j=S.n)returnERROR;S.node[i].parent=j;returnOK;}第六章树和二叉树算法分析和改进分析算法的效率合并O(1),检索O(d)，d为深度，最糟糕情况下，d=n改进思路合并时，将数量少的集合，合并到数量多的集合中根的parent记录集合中节点个数，为区别于正常parent值，用负数改进后的分析合并O(1)，树深度低于log2n第六章树和二叉树6.2二叉树第六章树和二叉树二叉树的定义定义二叉树是n(n?0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和两棵互不相交的左子树和右子树的二叉树组成。二叉树的特点：定义是递归的；0?结点的度?2；是有序树。第六章树和二叉树二叉树（续）二叉树的五种基本形态两种特殊的二叉树满二叉树：每一层上的结点数都是最大结点数。完全二叉树：只有最下面两层结点的度可小于2，而最下一层的叶结点集中在左边若干位置上。?123456712345678910第六章树和二叉树二叉树的性质性质1二叉树的第i层上至多有2i-1(i?1)个结点。性质2深度为k的二叉树至多有2k-1个结点(k?1)。性质3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。性质4具有n个结点的完全二叉树的深度为?log2