二叉树节点计算法方法

1 1．．6 6 树与二叉树树与二叉树 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结 点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个 后件，称为该结点的子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度， 所有结 点中最大的度称为树的度。树的最大层次称为树的深度。 二叉树的特点：（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，则该结点为根结点，它没有父结点；若k1，则该结点的 父结点编号为 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）首先遍历左子树，然后访问遍历右子树，最 后访问根结点。 设一棵完全二叉树共有设一棵完全二叉树共有 700700 个结点，则该二叉树中有个结点，则该二叉树中有____________个叶子个叶子 结点？结点？ 最佳答案 假设 n0 是度为 0 的结点总数（即叶子结点数）， n1 是度为 1 的结点 总数，n2 是度为 2 的结点总数，由二叉树的性质可知：n0＝n2＋1， 则 n= n0＋n1＋n2（其中 n 为完全二叉树的结点总数），由上述公 式把 n2 消去得：n= 2n0+n1－1，由于完全二叉树中度为 1 的结点数 只有两种可能 0 或 1，由此得到 n0＝（n＋1）/2 或 n0＝n/2，合并 成一个公式：n0＝?（n＋1）/2 ?，就可根据完全二叉树的结点总数计 算出叶子结点数。 或者 根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为 n0,度 为 2 的结点数为 n2,则 no=n2+1. 根据完全二叉树的定义可得:在完全二叉树中度为 1 的结点 n1 只能取 两种情况,要么为 0,要么为 1. 所以:n0+n1+n2=700 n0=n2+1; 2n0=701-n1; 因为结点数为整数，所以 n1=1,no=350 或者 完全二叉树的定义：若设二叉树的高度为h，除第 h 层外，其它各 层 (1～h-1) 的结点数都达到最大个数， 第 h 层从右向左连续缺若干 结点，这就是完全二叉树。 可以算出，这棵二叉树共十层，1-9 层的节点个数为 2^9-1=511 个, 所以最后一层的节点个数为 700-511=189 个,189div2=95,那么倒数 第二层的叶结点个数即是 2^(9-1)-95=161 个 所以所有的叶结点个数即为:189+161=350 个 问问 1 1、、 深度为深度为 mm 的满二叉树有几个结点？的满二叉树有几个结点？ 2 2、设二叉树根结点的层次为、设二叉树根结点的层次为 0 0，对含有，对含有 100100 个根结点的二叉树，可个根结点的二叉树，可 能的最小树身为多少？怎么计算？能的最小树身为多少？怎么计算？ 最佳答案 1.深度为 m 的满二叉树有 2^m-1 个结点. 因为满二叉树的定义为:一颗深度为 k 且有 2^k-1 个结点的二叉树称 为满二叉树. 2.若要树深为最小,显然要使除最后一层外的每一层都有尽可能多的 结点,即要二叉树为完全二叉树. 由二叉树的一个重要性质:具有 n 个结点的完全二叉树的深度为 [log2n]+1.(这是在根节点层次为 1 时,若为 0,将+1 去掉即可) log2n 是以 2 为底 n 的对数 [log2n]为不大于 log2n 的最大整数 可知,含有 100 个(根)结点的二叉树,(应该没“根“字吧) 可能的最小树深为[log2 100 ]+1 二叉树根结点的层次为 0 时,可能的最小树深为[log2 100 ] 即为 6. 可以这样计算:确定最小树深当且仅当二叉树为完全二叉树时出现,设 深度为 k,(此时设二叉树根结点的层次为 0)有: 2^0+2^1+2^2+.+2^(k-1)100=2^0+2^1+.+2^k 即 2^k-1100=2^(k+1)-1 或 2^k=1002^(k+1)(上下两式是相等的) 其中 2^k 为完全二叉树的第 k 层的最多结点个数 解得 k=log2 100k+1 即 k=[log2 100]=6 某二叉树的前序遍历结点访问顺序是某二叉树的前序遍历结点访问顺序是 abdgcefhabdgcefh，中序遍历的结点访，中序遍历的结点访 问顺序是问顺序是 dgbaechfdgbaechf，则后序遍历的结点访问顺序是（，则后序遍历的结点访问顺序是（gdbehfcagdbehfca）） 这个答案是怎么算出来的？这个答案是怎么算出来的？ 最佳答案 首先我们知道，前序遍历的规则是：根结点→左子结点→右子结点 中序遍历是：左子结点→根结点→右子结点 后序遍历是：左子结点→右子结点→根结点 那么，对于一棵二叉树，前序遍历的第一个结点一定是这棵树的根结 点，即根结点是 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 / \