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

《Java数据结构与算法解析(四)——树的概述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Java数据结构与算法解析(四)树的概述树：树(Tree)是n(n^O)个结点的有限集。n二0时称为空树。在任意一棵非空树中：(1)有且仅有一个特定的称为根(Root)的结点；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集匸、……、T・，其中毎一个集合本身又是一棵树.井且称为根的子树(SubTree)o树具有以下的特点：(01)每个节点有零个或多个子节点；(02)没有父节点的节点称为根节点；(03)每一个非根节点有且只有一个父节点；(04)除了根节点外，每个子节点可以分为多个不相交的子树。树的基本术语1•结点的度结点拥有的子树数称为结点的度。度为

2、0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。除根结点以外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。•根结点o内部结点o叶结点或终端结点分支结点或非终端结点•此结点度为2BEF丿此结点度为02•叶子：度为零的结点。3•分支结点：度不为零的结点。4•树的度:树中结点的］大的度。5•层次与深度结点的层次（LevEl）从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第1层，则其子树的根就在第1*1层。其双亲在同一层的结点互为堂兄弟。显然图6-2-6中的D.E、F是堂兄弟，而G・H.LJ也是。树中结点的最大层次称为树的深

3、度（Depth）或高度'当前树的深度为4。堂兄弟6•树的高度：树中结点的最大层次。7•无序树：如果树中结点的各子树之间的次序是不重要的，可以交换位置。8•有序树：如果树中结点的各子树之间的次序是重要的，不可以交换位置。9•森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根,树即成为森林。树的存储结构1.简单的顺序存储不能满足树的实现2.结合顺序存储和链式存储来实现三种表示方法•双亲表示法•孩子表示法•孩子兄弟表示法1•双亲表示法在每个结点中，附设一个指示器指示其双亲结点到链表中的位置dataparent下标dataparent0A1B02C0

4、3D14E25F26G37H38139J41•孩子表示法1•方案一2.方案二GOHOI0J01.最终方案把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中234567893•孩子兄弟表示法任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟data[firstchildrightsib~

5、AAB>CA1fAEFAA二叉树例子：猜1()0以内

6、的整数，注意猜的次数不能超过7个，回答者只回答大了还是小了二叉树(BinaryTree)是n(nMO)个结点的有限集合.该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成。i・二叉树的定义二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。:（1）空二叉树I（2）根和空的左右子榊二叉树的5种基本形态根和左右子树2•二叉树的性质性质1：在二叉树的第i层上至多有2（口）个结点（i〉=l）o性质2：深度为k的二叉树至多有2性1个结点（k

7、>=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

8、。性质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证明：在具有相同

9、深度的二叉树中，当每一层