广州天河区网站设计公司,漳州做网站配博大钱少a,小网站下载渠道有哪些,模块网站需要多少钱树的定义
树是一种重要的非线性数据结构#xff0c;树作为一种逻辑结构#xff0c;同时也是一种分层结构。具有以下两个特点#xff1a;
1.树的根结点没有前驱#xff0c;除根结点意外的节点只有一个前驱
2.树中所有结点都可以有0个或多个后继
树结构在多个领域都有广泛…树的定义
树是一种重要的非线性数据结构树作为一种逻辑结构同时也是一种分层结构。具有以下两个特点
1.树的根结点没有前驱除根结点意外的节点只有一个前驱
2.树中所有结点都可以有0个或多个后继
树结构在多个领域都有广泛应用如表示文件系统的结构、数据库的索引、层次数据关系等。
具体来说树是由nn≥0个节点组成的有限集合。当n0时称为空树当n0时为非空树。在非空树中有且仅有一个特定的节点被称为根root其余节点可分为mm0个互不相交的有限集T1, T2, …, Tm其中每一个集合本身又是一棵树并且被称为根的子树Subtree。 树的基本术语 节点Node包含一个数据元素及若干指向其子树的分支。在树中每个节点都代表一个实体如文件系统中的文件或目录。 结点的度Degree of a Node一个节点拥有的子树数目。例如一个节点如果有两个子节点则它的度为2。 树的度Degree of a Tree树中所有节点度的最大值。这表示树中最“繁忙”的节点有多少个直接子节点。 叶子节点Leaf Node度为零的节点也称为终端节点。在树的最底层没有子节点的节点都是叶子节点。 分支节点Branch Node度大于零的节点也称为非终端节点。这些节点在树中起到连接其他节点的作用。 路径Path由从根节点到某一节点所经分支和节点构成的序列。 路径的长度是路径上边的数量。 孩子节点Child Node节点的子树的根称为该节点的孩子节点。例如在文件系统中一个目录下的文件和子目录都是该目录的孩子节点。 双亲节点Parent Node相应地一个节点的直接前驱节点称为该节点的双亲节点。在文件系统中一个目录的上级目录就是该目录的双亲节点。 兄弟节点Sibling Node具有同一父节点的各个节点彼此是兄弟节点。在文件系统中同一目录下的文件和子目录互为兄弟节点。 祖先节点Ancestor Node从根节点到某一节点路径上的所有节点都是这个节点的祖先节点。在文件系统中从根目录到某个文件或目录路径上的所有目录都是该文件或目录的祖先节点。 子孙节点Descendant Node以某节点为根的子树中任一节点都称为该节点的子孙节点。在文件系统中一个目录下的所有文件和子目录以及子目录的子目录等都是该目录的子孙节点。 节点的层次Level of a Node从根节点到该节点所经过的路径长度加1。根节点位于第1层。 树的深度Depth of a Tree树中叶子节点具有的最大层次数。这表示从根节点到最远叶子节点的最长路径上的节点数。 树的宽度Width of a Tree整棵树中某一层中最多的节点数。这表示树在该层上的“宽度”。 有序树Ordered Tree如果将树中节点的各子树看成从左至右是有次序的即不能互换则称该树为有序树。与之相对的是无序树其中子树的顺序不重要。
树的性质可以从多个方面来阐述以下是一些主要的性质
一、基本性质 递归定义树是n(n≥0)个节点的有限集合当n0时称为空树。在非空树中有且仅有一个特定的称为根的节点其余节点可分为m(m0)个互不相交的有限集合每个集合本身又是一棵树并称为根的子树。这种定义是递归的。 节点关系 根节点没有前驱节点除根节点外的所有节点有且只有一个前驱节点。树中所有节点可以有零个或多个后继节点即子节点。 层次结构树具有层级结构从根节点开始根节点为第一层根节点的子节点为第二层以此类推。节点的层次从根开始定义根节点为第1层有些教材从0开始。 路径与路径长度路径是由树中的两个节点之间的节点序列构成的而路径长度是路径上所经过的边的个数。
二、节点与树的属性 节点的度一个节点拥有的子树数目称为该节点的度。树中节点的最大度数称为树的度。 叶子节点与分支节点度为零的节点称为叶子节点终端节点度大于零的节点称为分支节点非终端节点。 节点的高度与深度节点的高度是从该节点到其最远叶子节点的最长路径上的节点数即从下往上数。节点的深度是从根节点到该节点的路径长度即从上往下数。树的高度深度是树中节点的最大层次数。
三、特殊树的性质 二叉树二叉树是每个节点最多有两个子树的树结构。二叉树具有一些特殊的性质如满二叉树、完全二叉树等。 m叉树
m叉树是每个节点最多有m个子树的树结构。对于高度为h的m叉树其节点数至多为(m^h - 1) / (m - 1)至少为h每层只有一个节点或hm-1只有一个分支节点有m个孩子。第i层至多有m^(i-1)个结点。
四、其他性质 结点数与度数关系树中的结点数等于所有节点的度数之和加1。这是因为每个非根节点都有一个前驱节点即其父节点而根节点没有前驱节点所以总度数加1就等于结点数。 有序树与无序树树中节点的各子树从左到右是有次序的不能交换称该树为有序树否则称为无序树。 森林m(m≥0)棵互不相交的树的集合称为森林。森林可以看作是由多棵树组成的集合。
最小高度分析
度为m具有n个结点的树的最小高度h 度为m具有n个结点的树的最大高度hn-m1
