精华内容
下载资源
问答
  • 计算树高度

    千次阅读 2018-07-22 10:55:10
    那怎么计算树高度呢?我们可以分贝将左节点的高度计算出来和右 节点的高度计算出来,在比较大小。大的就是树的高度。   其实不管是求树的高度还是叶子节点个数,都是在遍历整个树,只不过在遍历的过程中满足了...

    树的高度就是数的层数。那怎么计算树的高度呢?我们可以分贝将左节点的高度计算出来和右

    节点的高度计算出来,在比较大小。大的就是树的高度。

     

    其实不管是求树的高度还是叶子节点个数,都是在遍历整个树,只不过在遍历的过程中满足了某种条件就做出一定的处理,所以树的遍历是最基本的。

    typedef struct BiTNode
    {
        int data;
        struct BiTNode* lchild, *rchild;
    }BiTNode;

    int Deepth(BiTNode *root)
    {
        int deepthleft = 0;
        int deepthright = 0;
        int deepcount = 0;
        if (root == NULL)
        {
            deepcount = 0;
            return deepcount;
        }
        //求左子树的高度
        deepthleft = Deepth(root->lchild);
        //求右子树的高度
        deepthright = Deepth(root->rchild);

       //每次都要加上根节点的高度

        deepcount = 1+ ((deepthleft > deepthright) ? deepthleft : deepthright);
        return deepcount;
    }

    void main()
    {
        BiTNode t1, t2, t3, t4, t5;
        memset(&t1, 0, sizeof(BiTNode));
        memset(&t2, 0, sizeof(BiTNode));
        memset(&t3, 0, sizeof(BiTNode));
        memset(&t4, 0, sizeof(BiTNode));
        memset(&t5, 0, sizeof(BiTNode));

        t1.data = 1;
        t2.data = 2;
        t3.data = 3;
        t4.data = 4;
        t5.data = 5;

        t1.lchild = &t2;
        t1.rchild = &t3;
        t2.rchild = &t4;
        t3.lchild = &t5;
        int deep=Deepth(&t1);
        printf("deep=%d ", Deepth(&t1));
        system("pause");
    }

    展开全文
  • 多叉的构建和高度计算

    千次阅读 2018-04-10 21:33:05
    题目描述现在有一棵合法的二叉树,的节点都是用数字表示,现在给定这棵上所有的父子关系,求这棵高度输入描述:输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成, 下面是n-1行,每行...

    题目描述

    现在有一棵合法的二叉树,树的节点都是用数字表示,现在给定这棵树上所有的父子关系,求这棵树的高度

    输入描述:

    输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,
    下面是n-1行,每行有两个整数,第一个数表示父节点的编号,第二个数表示子节点的编号

    输出描述:

    输出树的高度,为一个整数
    示例1

    输入

    5
    0 1
    0 2
    1 3
    1 4
    

    输出

    3

    /*
    题目有点小问题,测试用例存在多叉树但按照 AC 代码的意思要剔除这样的例子(-_-||
    但我总结了一下对于这种输入如何构建一个多叉树,以及找出最大高度的方法
    可能方法不是最好的,希望各位批评指正!! 
    对于题目中的输入
    0 1
    0 2
    1 3
    1 4
    左边是父节点,右边是子节点
    一个父亲可能有多个儿子,我这里用的是 map<int,queue<int> >来对应这种关系
    以父亲节点的值为 key, 所对应的一个队列queue<int>里放着他所有的儿子 
    这样就建立好了基本的对应关系,找出最大高度的方法类似于广度优先遍历
    一层一层向下迭代,详见代码 
    名词解释: 
    一个节点的高度:从该节点到一个树叶(没有儿子的节点)的最长距离 
    */
    #include<iostream>
    #include<map>
    #include<queue>
    #include<vector>
    #include<algorithm> 
    #include<string.h>
    using namespace std;
    map<int,queue<int> > G;//存储节点对应关系的 map 
    bool cmp(int a,int b)//自定义比较函数,对应sort的降序排列 
    {
    	return a>b;
    }
    /*
    获取最大高度的方法 
    */
    int getMax(int begin)		//函数传入的是根节点 
    {
    	if(G[begin].empty())
    	return 1; 		//这是递归结束条件,即遍历到树叶(没有儿子的节点)返回高度 1 
    	vector<int> v;		//一个节点有多个儿子,这是一个记录多个儿子高度的动态数组 
    	while(!G[begin].empty())		//把每一个儿子的高度放进vector 
    	{
    		int length = getMax(G[begin].front()) + 1;		//往下一层,高度 + 1 
    		v.push_back(length);		//儿子节点的高度放入vector 
    		G[begin].pop();		//注意pop()遍历过的节点 
    	}
    	//求动态数组的最值 ,作为该节点的最大高度并返回
    	sort(v.begin(),v.end(),cmp);//降序排序
    	return v[0]; //第一个即为最大值 
    } 
    int main()
    {
    	freopen("input.txt","r",stdin);
    	int a,b,n,begin;
    	int num[1001]={0};
    	while(~scanf("%d",&n))
    	{
    		//多叉图的构建 
    		for(int i=0;i<n-1;i++)
    		{
    			scanf("%d %d",&a,&b);
    			G[a].push(b);
    			num[b] = 1;		//散列思想,把所以儿子节点在数组 num里置 1,这样没被置 1的就是根节点 
    		}
    		//根节点的获取
    		//遍历 num数组,不是 1的就是根节点 
    		for(int i=0;i<n;i++)
    		{
    			if(num[i]==0)
    			{
    				begin = i;
    				break;
    			}
    		} 
    		//遍历树的最大高度
    		printf("%d\n",getMax(begin)); //放入根节点 
    		memset(num,0,sizeof(num));	//多组输入,初始化全局变量 
    		 
    	}
    
    	return 0;
    }

    展开全文
  • MYSQL的B+Tree索引树高度如何计算

    千次阅读 2020-04-24 08:35:37
    先给出一个千万级记录表的索引的高度大概在3-5 举例前先做一下举例时...由于索引每个节点的大小固定,所以索引KEY越小,B值就越大,那么每个BTREE节点上可以保存更多的索引KEY,也就是B值越大,索引高度就越...

     

    先给出一个千万级记录表的索引的高度大概在3-5

    举例前先做一下举例时用到的公式的一些维度的说明

    假设:

     表的记录数是N

     每一个BTREE节点平均有B个索引KEY

    那么B+TREE索引树的高度就是logNB(等价于logN/logB)

    由于索引树每个节点的大小固定,所以索引KEY越小,B值就越大,那么每个BTREE节点上可以保存更多的索引KEY,也就是B值越大,索引树的高度就越小,那么基于索引的查询的性能就越高。所以相同表记录数的情况下,索引KEY越小,索引树的高度就越小。

    现在我们假设表3000W条记录(因为2^25=33554432),如果每个节点保存64个索引KEY,那么索引的高度就是(log2^25)/log64≈ 25/6 ≈ 4.17

    通过上面的计算可知,要计一张表索引树的高度,只需要知道一个节点有多,从而就能知道每个节点能存储多少个索引KEY。现代数据库经过不断的探索和优化,并结合磁盘的预读特点,每个索引节点一般都是操作系统页的整数倍,操作系统页可通过命令得到该值得大小,且一般是4094,即4k。而InnoDB的pageSize可以通过命令得到,默认值是16k。

    以BIGINT为例,存储大小为8个字节。INT存储大小为4个字节(32位)。索引树上每个节点除了存储KEY,还需要存储指针。所以每个节点保存的KEY的数量为pagesize/(keysize+pointsize)(如果是B-TREE索引结构,则是pagesize/(keysize+datasize+pointsize))。

    假设平均指针大小是4个字节,那么索引树的每个节点可以存储16k/((8+4)*8)≈171。那么:一个拥有3000w数据,且主键是BIGINT类型的表的主键索引树的高度就是(log2^25)/log171 ≈ 25/7.4 ≈ 3.38。

    假设平均指针大小是8个字节,那么索引树的每个节点可以存储16k/((8+8)*8)≈128。那么:一个拥有3000w数据,且主键是BIGINT类型的表的主键索引树的高度就是(log2^25)/log128 ≈ 25/7 ≈ 3.57

    由上面的计算可知:一个千万量级,且存储引擎是MyISAM或者InnoDB的表,其索引树的高度在3~5之间

    展开全文
  • 高度计算

    千次阅读 2017-08-20 19:32:09
    //计算树的深度 { int H= 0 ; int HL= 0 ; int HR= 0 ; if ( NULL != T) { H++; HL=Heigh(T->LeftChild); //利用递归计算 HR = Heigh(T->RightChild); H += (HL >= HR ? HL : HR); } return...

    思路如下图所示:

    这里写图片描述
    采用递归的思路;黑色的是进入递归时变量的值,红色时返回时值;

    核心代码如下:

    typedef struct node BTree;
    typedef BTree* pBTree;
    
    struct node
    {
        pBTree Father;
        pBTree LeftChild;
        pBTree RightChild;
    };
    
    int Heigh(pBTree T)     //计算树的深度
    {
        int H=0;
        int HL=0;
        int HR=0;
        if (NULL != T)
        {
            H++;
            HL=Heigh(T->LeftChild);     //利用递归计算
            HR = Heigh(T->RightChild);
            H += (HL >= HR ? HL : HR);
        }
        return H;
    }
    展开全文
  • 不加 AND A.NAME = '数据库名称/表名称' 条件表示所有的库信息 1 B+高度则为 page_no+1 2 B+高度决定了要做多少次IO操作, 几千万行的高度有可能和几百万的高度一样 3 B+高度通常是1-3 4 primary ...
  • 关于的深度和高度计算

    万次阅读 2016-11-19 16:25:40
    关于的深度和高度计算,我看到两个不同的说法,它们的区别就在于到底是从0开始计算还是从1开始计算。(网上的和算法题偏向说法二,如果有能找到更加权威的解答望不吝赐教)说法一 《数据结构与算法分析:C语言...
  • #include using namespace std; struct Node { Node *lchild; Node *rchild; int d; }Tree[100]; int loc; Node *create() { Tree[loc].lchild = Tree[loc].rchild = NULL; return &Tree[loc++];...Node *in
  • #sicily#1003.计算二叉查找高度

    千次阅读 2016-12-30 11:31:30
    考点:用先序遍历和中序遍历查找二叉树的高度题意Description给定一个二叉查找,要求计算高度,每个二叉查找将给出先序与中序的遍历。例如:一个二叉查找其先序遍历为:16, 10, 4, 15, 23 ; 中序遍历为 4, ...
  • 中序遍历为 4, 10, 15, 16, 23,则其高度为2(假定空树高度为-1,只有根节点的数高度为0)Input第一行输入测试用例个数。对于每个测试用例,第一行是节点个数n,第二行是key值的先序遍历,第三行是key值的中序遍历
  • 数据结构树高度_树数据结构的高度

    千次阅读 2020-07-11 04:34:52
    数据结构树高度In this tutorial, we’ll be discussing Binary Trees. We’ll see how to calculate the height of a tree data structure recursively as well as iteratively. 在本教程中,我们将讨论二叉树。 ...
  • 对于一个高度为 h 的 AVL ,其最少结点数是多少?反之,对于一个有 n 个结点的 AVL , 其最大高度是多少 ? 最小高度是多少 ? (1)最少结点数: (2)最大高度: (3)最小高度: 平衡二叉树的...
  • 利用递归求下图的叶子结点数量以及的深度 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> //二叉树结点 typedef struct BINARYNODE { char ch; struct BINARYNODE* ...
  • =1,则对于任意一棵包含n个关键字、高度为h、阶数为m的B。 一、最小高度: 对于任意类型的数据结构,如果其每层节点能够分布的足够满,其高度也会随之变得足够的低。基于这个思路,对于B无外乎也是一种,B...
  • Android 计算软键盘高度(附源码和apk)
  • 求三叉树高度

    2014-10-10 15:32:26
    有12345个结点的满3叉数的高度为_____写出计算过程  1 层:1 节点数:1  / | \   2 3 
  • 高度与深度

    万次阅读 2017-04-10 23:07:42
    网上各种分析都是很乱的,造成很...1.可以看出两个概念定义是相互反向的,就跟我们数高楼从下往上,地下室深度从上往下,这里本来跟现实中的就是相反的,所以高度深度计算的方法也是相反。 2.一个数的高度与深度
  • 二叉树高度计算算法思悟

    千次阅读 2018-04-09 00:15:55
    二叉树高度计算算法思悟 总体来说,现在掌握的二叉树高度计算算法共有递归算法、基于后序遍历的算法、基于层次遍历的算法三种; github系列源码 递归算法实现 递归算法依旧格式优美、逻辑清晰、实现简单,便于...
  • 算法:这一类题目很简单,不过却是的最基本操作之一,引申为判断是不是平衡二叉树。一般做法是,计算二叉树的左右子树的高度+1,然后取它们的最大值或者最小值。题目1:https://lee...
  • 二叉树高度的三种计算方法

    万次阅读 多人点赞 2017-02-10 20:06:23
    计算二叉树的高度可以采用几种不同的算法。 算法一:采用后序遍历二叉树,结点最大栈长即为二叉树的高度; 算法二:层次遍历二叉树,最大层次即为二叉树的高度; 算法三:采用递归算法,求二叉树的高度。 /法1:...
  • 高度和深度

    千次阅读 2017-05-03 09:49:44
    用到的数据结构时,经常会考虑高度和深度,但是lz总是搞混了,总虽然比较简单,就是个定义,记住就行了,但是因为长时间总是弄错,所以写一篇博文,加深一下印象 1、的深度  的深度可以这样理解,计算一...
  • 例如,下面这棵高度是3: 计算二叉树高度有两种方法,一种是使用二叉树的层级遍历法,一种是使用递归法。 层级遍历法计算高度 我们可以使用二叉树的层级遍历法来计算二叉树的高度,这种方式的主要步骤是: ...
  • B最大高度推导

    千次阅读 2019-12-31 20:51:32
    文章目录B最大高度推导推导B的最小高度推导最大高度B+:MySQL数据库索引是如何实现的?1. 遇到问题2. 尝试用学过的数据结构解决这个问题3. 改造二叉查找4. 索引的弊端 B最大高度推导 【声明几个重要概念】...
  • 计算二叉树高度的三种方法

    万次阅读 2018-09-17 20:23:39
    思路:按后序遍历二叉树,节点最大栈长即为二叉树的高度。 public class Solution { public int TreeDepth(TreeNode root) { if(root==null){ return 0; } int height=0; Stack<TreeNode> nodes=...
  • 题目6.62 对以孩子-兄弟链表表示的树编写计算树的深度的算法。 将树拓展成森林,在森林上考虑此算法 森林转换成二叉树 可以看到,二叉树的根(A部分),左子树(B部分),右子树(C部分)分别对应森林的A,B,C三...
  • 二叉树高度、宽度计算

    千次阅读 2018-11-19 20:32:16
    二叉树高度可以采用迭代计算 public class TreeNode{ Data value; TreeNode left; TreeNode right; TreeNode(Data data,TreeNode left,TreeNode right) { this.data = data; this.left = left; this....
  • 理解结点的深度与高度

    千次阅读 2018-04-20 12:08:00
    一般情况的结点 n 计算  深度:从根结点到n结点的数值 高度:结点n到叶子结点最大路径数值 根据<<数据结构与算法分析:c语言描述>> 4.1章描述 因此可以看出:此描述计算高度和深度的基础数值从 ...
  • 二叉查找BinSearchTree:高的计算

    千次阅读 2020-01-13 16:17:41
    首先定义了计算树高的迭代函数getHeightRec(),它的参数是当前节点,函数从根节点进入,判断不是叶子节点后计算其左子树和右子树的树高,并返回其中高的那一个并加一(当前节点的一个树高),如此迭代,直到迭代到...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 92,808
精华内容 37,123
关键字:

计算树的高度