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.根结点既有左子树又有右子树。