资源预览内容
第1页 / 共168页
第2页 / 共168页
第3页 / 共168页
第4页 / 共168页
第5页 / 共168页
第6页 / 共168页
第7页 / 共168页
第8页 / 共168页
第9页 / 共168页
第10页 / 共168页
亲,该文档总共168页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
数据结构 C+实现 第六章 树和森林 缪淮扣 顾训穰 沈 俊 编著 科 学 出 版 社,新世纪计算机专业系列教材,主要内容 树的概念 二叉树 二叉树的存储结构 遍历二叉树 线索二叉树 二叉树的应用,树的概念,某家族的血统关系如下: 张宇有四个孩子分别是:张山、张川、张星和张月; 张山有二个孩子张冰和张雪; 张星有三个孩子张雨、张云和张风; 张云有两个孩子张亮和张丽。,树的定义: 树(tree)T是一个包含n(n=0)个数据元素的有限集合。并且有: (1)当n=0时,T称为空树; (2)如果n0,则树有且仅有一个特定的被称为根(root)的结点,树的根结点只有后继,没有前驱; (3)当n1时,除根结点以外的其余结点可分为m(m0)个互不相交的非空有限集T1、T2、.、Tm,其中每一个集合本身又是一棵非空树,并且称它们为根结点的子树(subtree)。,如右图(a)表示了一棵空树,它没有数据元素; 如右图(b)表示了只有一个数据元素的树,树中只有一个没有子树的根结点A; 如右图(c)是有14个数据元素结点的树,其中A是树根,其余结点分成三个互不相交的有限集:T1=B,E,F,K,L、T2=C,G、T3=D,H,I,J,M,N,T1、T2、T3又都是树,且它们是结点A的子树。,树的术语: 1结点(node):在树中每一个数据元素及指向其子树根的分支称为一个结点。 2结点的度(degree of node):一个结点的子树数目称之为该结点的度。例如在图(c)所示的树中, 结点A的度为3,结点C的度数为1, 结点E的度数为0。,3终端结点(terminal node):在树中,度为0的结点称为终端结点或叶子(leaf)。如在图(c)所示的树中,结点E,K,L,G,H,M,N,J都是树的叶子。 4非终端结点(nonterminal node):在树中,度不为0的结点称为非终端结点或分支结点。除根结点之外的分支结点也称内部结点。如在图(c)所示的树中,结点A、B、C、D、F、I都是树的分支结点,且结点B、C、D、F、I是树T的内部结点。,5树的度(degree of tree):树的结点中,最大的度称为该树的度。如图(c)所示的树,其度为3。 6孩子(child)和双亲(parent):在树中,结点p的子树的根称为结点p的孩子;反之,这个结点p称为其孩子的双亲(父亲)。如在图(c)所示的树中,结点D为结点A的子树的根,因此结点D是结点A的孩子,结点A是结点D的双亲结点(父结点)。 7兄弟(sibling):在树中,同一个双亲的孩子之间互称为兄弟。例如,在图(c)所示的树中,结点B、C、D互为兄弟。,8祖先(ancestor):在树中,从根结点到结点x所经的分支上的所有结点称为结点x的祖先。如在图(c)所示的树中,结点M的祖先为:A、D、I。 9子孙(descendant):在树中,以某结点p为根的子树中的所有结点都称为结点p的子孙。例如在图(c)所示的树中,D的子孙有H、I、J、M、N。,10结点的层次(level):在树中,从根结点开始,根为第一层,根的孩子为第二层,依次类推,树中任一结点的层次是其双亲结点层次数加1。例如在图(c)所示的树中,结点K、L、M、N的层次数为4。 11树的深度(depth):树中结点的最大层次称为树的深度或树的高度(height)。例如图(c)所示的树的深度为4。 12堂兄弟:双亲在同一层的结点互称为堂兄弟。如在图(c)所示的树中,结点F、G、H互称为堂兄弟。,13有序树:如果树中结点p的各棵子树是有次序的则称该树为有序树,此时结点p从左到右的k子树分别称为p的第1棵子树、第2棵子树、第k棵子树。 14无序树:如果树中结点的各棵子树的次序是无关的则称该树为称无序树。 15森林(forest):森林是m(m0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。,树的表示形式: 树形表示法 嵌套集合表示法 凹入目录表示法 广义表形式的表示法。,由于树形表示法比较直观,所以在本书中主要采用树形表示法来表示树形结构。,树的基本操作: (1)Root ( ):求树根结点的指针,若树为空,则返回0。 (2)CreateRoot ( d ):建立树的根结点,使根结点的数据元素值为d。 (3)Parent( x ):求树中给定结点x的双亲结点的指针,若x为根结点,则返回空。,(4)FirstChild ( x ):求树中给定结点x的第一个孩子结点的的指针,若x为叶子结点,则返回空。 (5)NextSibling ( x, y ):给定结点x、y,其中结点y是结点x的一个孩子。该函数求树中结点y的下一个兄弟结点的指针,若结点y是结点x的最后一个孩子,则返回空。,(6)PreSibling ( x, y ) 给定结点x、y,其中结点y是结点x的一个孩子。该函数求树中结点y的前一个兄弟结点的指针,若结点y是结点x的第一个孩子,则返回空。 (7)Retrieve ( x ):求给定结点x中数据元素的值。 (8)Assign (x,d):对二叉树中给定结点x赋值为d。 (9)InsertChild ( x,d ):在结点x下插入数据元素值为d的新孩子结点,若插入成功,则返回1;否则返回0。,(10)DeleteChild ( x,i ):删除以结点x的第i个孩子为根的子树,若删除成功,则返回1;否则返回0。 (11)DeleteSubTree ( x ):删除以结点x为根的子树; (12)IsEmpty ( ):判断树是否为空树。若树为空树,则返回1;否则返回0。 (13)Travers( ):遍历树,按某种次序依次访问树中的每一个结点,并使每一个结点只被访问一次。,树的抽象数据类型: ADT tree is Data 树的根结点 Operation Root 输入:无 前置条件:无 动作:求树根结点的指针,若树为空,则返回空指针。 输出:树的结点的指针 后置条件:无,CreateRoot 输入:数据元素d 前置条件:无 动作:建立树的根结点,使根结点的数据元素值为d。 输出:树的结点指针 后置条件:无,Parent 输入:树中的结点x 前置条件:无 动作:求树中给定结点x的双亲结点的指针,若x为根结点,则返回空。 输出:树中结点的指针 后置条件:无,FirstChild 输入:树中的结点x 前置条件:无 动作:求树中给定结点x的第一个孩子结点的的指针,若x为叶子结点,则返回空。 输出:树中结点的指针 后置条件:无,NextSibling 输入:树中的结点x、y 前置条件:无 动作:给定结点x、y,其中结点y是结点x的一个孩子。该函数求树中结点y的下一个兄弟结点的指针,若结点y是结点x的最后一个孩子,则返回空。 输出:树中结点的指针 后置条件:无,PreSibling 输入:树中的结点x、y 前置条件:无 动作:给定结点x、y,其中结点y是结点x的一个孩子。该函数求树中结点y的前一个兄弟结点的指针,若结点y是结点x的第一个孩子,则返回空。 输出:树中结点的指针 后置条件:无,Retrieve 输入:树中的结点x 前置条件:结点x必须存在 动作:求给定结点x中数据元素的值 输出:树结点中数据元素 后置条件:无,Assign 输入:树中的结点x和数据元素d 前置条件:结点必须存在 动作:对树中给定结点x赋值为d 输出:无 后置条件:无,InsertChild 输入:结点x和数据元素d 前置条件:结点x必须存在 动作:在结点x下插入数据元素值为d的新孩子结点,若插入成功,则 返回1;否则返回0。 输出:无 后置条件:无,DeleteChild 输入:结点x和序号i 前置条件:结点x必须存在且结点x孩子个数超过i 动作:删除以结点x的第i个孩子为根的子树,若删除成功,则返回1;否则返回0。 输出:1或0 后置条件:无,DeleteSubTree 输入:树中结点x 前置条件:树中结点x 动作:删除以结点x为根的子树 输出:无 后置条件:无,IsEmpty 输入:无 前置条件:无 动作:判断树是否为空。若树为空,则返回1;否则返回0。 输出:1或0 后置条件:无,Travers 输入:无 前置条件:无 动作:遍历树,按某种次序依次访问树中的每一个结点,并使每一个结点只被访问一次。 输出:一般为数据元素序列 后置条件:无 end ADT tree,二叉树,二叉树的定义 : 二叉树BT是有限个结点的集合。当集合非空时,其中有一个结点称为二叉树的根结点,用BT表示,余下的结点(如果有的话)最多被组成两棵分别被称为BT的左子树(left subtree)和右子树(right subtree)、互不相交的二叉树。 二叉树的五种形态 :,二叉树的性质 : 性质1:有n(n0)个结点的二叉树的分支数为n-1。 证明:因为在二叉树中,除根结点以外的其它每个结点有且仅有一个父结点。而子结点与父结点间有且只有一条分支,因此对于有n(n0)个结点的二叉树,其分支的数目为n-1。,性质2:若二叉树的高度为h(h0),则该二叉树最少有h个结点,最多有2h-1个结点。 证明:因为在二叉树中,每一层至少要有1个结点,因此对于高度为h的二叉树,其结点数至少为h个。 在二叉树中,第一层只有一个根结点;又因为每个结点最多有2个孩子结点,所以第i层的结点最多为2i-1个,所以高度为h(h0)的二叉树结点总数最多为: 20 + 21 + + 2h-1 = 2h - 1,性质3:含有n个结点的二叉树的高度最大值为n,最小值为log2(n+1) 。 证明:因为在二叉树中,每层至少有一个结点,因此对于含有n个结点的二叉树,其高度不会超过n。 根据性质2可以得知,高度为h的二叉树最多有2h-1个结点,即n2h-1,因此hlog2(n+1)。 由于h是整数,所以hlog2(n+1)。,满二叉树的定义:若高度为h的二叉树具有最大数目(2h-1个)的结点,则称其为满二叉树(full binary tree )。 完全二叉树的定义:若高度为h的二叉树,除第 h 层外,其它各层 (1 h-1) 的结点数都达到最大个数,并且第 h 层的结点是自左向右连续分布的。则称它为完全二叉树(complete binary tree )。,性质4:具有 n 个结点的完全二叉树的高度为log2(n+1) 。 证明:设完全二叉树的高度为h,则由性质2得: 2h-1-1n2h -1 2h-1n+12h 不等式中的各项取对数得:h-1log2(n+1)h。因为h为整数,所以h=log2(n+1)。,性质5:如果将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号0、1、2、n-1。则有以下关系: (1)若i0,则 i 无双亲,若i0,则 i 的双亲为i/2-1; (2)若2*i+1n,则 i 的左孩子为2*i+1; (3)若2*i+2n,则 i 的右孩子为2*i+2; (4)若i为偶数,且i1,则 i 是其双亲的右孩子,且其有编号为i-1左兄弟; (5)若i为奇数,且in-1,则 i 是其双亲的左孩子,且其有编号为i+1右兄弟。,证明:此性质可以用归纳法证明,在此先证明其中的(2)和(3)。 当i0时,由完全二叉树的定义得知, 如果2*i+11n,说明二叉树中存在两个或两个以上的结点,所以结点i的左孩子存在且编号为1; 反之,如果2*i+11n,说明二叉树中只有一个结点i,结点i的左孩子结点不存在。 同理,如果2i+22n,说明结点i的右孩子存在且编号为2; 如果2*i+22n,说明二叉树中不存在编号为2的结点,即结点i的右孩子不存在。,假设对于编号为j(0ji)的结点,(2)和(3)成立。 当ij+1时,根据完全二叉树的定义,若其左孩子结点存在则其左孩子结点的编号等于编号为j的结点的右孩子的编号加1,即其左孩子结点的编
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号