- 浏览: 61876 次
- 性别:
- 来自: 北京
最新评论
有12345个结点的满3叉数的高度为_____写出计算过程
1 层:1 节点数:1
/ | \
2 3 4 层:2 节点数:3
/ | \ / | \ / | \
5 6 7 8 9 10 11 12 13 层:3 节点数:9
满三叉树每层节点数目
假设k-1层有n个节点 那么第k层就应该有3n个节点。也就是说这是一个首项是1,公比是3的等比数列。第n层节点数an可以表示为
an=a1*q^(n-1) = 1*3(n-1) = 3^(n-1)
满三叉树总的节点数目
总的节点数目就是对各层节点数目求和,每层的节点数目计算公式已经有了。然后就是公比数列求和就行了。一个高位n的满三叉树总节点个数
sn = a1*(1-q^n)/(1-q) = 1*(1-3^n)/(1-3) = (3^n-1)/2
其实有了这个公式这题就可以做了,可以估计一下。求得一个n和n+1让12345在sn和sn'之间就行了。
下面给出一个较为严格的推导。
....
/.......\
(3^(k-1)-1)/2 层:k-1
/ \
(3^(k-1)+1)/2 (3^k-1)/2 层:k
设一个有n层的满三叉树的节点总数为n,那么
(3^(k-1)+1)/2 <= n <= (3^k-1)/2
3^(k-1)+1 <= 2n
3^k-1 >= 2n
k <= log3(2n - 1) - 1
k >= log3(2n + 1)
对k向下取整就行了。
1 层:1 节点数:1
/ | \
2 3 4 层:2 节点数:3
/ | \ / | \ / | \
5 6 7 8 9 10 11 12 13 层:3 节点数:9
满三叉树每层节点数目
假设k-1层有n个节点 那么第k层就应该有3n个节点。也就是说这是一个首项是1,公比是3的等比数列。第n层节点数an可以表示为
an=a1*q^(n-1) = 1*3(n-1) = 3^(n-1)
满三叉树总的节点数目
总的节点数目就是对各层节点数目求和,每层的节点数目计算公式已经有了。然后就是公比数列求和就行了。一个高位n的满三叉树总节点个数
sn = a1*(1-q^n)/(1-q) = 1*(1-3^n)/(1-3) = (3^n-1)/2
其实有了这个公式这题就可以做了,可以估计一下。求得一个n和n+1让12345在sn和sn'之间就行了。
下面给出一个较为严格的推导。
....
/.......\
(3^(k-1)-1)/2 层:k-1
/ \
(3^(k-1)+1)/2 (3^k-1)/2 层:k
设一个有n层的满三叉树的节点总数为n,那么
(3^(k-1)+1)/2 <= n <= (3^k-1)/2
3^(k-1)+1 <= 2n
3^k-1 >= 2n
k <= log3(2n - 1) - 1
k >= log3(2n + 1)
对k向下取整就行了。
发表评论
-
求链表中间节点的值,检测链表的环
2012-07-27 14:19 806求链表中间节点的值,检测链表的环 int loop(st ... -
实习前记
2012-07-16 15:27 696经过回来一周的找工作,总体感觉就是很累啊,每天东跑西颠的。面了 ... -
php函数参数列表
2012-05-11 16:50 1400[size=medium] 1.直接传值 function ... -
php的ob_flush和flush
2012-05-10 21:20 1069php.ini中 output_buffering = of ... -
php读文件的4中方法。
2012-05-10 20:38 871fopen $fp = fopen("downl ... -
百度笔试算法题一道。
2012-05-10 15:02 932一个数组a[0-n-1],a[0-mid]和a[mid+1-n ... -
自己实现php UTF8中文字符串截取
2012-05-09 11:38 2848header("Content-type: te ... -
C与C++动态分配,释放内存的区别
2012-05-08 17:30 160221. malloc()函数 1.1 malloc的 ... -
nginx rewrite
2012-05-04 11:23 0http://blog.cafeneko.info/2010/ ... -
php magic method
2012-05-04 11:16 859php的魔术方法总结 php的魔术方法都是和类有关的。 ... -
诡异的 shell 08 bug
2012-04-30 01:11 724v=08 echo $v shell里以0开头的都会把它当作8 ... -
排序相关
2012-04-22 16:01 0排序分类 内排序: 交换式排序: ... -
php string
2012-04-22 11:33 854一.字符串类型 php一共有8中数据类型 ... -
简单的树的递归、非递归创建,前序中序后序遍历
2012-04-21 10:03 1034c语言写着还挺带感 #in ... -
php 深度优先递归输出路径下所有文件
2012-04-19 21:27 1491<?php $dir = " ... -
简单的栈
2012-04-19 21:14 679#include <stdio.h> #de ... -
简单的循环队列
2012-04-19 21:13 780#include <stdlib.h> ... -
单链表删除一个节点
2012-04-19 21:10 9813有头结点的情况,附加一个逆置 #include <s ... -
KMP与BF,实现了一个非主流next函数
2012-04-19 20:16 899#include <stdlib.h> #i ... -
ip过滤问题
2012-03-22 21:09 0假设有很多段ip段属于教育网的,如何尽快辨别一用户ip是否属于 ...
相关推荐
通过复杂度对比与模拟实验结果表明:(1)相较其他有序数据机构,平衡三叉树具有较低的最坏高度;(2)平衡三叉树可以轻易实施区间操作;(3)平衡三叉树不需要对结构进行经常性的调整,平均内部路径长度远远小于...
【免费题库】华为OD机试 - 计算三叉搜索树的高度(Java & JS & Python & C & C++).html
【职业技能大赛计算机程序设计员赛项】理论试题及参考答案.pdf【职业技能大赛计算机程序设计员赛项】理论试题及参考答案.pdf【职业技能大赛计算机程序设计员赛项】理论试题及参考答案.pdf【职业技能大赛计算机程序...
数据结构源码C语言描述续,本篇描述了二叉树三叉链表结构及其操作,以及测试程序: //创建二叉树结点 TriTreeNode *CreateTriTreeNode(char data); //给二叉树添加结点,用于创建二叉树 int AddTriTreeNode(char ...
数据结构题库+答案 1. 在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为( )个...3. 假定一棵三叉树的结点数为50,则它的最小高度为( )。 A. 3 B. 4 C. 5 D. 6
此时采用三叉树链表储存二叉树。 其中,data,lchild,rchild三个域的含义同二叉树,parent域为指向该结点的双亲结点指针。 5.4.4 线索链表 按照某种遍历次序对二叉树进行遍历,可以把二叉树中所有结点排成一个线性...
题目: 41.家族关系查询 建立家族关系数据库,实现对家族成员关闭的相关查询 设计要求: (1)建立家族关系并能存储到... (4)该家族树宽度至少5,高度至少5 数据结构: 树状采用三叉链表实现,队列采用链式队列
三叉树,对应不喜欢、一般般喜欢和喜欢三个节点 生成的节点信息用self.tree和self.node_interval两个变量保存 构建预测模型: 利用Spark的mllib包实现ALS Matrix Factorization 生成伪物品(每个节点)和用户对应的...
三叉树,对应不喜欢、一般般喜欢和喜欢三个节点 生成的节点信息用self.tree和self.node_interval两个变量保存 构建预测模型: 利用Spark的mllib包实现ALS Matrix Factorization 生成伪物品(每个节点)和用户对应的...
输入一组关键字序列,并以此顺序建立一棵平衡二叉树(提示:为简化运算,可采用含有左、右子树高度和指向父母的指针的三叉链表表示),并在建树过程中用逆中序法输出每次插入新结点后的平衡二叉树形状。
输入一组关键字序列,并以此顺序建立一棵平衡二叉树(提示:为简化运算,可采用含有左、右子树高度和指向父母的指针的三叉链表表示),并在建树过程中用逆中序法输出每次插入新结点后的平衡二叉树形状。
e. 如有可能,请建立一个存储商品名称和数量的文本文件,并为二叉搜索树建立一个成员函数SetupInventory(),用于从该文本文件中读取库存商品的数据, 实验报告要求: 1、 按要求记录下二叉搜索树的完整实验...