二叉树结点计算
2024-05-10 03:22
1. 二叉树结点计算
首先我们知道，前序遍历的规则是：根结点→左子结点→右子结点
中序遍历是：左子结点→根结点→右子结点
后序遍历是：左子结点→右子结点→根结点
那么，对于一棵二叉树，前序遍历的第一个结点一定是这棵树的根结点，即根结点是a。
在中序遍历的顺序dgbaechf中，以a分成左、右两边，左边是dgb，右边是echf。
所以，这棵树现在可以确定如下：
a
/ \
dgb echf
接下来再分别对左子树和右子树进行类似的操作。
对于左子树dgb来说，在前序遍历abdgcefh中找到bdg，证明这子树的根是b，那么现在可以确定的树结构如下：
a
/ \
b echf
/
dg
再看dg，前序遍历中的顺序为dg，所以d是dg这部分子树的根，那么又因为中序遍历的dg顺序也是dg，所以g是右子结点。
即：
a
/ \
b echf
/
d
\
g
现在看echf这部分子树，前序中顺序是cefh，所以子树根结点是c，那么左子结点是e，右子树是hf：
得到：
a
/ \
b c
/ / \
d e hf
\
g
最后只剩下hf部分了，前序遍历中是fh，所以根是f，那么h就是左子结点。
现在得到了整棵树：
a
/ \
b c
/ / \
d e f
\ /
g h
对这棵树再进行后序遍历就行了，结果就是：gdbehfca
求采纳为满意回答。
2. 树怎样转成二叉树？关于二叉树的公式有哪些？
树与二叉树 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。 二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 二叉树的基本性质： （1）在二叉树的第k层上，最多有2k-1(k≥1)个结点； （2）深度为m的二叉树最多有2m-1个结点； （3）度为0的结点（即叶子结点）总是比度为2的结点多一个； （4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分； （5）具有n个结点的完全二叉树的深度为[log2n]+1； （6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论： ①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)； ②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）； ③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。 满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。 完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。 二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。 二叉树的遍历： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树； （2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树； （3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
3. 二叉树结点的计算？？
首先我们知道，前序遍历的规则是：根结点→左子结点→右子结点
中序遍历是：左子结点→根结点→右子结点
后序遍历是：左子结点→右子结点→根结点
那么，对于一棵二叉树，前序遍历的第一个结点一定是这棵树的根结点，即根结点是a。
在中序遍历的顺序dgbaechf中，以a分成左、右两边，左边是dgb，右边是echf。
所以，这棵树现在可以确定如下：
a
/ \
dgb echf
接下来再分别对左子树和右子树进行类似的操作。
对于左子树dgb来说，在前序遍历abdgcefh中找到bdg，证明这子树的根是b，那么现在可以确定的树结构如下：
a
/ \
b echf
/
dg
再看dg，前序遍历中的顺序为dg，所以d是dg这部分子树的根，那么又因为中序遍历的dg顺序也是dg，所以g是右子结点。
即：
a
/ \
b echf
/
d
\
g
现在看echf这部分子树，前序中顺序是cefh，所以子树根结点是c，那么左子结点是e，右子树是hf：
得到：
a
/ \
b c
/ / \
d e hf
\
g
最后只剩下hf部分了，前序遍历中是fh，所以根是f，那么h就是左子结点。
现在得到了整棵树：
a
/ \
b c
/ / \
d e f
\ /
g h
对这棵树再进行后序遍历就行了，结果就是：gdbehfca
4. 二叉树结点计算
首先介绍二叉树的几个规则： 1. 二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：n=n0+n1+n2（式子1） 2. 1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2 3. 树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：n=n1+2n2+1 (式子2) 由式子1和式子2得到：no=n2+1 举例分析： 已知二叉树有11个结点，其中4个结点是有一个孩子，叶子有（4）个 计算过程: 已知n=11, n1=4, 代入公式如下： 11=4+2n2+1 n2=(11-4-1)/2=3 故叶子数量: n0=n2+1=3+1=4
5. 二叉树运算的介绍
二叉树运算，通常指对二叉树进行新建、删除、遍历查找等运算。是算法中最常见的基本类型之一。
6. 二叉树运算的基本运算
对于二叉树有下列基本运算：（1）建空二叉树Setnull（BT），置BT为空二叉树。（2）求二叉树的根root（x），求结点x所在二叉树的根。（3）求双亲结点parent（BT，x），在二叉树BT中求结点x的双亲结点。（4）求左或右孩子结点lchild（BT，x）或rchild（BT，x），在二叉树BT中求结点x的左孩子结点或右孩子结点。（5）插入左孩子或右孩子结点int_lchild(BT，x，y)或ins_child（BT，x，y），在二叉树中，将结点y置为结点x的左孩子或右孩子。（6）删除左孩子或右孩子结点del_lchild（BT，x）或del_rchild（BT，x），在二叉树中，删除结点x的左孩子或右孩子结点（实际上是删除x的左子树或右子树）。（7）遍历二叉树TRAVERSE（BT），即按某种次序，依次访问二叉树中每个结点，且每个结点只访问一次
7. 二叉树相关的一些知识及计算题
本人正在学习的过程中，若有不足或者错误，希望能够指出 希望我写的这些，能够帮到看到这篇文章的你 1、二叉树的深度（好多资料都喜欢设为k），也就是层数； 2、任意一棵树的总的节点数等于总分支数＋1； 3、叶子节点，也可以称为末级节点（即最底层的节点，度为0，度的值也就是分支数）； 4、一个深度为k的满二叉树的总结点数为2^k - 1（满二叉树指除叶子节点外每一个节点都有两个分支，即只有度为2和度为0的节点）; 5、深度为k的完全二叉树，最少有2^(k -1 )个节点，最多有2^k - 1个节点（即满二叉树，是特殊的完全二叉树）。 1、一颗二叉树第六层（即深度为6）的节点树最多为？ 答：二叉树每层的节点数最多为2^(k -1 )； 一般问最多，直接考虑为满二叉树，所以第六层为2^5 ＝ 32; 2、某二叉树中度为2的节点有18个，则该二叉树中有多少个叶子节点？ 答：首先需要知道两个公式： 总节点个数＝总分支数＋1 总结点个数＝度为2的节点数＋度为1的节点数＋度为0的节点数 然后就可以列等式了（数学真的是很厉害） 度为2的，分支数为节点数*2；度为1的，分支数为节点数*1；度为0的，分支数为节点数*0； 设度为2、1、0的节点数为n2、n1、n0，那么有n2 + n1 +n0 = n2 * 2 + n1 * 1 + n0 * 0 + 1 也就是一个公式n0 = n2 + 1，直接就出来了 结果：n0=19； 3、设一颗完全二叉树共有199个节点，那么该二叉树共有多少个分支节点？ 答：以第二题的节点进行假设： 分支节点数 ＝ n2 + n1，也就是总节点数n － 叶子总节点数n0； 进行一个假设，这个完全二叉树深度为k，也就是前k-1层为满二叉树，那么有： 2^(k-1) - 1 < 199 这个k值怎么取应该不用我再细说，得到k＝8；所以前7层的总的节点数为2^7 - 1 =127； 那么最后一层的叶子数为：总结点数 － 前7层的叶子总数 ＝ 199 － 127 ＝ 72； 第7层肯定是有叶子节点的（不然就是满二叉树了），第七层的叶子数 ＝ 第七层的叶子数 － 度为2以及度为1的节点数 ＝ 2^7 - 72/2 = 28; 所以这个完全二叉树的总叶子节点数为：28 ＋ 72 ＝ 100； 依据开头的公式，分支节点数 ＝ 总节点数 － 叶子总节点数 ＝ 199 － 100 ＝ 99； 4、在深度为7的二叉树中，最多有多少个叶子节点？ 答：先说答案，最多为满二叉树，也就是2^(7-1) ＝ 64； 5、设一颗完全二叉树共有127个节点，那么该二叉树是满二叉树吗？ 答：还是先设深度为k，那么假设它为满二叉树，看能否计算出k值（记住k可是整数啊）； 有公式2^k - 1 = 127 ，得k ＝ 7； 说明肯定是满二叉树。 6、具有53个节点的完全二叉树的深度为？ 答：惯例，设深度为k； 一般提到完全二叉树，先考虑前k - 1层，因为前k - 1层肯定是满二叉树，根据公式 2^(k-1) - 1 < 53 取最大的一个k值即可，得k＝6 7、设一颗完全二叉树共有700个节点，则在该二叉树中共有多少个叶子节点？ 答：来来来，国际惯例，设深度k 聪明的你，有没有发现其实和第三题算是一个题（一个是求分支节点，一个叶子节点，合起来不就是总节点数么） 我就直接列公式了：2^(k -1) - 1 < 700 取最大的一个k值，得k ＝ 10 就能够得到第10层的节点数也就是一部分叶子节点（因为第9层还有叶子节点）为：700 － 2^9 + 1 = 189； 第9层的叶子节点 ＝ 第9层节点总数 - 第9层度为2的节点和度为1的节点数 = 2^(9 - 1 ) - 188/2 -1 = 161； 所以这个二叉树中的总叶子节点数为：161 ＋ 189 ＝ 350 公式（上面的题要是都了解了，下满的公式也就不重要了，不然可能会让你混乱）： 这里先设值，二叉树的深度为k，二叉树的节点总数为n，度为2、1、0的节点数为n2、n1、n0，第k层的节点数nk 二叉树的节点总数n ＝ n2 + n1 + n0，n0 ＝ n2 + 1 总节点个数n = 总分支个数 ＋ 1 ＝ n2 * 2 + n1 * 1 + n0 * 0 + 1 二叉树为满二叉树：节点总数n = 2^k - 1，第k层的节点数nk ＝ 2^(k - 1 ) 第一次写，题目是自己在网上找的，但分析是自己分析的；有点乱，后续会把它精简，毕竟有一个从繁到简的过程； 分析的不知是否正确，若有错误，希望能够给我留言，我会及时改正的。
8. 二叉树结点计算方法
二叉树叶子结点计算方法： 1、结点的度是指，该结点的子树的个数，在二叉树中，不存在度大于2的结点。 2、计算公式：n0=n2+1，n0是叶子节点的个数，n2是度为2的结点的个数，n0=n2+1=5+1=6。 3、故二叉树有5个度为2的结点，则该二叉树中的叶子结点数为6。 叶子节点数=总结点数-度数非零的节点数（戒子节点度为0） 叶子结点是离散数学中的概念，一棵树当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”。 叶子是指出度为0的结点，又称为终端结点。 例：一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少？ 解：因为任一棵树中，结点总数=度数*该度数对应的结点数+1，所以： 总结点数=1*4+2*2+3*1+4*1+1=16 叶子结点数=16-4-2-1-1（总节点数－度不为0的个数）=8 则：n0=8 其中：n0表示叶子结点。
最新文章
热门文章
推荐阅读