叉树节点计算法方法

1、16 树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0

2、的结点（即叶子结点）总是比度为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)；1 / 9若2kn，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；若2k+1n，则编号为k的结点的右子结点编号为2k+1；否则该结点无

3、右子结点。满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。设一棵完全二叉树共有700个结点，则该二叉树中有_个叶子结点？

4、最佳答案 假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0n21，则n= n0n1n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n11，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0（n1）/2或n0n/2，合并成一个公式：n0?（n1）/2 ?，就可根据完全二叉树的结点总数计算出叶子结点数。 或者 根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为n0,度为2的结点数为n2,则no=n2+1. 根据完全二叉树的定义可得:在完全二叉树中度为1的结点n1只能取两种情况,要么为0

5、,要么为1. 所以:n0+n1+n2=700 n0=n2+1; 2n0=701-n1; 因为结点数为整数，所以n1=1,no=350 或者 完全二叉树的定义：若设二叉树的高度为h，除第 h 层外，其它各层 (1h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。 可以算出，这棵二叉树共十层，1-9层的节点个数为29-1=511个,所以最后一层的节点个数为700-511=189个,189div2=95,那么倒数第二层的叶结点个数即是2(9-1)-95=161个 所以所有的叶结点个数即为:189+161=350个问1、 深度为m的满二叉树有几个结点？2、设二叉树根

6、结点的层次为0，对含有100个根结点的二叉树，可能的最小树身为多少？怎么计算？最佳答案 1.深度为m的满二叉树有2m-1个结点.因为满二叉树的定义为:一颗深度为k且有2k-1个结点的二叉树称为满二叉树.2.若要树深为最小,显然要使除最后一层外的每一层都有尽可能多的结点,即要二叉树为完全二叉树.由二叉树的一个重要性质:具有n个结点的完全二叉树的深度为log2n+1.(这是在根节点层次为1时,若为0,将+1去掉即可)log2n是以2为底n的对数log2n为不大于log2n的最大整数可知,含有100个(根)结点的二叉树,(应该没"根"字吧)可能的最小树深为log2 100 +1二

7、叉树根结点的层次为0时,可能的最小树深为log2 100 即为6.可以这样计算:确定最小树深当且仅当二叉树为完全二叉树时出现,设深度为k,(此时设二叉树根结点的层次为0)有:20+21+22+.+2(k-1)<100=<20+21+.+2k即2k-1<100=<2(k+1)-1或2k=<100<2(k+1) (上下两式是相等的)其中2k为完全二叉树的第k层的最多结点个数解得k=<log2 100<k+1即k=log2 100=6某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则后序遍历的结点访问顺序是（

8、gdbehfca） 这个答案是怎么算出来的？最佳答案 首先我们知道，前序遍历的规则是：根结点左子结点右子结点中序遍历是：左子结点根结点右子结点后序遍历是：左子结点右子结点根结点那么，对于一棵二叉树，前序遍历的第一个结点一定是这棵树的根结点，即根结点是a。在中序遍历的顺序dgbaechf中，以a分成左、右两边，左边是dgb，右边是echf。所以，这棵树现在可以确定如下：      a     / dgb echf接下来再分别对左子树和右子树进行类似的操作。对于左子树d

9、gb来说，在前序遍历abdgcefh中找到bdg，证明这子树的根是b，那么现在可以确定的树结构如下：    a   /   b  echf /dg再看dg，前序遍历中的顺序为dg，所以d是dg这部分子树的根，那么又因为中序遍历的dg顺序也是dg，所以g是右子结点。即：    a   /   b  echf /d  g现

10、在看echf这部分子树，前序中顺序是cefh，所以子树根结点是c，那么左子结点是e，右子树是hf：得到：    a   /   b  c /   / d  e hf  g最后只剩下hf部分了，前序遍历中是fh，所以根是f，那么h就是左子结点。现在得到了整棵树：    a   /  

11、0;b  c /   / d  e  f     / g  h对这棵树再进行后序遍历就行了，结果就是：gdbehfca设一棵完全二叉树共有500个结点，则在该二叉树中有_个叶子结点。我算得256 答案是250 不知道是多少，能给出过程吗？谢谢最佳答案 答案：250个叶子结点对一棵有n个结点的完全二杈树，其深度为2n+1，则对任一结点i（1in），如果2in，则其结点i为叶子结点，其叶子结点的个数为2i。不知

12、道这么解释你能明白否，不过这是个公式，你只要记住就好了。1、设一棵完全二叉树共有700个结点，求其叶子节点2、具有16个结点的完全二叉树的深度是多少？最好是能有详细解答过程，公式。多谢各位啦！最佳答案 根据“二叉树的第i层至多有2(i 1)个结点；深度为k的二叉树至多有2k 1个结点（根结点的深度为1）”这个性质：因为29-1 < 700 < 210-1 ,所以这个完全二叉树的深度是10，前9层是一个满二叉树，这样的话，前九层的结点就有29-1=511个；而第九层的结点数是2(9-1)=256所以第十层的叶子结点数是700-511=189个；现在来算第九层的叶子结点个数。由于第十层的叶子结点是从第九层延伸的，所以应该去掉第九层中还有子树的结点。因为第十层有189个，所以应该去掉第九层中的（189+1）/2=95个；所以，第九层