Java数据结构与算法解析(四)——树的概述

(16页)

'Java数据结构与算法解析(四)——树的概述'
Java数据结构与算法解析(四)树的概述树:树(Tree)是n (n^O)个结点的有限集。n二0时称为空树。在任意一棵非空 树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其 余结点可分为m (m>0)个互不相交的有限集匸、……、T?,其中毎一个 集合本身又是一棵树.井且称为根的子树(SubTree)o树具有以下的特点:(01)每个节点有零个或多个子节点;(02)没有父节点的节点称为根节点;(03)每一个非根节点有且只有一个父节点;(04)除了根节点外,每个子节点可以分为多个不相交的子树。树的基本术语1 ?结点的度结点拥有的子树数称为结点的度。度为0的结点称为叶子结点或终端结点,度不为 0的结点称为非终端结点或分支结点。除根结点以外,分支结点也称为内部结点。 树的度是树内各结点的度的最大值。?根结点o内部结点o叶结点或终端结点分支结点或非终端结点?此结点度为2BEF丿此结点度为02?叶子:度为零的结点。3?分支结点:度不为零的结点。4 ?树的度:树中结点的]大的度。5 ?层次与深度结点的层次(LevEl)从根开始定义起,根为第一层,根的孩子为第二层。若某结 点在第1层,则其子树的根就在第1*1层。其双亲在同一层的结点互为堂兄弟。显然 图6-2-6中的D. E、F是堂兄弟,而G?H. L J也是。树中结点的最大层次称为树 的深度(Depth)或高度'当前树的深度为4。堂兄弟6?树的高度:树中结点的最大层次。7?无序树:如果树中结点的各子树之间的次序是不重要的,可以交换位置。8?有序树:如果树中结点的各子树之间的次序是重要的,不可以交换位置。9?森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。树的存储结构1. 简单的顺序存储不能满足树的实现2. 结合顺序存储和链式存储来实现三种表示方法?双亲表示法?孩子表示法?孩子兄弟表示法1 ?双亲表示法在每个结点中,附设一个指示器指示其双亲结点到链表中的位置data parent下标dataparent0A1B02C03D14E25F26G37H38139J4 2 ?孩子表示法1?方案一2.方案二GO HO I 0 J 03. 最终方案把每个结点的孩子结点排列起来,以单链表作为存储结构,则n个结点有n个孩子 链表,如果是叶子结点则此单链表为空,然后n个头指针又组成一个线性表,采用 顺序存储结构,存放在一个一维数组中 234567893 ?孩子兄弟表示法任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也 是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右 兄弟data [ firstchild rightsib ~|AAB > CA1fAE\FAA二叉树例子:猜1()0以内的整数,注意猜的次数不能超过7个,回答者只回答大了还是小 了二叉树(Binary Tree )是n ( nMO )个结点的有限集合.该集合 或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交 的.分别称为根结点的左子树和右子树的二叉树组成。i?二叉树的定义二叉树是每个节点最多有两个子树的树结构。它有五种基本形态:二叉树可以是空 集;根可以有空的左子树或右子树;或者左、右子树皆为空。:(1)空二叉树I(2)根和空的左右子榊二叉树的 5种基本形态根和左右子树2 ?二叉树的性质性质1:在二叉树的第i层上至多有2(口)个结点(i〉=l) o性质2:深度为k的二叉树至多有2性1个结点(k>=l) o性质3:对任何一颗二叉树T,如果其终端结点数为nO,度为2的结点 数为n2,则 nO = n2+l.性质4:包含n个结点的二叉树的高度至少为log2(n+l)o性质5:如果对一颗有n个结点的完全二叉树(其深度为[logm]+l)的结点按层序 编号(从第1层到第[log2n]+l层,每层从左到右),对任意一个结点i(l<=i<=n)W:1) ?如果匸1,则结点i是二叉树的根,无双亲;如果i>l,则其双亲是结 点[i/2]2) .如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。3) .如果2i+l>n,则结点i无右孩子;否则其右孩子是结点2i+l。性质1:在二叉树的第i层上至多有2冋个结点(i>=l)。证明:下面用”数学归纳法”进行证明。(1) 当匸1时,第i层的节点数目为"吩2?=1。因为第1层上只有一个根结点,所 以命题成立。⑵ 假设当i>l,第i层的节点数目为2冋。这个是根据(1)推断出来的!下而根据这个假设,推断出"第(i+1)层的节点数目为2咿即可。由于二叉树的每个结点至多有两个孩子,故”第(i+1)层上的结点数屮 最多是“第i 层的结点数目的2倍”。即,第(i+1)层上的结点数目最大值=2x23=2"}。故假设成立,原命题得证!性质2:深度为k的二叉树至多有2(札1个结点(k>=l) o证明:在具有相同深度的二叉树中,当每一层都含有最大结点数时,其树中结点数 最多。利用"性质T可知,深度为k的二叉树的结点数至多为:2°+2,+...+2k-,=2k-l故原命题得证!性质3:对任何一颗二叉树T,如果其终端结点数为nO,度为2的结点数为n2,则 nO = n2+l.证明:因为二叉树屮所有结点的度数均不大于2,所以结点总数(记为n)=P度结点 数(nO)” + “l度结点数(nlf + "2度结点数(n2)S由此,得到等式一。(等式一)n=nO+nl+n2另一方面,0度结点没有孩子,1度结点有一个孩子,2度结点有两个孩子,故二叉 树中孩子结点总数是:nl+2n2o此外,只有根不是任何结点的孩子。故二叉树中的 结点总数又可表示为等式二。(等式二)n=nl+2n2+l由(等式一)和(等式二)计算得到:nO二n2+l。原命题得证!性质4:包含n个结点的二叉树的高度至少为log2(n+l)o证明:根据计生质夢可知,高
关 键 词:
Java 数据结构 算法 解析 概述
 剑锋文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:Java数据结构与算法解析(四)——树的概述
链接地址: //www.wenku365.com/p-43709247.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给剑锋文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 //www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开