二叉树叶子节点与度为二的节点有什么关系?

论坛 期权论坛 期权     
js755351723   2018-4-26 14:01   14691   5
分享到 :
0 人收藏

5 个回复

倒序浏览
2#
热心网友  15级至尊 | 2018-4-30 01:55:03 发帖IP地址来自
结点:指二叉树中一个个的点,就是下图中的0、1、2、3、4、5、6;
度:指父结点下面有几个孩子结点,举两个例子你就明白了。针对结点1,他下面有两个孩子3、4,所以说结点1的度为2;针对结点4,他下面一个孩子都没有,所以说结点4的度为0;


置于遍历有一点点麻烦,但要抓住以下要点就可以了(不管任何大小的树):
前序:根结点第一个访问,然后访问左、右孩子;
后序:根结点最后访问,开始先访问左、右孩子;
中序:根结点第二个访问,最先访问左孩子,最后访问右孩子


以下图为例子:我把答案写给你看,你自己研究研究呢:
前序序列:0134256
后序序列:3415620
中序序列:3140526


聽 聽 聽 聽结点拥有的子树数;例如,A的度为3。
聽 聽 聽 常见的数据结构包括线性表、队列、栈、树等。

聽 聽 聽 树是n(n>0)个结点的有限集合(换句话说,树是由节点组成的)。当n=0时称为空树。在任一非空树中:①有且仅有一个称为该树之根的节点;②除根结点之外的其余节点可分为有限个互不相干的集合,且其中每一个集合本身又是一棵树,称为根的子树。这是一个递归定义,即在树的定义中又用到了树。树的定义显示了树的特性,即一棵树是由根结点和若干棵子树构成的,而子树又可由若干棵更小的子树构成。树中的每一个结点都是该树中某一棵子树的根结点。
聽 聽 聽 如图 A结点的度为3,B结点的度为2,c结点的度为1,D结点的度为3
聽 聽 聽 E、F、G、H、I 以及J度都为0,称为叶子结点.[1]聽


3#
2008hyc  3级会员 | 2018-4-30 01:55:04 发帖IP地址来自
叶子结点就是没有孩子的结点,其度为0,度为二的结点是指有两个子数的结点。比如一棵完全二叉树有三层,叶子结点就是最下面那一层的结点数,没有孩子结点,就是4,度为二的结点有3个。
4#
helio_true  1级新秀 | 2018-4-30 01:55:05 发帖IP地址来自
首先明白几个概念:结点所拥有的子树的个数称为该结点的度(Degree);树中各结点度的最大值称为该树的度;称度为m的树为m叉树。所以就简单了,也就是是这颗树每个节点最多承载2个子节点,或两个叶子。每多一个节点会多增加两个叶子,但是也会占用父节点的一个叶子空间。除根节点外。(这个话说起来有点绕,自己在纸上画画就明白了。) 这样就可以列出公式了: 叶子数=度*节点数-(节点数-1)
5#
zx_lxy0  4级常客 | 2018-4-30 01:55:06 发帖IP地址来自
设叶子节点为x个,度为2的节点的个数为y,则x=y+1
6#
huguangchaoren  2级吧友 | 2018-4-30 01:55:07 发帖IP地址来自
我们设度为0,1,2的节点分别为n0,n1,n2个,那么节点总数n=n0+n1+n2,然而边数b=n-1,并且b=n1+2*n2=n-1=n0+n1+n2-1,由此式我们可以推出n0=n2+1

也就是说叶子节点要比度为二的节点多一个。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP