位置: IT常识 - 正文
推荐整理分享树结构(树结构ADT知识点思维导图),希望有所帮助,仅作参考,欢迎阅读内容。
文章相关热门搜索词:树结构ADT知识点思维导图,树结构属于什么结构?,树结构的定义,树结构部首,树结构图,树结构图,树结构图,树结构属于什么结构?,内容如对您有帮助,希望把文章链接给更多的朋友!
树(Tree):个节点构成的有限集合。当n = 0时,称为空树。对于任一棵非空树(n>0),它具备以下性质:
树中有一个称为"根(Root)"的特殊节点,用r表示;其余节点可分为m(m>0)个互不相交的有限集、,...,,其中每个集合本身又是一棵树,称为原来树的子树(SubTree)。如下图:
1.2 树结构的术语树结构中有很多概念术语,在深入讨论树结构之前,我们先来介绍下跟树结构有关的术语。为了方便理解记忆,结合具体的一棵树结构来进行介绍,树结构如下:
节点:树中存储的项。上图中的A-L都是节点。
根节点:树中最顶端的节点。在树结构中只有它没有父节点。上图中的A为根节点。
节点的度:一个节点含有的子树的个数。根节点A的度为3;子节点C的度为1。
树的度:树中最大节点度。树中最大节点度为3(根节点A和子节点B的度均为3),所以树的度为3。
子节点(孩子节点):紧邻一个给定的节点之下,并且直接与给定节点相连的一个节点。一个节点可以有多个子节点。上图中B-L都是子节点。
父节点(双亲节点):紧邻一个给定节点之上,且直接与给定节点相连的一个节点。一个节点只能有一个父节点。上图中A、B、C、D、H都是父节点。
兄弟节点:拥有共同父节点的子节点。上图中B、C、D是兄弟节点,E、F、G也是兄弟节点。
叶子节点:没有子节点的节点。或者说度为0的节点。上图中标绿的几个节点都是叶子节点。
内部节点:至少有一个子节点的节点。B、C、D、H都是内部节点。
边/分支:将一个父节点连接到其子节点的线。上图中的线就是边也称为分支。
后代(子孙):以某节点为根的子树中任一节点都称为该节点的后代。E、F、G是节点B的后代;H、K、L是节点C的后代,B-L的所有节点都是根节点A的后代。
祖先:从根到该节点所经分支上的所有节点。节点D是I、J的祖先;根节点A是所有节点的祖先。
路径:连接一个节点与其后代节点边的序列。A-B-E和A-C-H-K都可以称作一条路径。
路径长度:路径中边的数目。路径A-B-E的路径长度为2;路径A-C-H-K的路径长度为3。
节点的层次:从根节点定义,根节点为第1层,根节点的子节点为第2层,依次类推。节点的层在上图中已经标出。
深度(高度):叶子节点所在的最大层次。上图中树的深度为4。
森林:m棵不相交的树的集合。分别以B、C、D为根节点的子树组成的集合可以看做一个森林。
以上就是树结构的一些术语。
1.3 树的分类树结构可以分为两大类:有序树和无序树。树中任意节点间没有顺序关系,那么称其为无序树,也称自由树。相对的,树中的任意节点有顺序关系,称其为有序树。在有序树中,子节点被视为按照从左到右的顺序排列,最左边的子节点称为第一个子节点,最右边的子节点称为最后一个子节点。我们研究的最多的树结构就是有序树。而有序树中最具代表性的树结构就是二叉树。
二叉树就是度不超过2的有序树结构。 二叉树中的每个节点最多只能有两个分支,分别称为左子树和右子树。
根据二叉树的定义,会有如下两种极端的二叉树:
根据二叉树的形状,有以下几种常见的二叉树:
平衡二叉树:当且仅当任意节点的两棵子树的高度差不大于1的二叉树。
完全二叉树:除了最后一层外,其他层的节点数目都达到最大的二叉树。完全二叉树是平衡二叉树的一个特例,完全二叉树最后一层上的节点都是从左到右填充的。对于一颗k层的完全二叉树,其节点总数最少的情况是:最后一层只有一个节点,此时节点数目为:;其节点总数最多的情况是:最后一层节点数目达到最大,即满二叉树,此时节点数目为:。对于节点数目为k的完全二叉树,其深度为:
满二叉树:所有层的节点数目均达到最大的二叉树。满二叉树是完全二叉树的一个特例。对于深度为k的满二叉树,其节点数目是:;对于节点数目为k的满二叉树,其深度为:。
几种二叉树的结构图如下:
关于二叉树还有一个性质:二叉树中叶子节点数为(因为叶子节点的度为0,所以下标为0),度为2的节点数为 ,那么有: n0 = n2 + 1
解析:关于上面等式关系的求解我们可以这样考虑。假设二叉树的总节点数为,因为二叉树的节点度只有0、1、2三种情况,假设节点度为0、1、2的节点数分别为:n0、n1和n2。那么有n = n0 + n1 + n2。二叉树中节点度为1的节点有1条边连接到其子节点、节点度为2的节点有2条边连接到其子节点,假设二叉树有E条边,那么E = n1 + 2n2。而我们知道,在二叉树中节点总数和边的数目有这样的关系:n = E +1 = n1 + 2n2 + 1。联立加粗的两个等式,容易得出 n0 = n2 + 1。
上一篇:织梦dedecms栏目添加自定义字段,增加栏目上传缩略图功能(织梦专题页模板)
友情链接: 武汉网站建设