设为首页 - 加入收藏
广告 1000x90
您的当前位置:78345黄大仙救世网挂牌 > 结点 > 正文

什么是树的节点

来源:未知 编辑:admin 时间:2019-06-30

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  每片树叶都长在一个结点上,这个结点就叫做这个叶子的父结点,这个叶子叫做你结点的子结点,也叫这棵树的叶结点,它再没有子结点了。

  而叶子的父结点一定还会有上面的父结点,这样一级一级上去就到了根结点,它就像是树的根,它上面再没有“叉儿”了。

  树状图是一种数据结构,它是由n(n=0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

  它具有以下的特点:每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树;

  每片树叶都长在一个结点上,这个结点就叫做这个叶子的父结点,这个叶子叫做你结点的子结点,也叫这棵树的叶结点,它再没有子结点了。而叶子的父结点一定还会有上面的父结点,这样一级一级上去就到了根结点,它就像是树的根,它上面再没有“叉儿”了

  树状图是一种数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树。

  是数据结构中,用来描述“树”型结构的名词。这种结构像一根倒着的树。每片树叶都长在一个结点上,这个结点就叫做这个叶子的父结点,这个叶子叫做你结点的子结点,也叫这棵树的叶结点,它再没有子结点了。

  而叶子的父结点一定还会有上面的父结点,这样一级一级上去就到了根结点,它就像是树的根,它上面再没有“叉儿”了。

  节点的度:一个节点含有的子树的个数称为该节点的度;叶节点或终端节点:度为0的节点称为叶节点;非终端节点或分支节点:度不为0的节点;双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;

  孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;兄弟节点:具有相同父节点的节点互称为兄弟节点;树的度:一棵树中,最大的节点的度称为树的度;节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

  树的高度或深度:树中节点的最大层次;堂兄弟节点:双亲在同一层的节点互为堂兄弟;节点的祖先:从根到该节点所经分支上的所有节点;子孙:以某节点为根的子树中任一节点都称为该节点的子孙。森林:由m(m=0)棵互不相交的树的集合称为森林;

  如上图所示为一个二叉树,其中A为父节点,B、C为A的子节点,B和C为兄弟节点

  每片树叶都长在一个结点上,这个结点就叫做这个叶子的父结点,这个叶子叫做你结点的子结点,也叫这棵树的叶结点,它再没有子结点了。而叶子的父结点一定还会有上面的父结点,这样一级一级上去就到了根结点,它就像是树的根,它上面再没有“叉儿”了

  一个结点的儿子结点的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。

  树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。例如在图1中,结点A,B和E的度分别为3,2,0。其中A为根结点,B为内部结点,E为叶结点,树的度为3。

  如果存在树中的一个结点序列K1,K2,..,Kj,使得结点Ki是结点Ki+1的父结点(1≤i≤j),则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。我们称这条路径的长度为j-1,它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。例如,在图1中,结点A到结点I有一条路径ABFI,它的长度为3。

  如果在树中存在一条从结点K到结点M的路径,则称结点K是结点M的祖先,也称结点M是结点K的子孙或后裔。例如在图1中,结点F的祖先有A,B和F自己,而它的子孙包括它自己和I,J。注意,任一结点既是它自己的祖先也是它自己的子孙。

  我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中,树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。

  树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。例如图1中的结点B,C和D的高度分别为2,0和1,而树的高度与结点A的高度相同为3。

  从树根到任一结点n有唯一的一条路径,我们称这条路径的长度为结点n的深度或层数。根结点的深度为0,其余结点的深度为其父结点的深度加1。深度相同的结点属于同一层。例如,在图1中,结点A的深度为0;结点B,C和D的深度为1;结点E,F,G,H的深度为2;结点I和J的深度为3。在树的第二层的结点有E,F,J和H,树的第0层只有一个根结点A。

  树的定义在某些结点之间确定了父子关系,我们又将这种关系延拓为祖先子孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序,则得到一棵有序树;否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为n1,n2,..,nk,则我们称n1是n的最左儿子,或简称左儿子,并称ni是ni-1的右邻兄弟,或简称右兄弟(i=2,3,..k)。图2中的两棵树作为无序树是相同的,但作为有序树是不同的,因为结点a的两个儿子在两棵树中的左右次序是不同的。后面,我们只关心有序树,因为无序树总可能转化为有序树加以研究。图2 两棵不同的有序树我们还可以将兄弟结点之间的左右次序关系加以延拓:如果a与b是兄弟,并且a在b的左边,则认为a的任一子孙都在b的任一子孙的左边。

  森林是m(m0)棵互不相交的树的集合。如果我们删去一棵树的树根,留下的子树就构成了一个森林。当我们删去的是一棵有序树的树根时,留下的子树也是有序的,这些树组成一个树表。在这种情况下,称这些树组成的森林为有序森林或果园。

本文链接:http://anicburst.com/jiedian/394.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top