数据结构 二叉树

1. 数据结构 二叉树

m-n，根结点算在内。
二叉树的根结点是第一棵树的根结点，它的左子结点是第一棵树的最左子结点，右子结点是下一棵树（相当于兄弟结点）。一棵树对应的二叉树的根结点右子结点总是为空。

2. 数据结构 二叉树

答案是B，至少2h-1个。
二叉树的结构类似下图：

                                   o
                                /       \
                              o         o
                           /      \
                         o        o
                      /      \  
                   o         o

分析其结构，二叉树中只有度为0的结点和度为2的结点。对于最少结点的情况，除了第一层外，其余每层都一定是两个结点，结点总数是：
    1 + 2 * (h - 1) = 2h - 1

3. 数据结构二叉树

首先总的节点数=（2的k次）-1
因为（2的k-1次）-1=100  得到k=7  所以树的深度为7
根据公式 每一层有（2的k-1次）个节点  所以前6层分别有 1,2,4,8,16,32,加起来共有63个 
（用2的6次-1这种计算可以得到前6层的节点数）。那么剩下的第7层肯定有100-63=37个咯
因为是奇数 又是完全二叉树  故有单分支节点  1个
那么剩下的36个肯定上面一层的18个射出的分支咯
所以上面一层有叶子节点的个数为32-18=14
最下面一层有叶子节点37  加起来共有37+14=51个叶子节点啦

4. 数据结构二叉树

已知公式
1结点总数n=n0+n1+n2 
2 n0 = n2+1
得到n=2n0+n1-1
no = 70
n1 = 80
 
n = 219

5. 数据结构二叉树

楼主哥哥：
1.完全二叉树 就是 除了最后一层，上面都是满的！ 2的6次方 就是 64，64-1=63 余下的37个就是叶子节点啦。 就是计算 出一个小于100的 2的n次方-1，然后用100减它。

2.单分支就是用37/2 ，结果就是余数为1，说明有一个单分支

6. 数据结构之二叉树

  二叉树的分类    满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。   完全二叉树：除了最下面一层，其他层结点都是饱满的，并且最下层上的结点都集中在该层最左边的若干位置上。（满二叉树也是完全二叉树）   非完全二叉树：既不是满二叉树，也非完全二叉树。
                                            二叉树的遍历    前序遍历（先根遍历）：根左右。   后序遍历（后根遍历）：左右根。   中序遍历（中根遍历）：左跟右。   层次遍历：一层一层自左向右。
                                           图中前序遍历结果是：1,2,4,5,7,8,3,6；   图中中序遍历结果是：4,2,7,8,5,1,3,6；   图中后序遍历结果是：4,8,7,5,2,6,3,1；   图中层次遍历结果是：1,2,3,4,5,6,7,8；
    树和二叉树的转换    将树的孩子结点转成二叉树的左子结点，树的兄弟结点转成二叉树的右子结点。
                                            二叉树的一些重要特性    1、在二叉树的第i层上最多有2^(n-1)个结点（i>=1）；   例：   以图1为例：任一图中第2层，最多只能有2个结点。验证正确！   2、深度为k的二叉树最多有2^k - 1个结点（K>=1）；   例：   以图1为例：图中所有二叉树深度为3，因此，该些二叉树最多有2^3 -1 = 7个结点，验证正确！   3、对任何一颗二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1；   例：   以图1为例：看最后一个非完全二叉树，图中所示，叶子结点n0 = 2；度为2的结点n2 = 1(结点2)；则2 = 1 + 1。验证正确！   4、如果对一颗有n个结点的完全二叉树的结点按层序编号（从第1层到⌊log2n⌋ + 1层，每层从左到右），则对任一结点i(11，则父节点是⌊i/2⌋ ；   例：   以图1左侧的完全二叉树为例：若i = 3，则i > 1，⌊3/2⌋ = 1，3的根结点为1。验证正确！   如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i；   例：   以图1左侧的完全二叉树为例：若i = 3，因 n = 5，则2i>n，由此推出3为叶子结点。若i = 2，因 n = 5，则2in，则结点i无右子结点，否则，其右子结点是结点2i + 1。   例：   以图1左侧的完全二叉树为例：上一条否命题求出了左子树结点，而这条正好求出了右子树结点。结点i=2的右子树结点为5，验证正确！

7. 数据结构 - 二叉树

 一棵树可以没有任何节点称为 空树 ，可以只有一个节点root   一棵树可以分为多个子树组合，二叉树有左子树、右子树。    节点的度： 这个节点子树的个数。上图的节点1度为5，节点2的度为2。    树的度： 所有节点度中的最大值，上图的树的度为5    叶子节点： 度为0的节点    层数： 根节点在第一层，根节点的子节点在第二层。以此类推    节点的深度： 从根节点到当前节点的唯一路径上的节点总数，如图22的深度为3    节点的高度： 从当前节点到最远叶子节点的路径上的节点总数，如图22的高度为2    树的深度： 所有节点深度中的最大值，图中树的深度为4    树的高度： 所有节点高度中的最大值，图中树的高度为4
                                           特点：
   以下都是二叉树
                                           二叉树的特性：
                                            所有的节点度要不为0 要不为2    
                                           
    最后一层节点的度都为0，其他节点的度为2    
                                           
   假设满二叉树的高度为 h（h >= 1） ，那么
    对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应    
                                           
   下图不是完全二叉树
                                           完全二叉树的性质
   假设完全二叉树的高度为 h（h >= 1） ， 那么
    一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从  1  开始进行编号，对任意第 i 个节点    
                                           
    一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从  0  开始进行编号，对任意第 i 个节点    
                                           
   面试题：   如果一棵完全二叉树有 768 个节点，求叶子节点的个数？
   解题：384   假设叶子节点个数为 n0，度为 1 的节点个数为 n1，度为 2 的节点个数为 n2   总结点个数 n = n0 + n1 + n2，而且 n0 = n2 + 1   所以： n = 2n0 + n1 – 1 
   完全二叉树的 n1 要么为 0，要么为 1   n1为1时，n = 2n0，n 必然是偶数   叶子节点个数 n0 = n / 2，非叶子节点个数 n1 + n2 = n / 2   n1为0时，n = 2n0 – 1，n 必然是奇数   叶子节点个数 n0 = (n + 1) / 2，非叶子节点个数 n1 + n2 = (n – 1) / 2
   叶子节点个数  n0 = floor( (n + 1) / 2 )= ceiling( n / 2 )    非叶子节点个数  n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 ) 

8. 数据结构二叉树

二叉树的定义：二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。（在某个阶段都是两种结果的情形）
二叉树的特点有：
*每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
*左子树和右子树是有顺序的，次序不能任意颠倒。
*即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树具有五种基本形态：
1.空二叉树。
2.只有一个根结点。
3.根结点只有左子树。
4.根结点只有右子树。
5.根结点既有左子树又有右子树。