精华内容
下载资源
问答
  • 1、完全二叉树与满二叉树的区别: 满二叉树:深度为k且有2^k-1个结点的二叉树称为满二叉树。 完全二叉树:设二叉树的深度为h,除...计算完全二叉树深度公式-推导证明: 假设两种极端情况 <1>该树为满二叉树时...

    1、完全二叉树与满二叉树的区别:

    满二叉树:深度为k且有2^k-1个结点的二叉树称为满二叉树。 
    完全二叉树:设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边。

    2、计算二叉树的深度 : 

    满二叉树的深度为k=log2(n+1)
    在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。 

    计算完全二叉树深度公式-推导证明:
    假设两种极端情况
    <1>该树为满二叉树时,结点n1=2^k-1
    此时k=log2(n1+1)
    
    <2>当该树为满二叉树附加一个结点时,n2=2^(k-1),此时k=log2n2 +1,
    并且log2(n1+1)=log2n2 +1
    对任意结点n的完全二叉树,n2<=n<=n1
    2^(k-1)<=n<=2^k -1
    log2(n+1)<=k<=log2n +1
    则k向下取整log2n +1
    


     

    展开全文
  • 如何计算完全二叉树深度

    万次阅读 2017-09-22 19:46:52
    如何计算完全二叉树深度一棵有12个节点的完全二叉树,其深度是()一棵有12个节点的完全二叉树,其深度是() 4 5 3 6 在此之前我想说一下三种二叉树 Full Binary Tree Perfect Binary Tree Complete Binary Tree ...

    如何计算完全二叉树的深度

    一棵有12个节点的完全二叉树,其深度是()一棵有12个节点的完全二叉树,其深度是()

    • 4
    • 5
    • 3
    • 6

    在此之前我想说一下三种二叉树

    1. Full Binary Tree
    2. Perfect Binary Tree
    3. Complete Binary Tree

    为什么要说到这个问题,是因为在翻译的时候有个坑,特地想拿出来给大家说一下,Full Binary Tree翻译过来应该是满二叉树, 但是国内的满二叉树指的却是 Perfect Binary Tree。

    正文

    本篇博文旨在说明怎样计算完全二叉树的深度。

    证明:
    ​ 设该完全二叉树的深度为k,结点个数为12,根据完全二叉树的定义可知,前k-1层的结点个数为 2^(k-1) - 1个,由此可得

    12 > 2^(k-1)-1

    假设该完全二叉树恰好是一颗满二叉树(Perfect Binary Tree),则该树的结点个数为2^k - 1,由此可得

    2^k - 1 > 12 > 2^(k-1) - 1
    2^k > 13 > 2^(k-1)
    ∴ log2 13 < k < (og2 13) + 13 < k < 5

    因为k 只能为int ,所以取4

    答案选A

    由此可得完全二叉树的深度为log2 n ,其中n 为结点个数,取得下界

    展开全文
  • 二叉树深度计算 1、一颗树只有一个节点,它的深度是1; 2、二叉树的根节点只有左子树而没有右子树,那么可以判断,二叉树的深度应该是其左子树的深度加1; 3、二叉树的根节点只有右子树而没有左子树,那么可以判断...

    二叉树的深度计算
    1、一颗树只有一个节点,它的深度是1;

    2、二叉树的根节点只有左子树而没有右子树,那么可以判断,二叉树的深度应该是其左子树的深度加1;

    3、二叉树的根节点只有右子树而没有左子树,那么可以判断,那么二叉树的深度应该是其右树的深度加1;

    4、二叉树的根节点既有右子树又有左子树,那么可以判断,那么二叉树的深度应该是其左右子树的深度较大值加1。

    int TreeDeep(struct node *T)
    {
        int deep=0;
        if(T)
        {
            int ld=TreeDeep(T->l);
            int rd=TreeDeep(T->r);
            deep=ld>=rd?ld+1:rd+1;
        }
        return deep;
    }
    

    在这里插入图片描述
    满二叉树与完全二叉树
    一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树 。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。

    展开全文
  • 完全二叉树定义:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。...

    完全二叉树定义:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

    所以判断完全二叉树须满足两个条件:
    1所有叶子节点处的深度均为二叉树的深度
    2不存在只有右孩子而没有孩子的节点
    求深度即可,主要是递归有点绕
    递归一次,深度加一,返回一次,深度减一

    #include<iostream>
    using namespace std;
    #define  ElemType  char
     struct BiTree {
    	ElemType data;
    	 BiTree* Lchild, * Rchild;
    };
    void createBiTree(BiTree* &T)
    {
    	ElemType temp;
    	temp = getchar();
    	if (temp == '#')
    	{
    		T = NULL;
    	}
    	else
    	{
    		T = new BiTree;
    		T->data = temp;
    		createBiTree(T->Lchild);
    		createBiTree(T->Rchild);
    	}
    }
    void InOrder(BiTree* T)
    {
    	if (T)
    	{
    		InOrder(T->Lchild);
    		cout << T->data;
    		InOrder(T->Rchild);
    	}
    }
    void Deepth(BiTree* T,int& temp, int& n)
    {
    	if (T)
    	{
    		temp++;
    		Deepth(T->Lchild,temp,n);
    		Deepth(T->Rchild,temp,n);
    	}
    	else 
    	{
    		if (temp > n)
    			n = temp;
    		temp--;
    	}
    }
    void IsBest(BiTree* T, int &n, int &temp,bool &temp1)
    {
    	if (T)
    	{
    		temp++;
    		if (T->Lchild == NULL && T->Rchild!=NULL)
    			temp1 = false;
    		IsBest(T->Lchild, temp, n,temp1);
    		IsBest(T->Rchild, temp, n,temp1);
    	}
    	else
    	{
    		if (temp != n)
    			temp1 = false;
    		temp--;
    	}
    }
    int main()
    {
    	BiTree* T;
    	bool temp1=true;
    	T = NULL;
    	int temp, n;
    	temp = 0;
    	n = 0;
    	createBiTree(T);
    	InOrder(T);
    	Deepth(T, temp, n);
    	temp = 0;
    	cout << n;
    	IsBest(T, n, temp,temp1);
    	if (!temp1)
    		cout << "no";
    	else
    		cout << "yes";
    	return 0;
    }
    
    展开全文
  • 完全二叉树深度

    万次阅读 2019-09-25 20:00:59
    在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。 满二叉树的深度为k=log2(n+1) 证明: 假设两种极端情况 该树为满二叉树时,结点n1=2^k-1 此时k=log2(n1+1) 当该树为满...
  • 本系列文章将着重介绍一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树。希望各位读者能够关注专题,并给出相应意见,通过系列的学习做到心中有“树”。 二叉树...
  • 完全二叉树(Complete Binary Tree):若设二叉树的深度为h,除第h层外,其他各层(1~h-1)的节点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树完全二叉树由满二叉树而引起来的。对于...
  • 二叉树深度计算

    万次阅读 多人点赞 2019-03-10 15:45:36
    今天面试,被问到了二叉树深度计算问题。 一听到这个问题,第一反应是大学被写烂了的基本数据结构问题。 然而我已经毕业3年,没写算法很久,手都生了。但是呢,不能说生了就只对面试官说思路吧,于是还是...
  • 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。 ————来自维基...
  • 考虑1个叶子节点和0个叶子节点的极端情况: 故:
  • 求证:具有 n 个结点的完全二叉树深度为⌊log2n⌋+1 或⌈log2(n+1)⌉ 。 证明:设完全二叉树深度为h,则依据“深度为h的二叉树至多有2h-1个结点(h≥1)”的性质,可得:2^(h-1)-1≤ 2^h-1 其等价于 2^(h-1)≤ 2...
  • 给定一棵完全二叉树的根节点...1 找到完全二叉树的最左节点,也就是求左子树的深度 2 找到完全二叉树头节点右子树中的最左节点,记录右子树深度 3 如果两个深度相等,说明头节点左子树是一棵满二叉树,使用公式求...
  • 计算完全二叉树的树高

    千次阅读 2021-01-09 22:19:40
    计算完全二叉树的树高 思路: 要求在低于O(N)的时间复杂度内解决问题 由于任务是累加,每个递归中都是O(1),所以很自然地,树的节点统计必然也是至少和节点数量一样O(N) —— 至少要遍历一遍吧 但是完全二叉树,满...
  • 试写一个判别给定二叉树是否为完全二叉树的程序。 (1) 此二叉树以二叉链表作存储结构;
  • **完全二叉树:**对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树,其中满二叉树的定义是所有叶节点...
  • C++求二叉树深度的两种方法

    千次阅读 2020-03-17 20:44:07
    今天在leetcode中碰到了求二叉树深度问题,于是总结一下这两种方法 方法一是用递归的方法,方法二是借助队列和层序遍历的思想 #include<iostream> #include<queue> using namespace std; //构建...
  • 前序遍历和后序遍历的代码...二叉树深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回它的最大
  • 【算法】【python实现】二叉树深度、广度优先遍历 二叉树的遍历,分为深度优先遍历,以及广度优先遍历. 在深度优先遍历中,具体分为如下三种: 先序遍历:先访问根节点,再遍历左子树,再遍历右子树: 中序遍历:先遍历左...
  • 完全二叉树的定义 在完全二叉树中,除了最底层结点可能没填满外,其余每层结点数都达到最大值,并且最下面一层的结点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^h 个结点 预期结果 输入: ...
  • // 二叉树可以分为普通二叉树,搜索二叉树(排序二叉树),平衡二叉树,完全二叉树,满二叉树 // 搜索二叉树满足所有左子树的值都不大于根节点,所有右子树的值都不小于根节点,并且左右子树也都是搜索二叉树 // 平衡...
  • 二叉树深度 虽然前面已经做了二叉树深度,仍然不牢固。 剑指offer里面用的是递归的方法。只要的思路就是,左子树和右子树的比较,大的一支加1作为深度。并不是此时右子树的深度就不加一,现在考虑的是该节点的...
  • 二叉树的二叉链表的存储结构:typedef char TElemType;typedef struct BiTNode{TElemType data;//数据元素BiTNode * lchild;...一、二叉树深度如果二叉树为空,结点的深度为0;如果二叉树只有一个结点G为例,其...
  • 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。 PHP代码实现(暂时实现添加节点、层次遍历节点,删除节点后续更新) &...
  • 如何计算完全二叉树的结点数?

    千次阅读 2019-01-16 21:36:07
    如何计算完全二叉树的结点数?要求:时间复杂度低于O(n),即不能直接遍历二叉树。 答:从根节点开始,查看右子树的高度right_h与左子树的高度left_h的关系,如果right_h &lt; left_h 说明右子树一定是满二叉树...
  • 已知完全二叉树总结点数 N,求叶子结点数 n? 如果是偶数个节点,叶子节点等于总节点除以2, 即 N % 2==0, n = N/2 如果是奇数个叶子节点等于(总节点+1)除以2, 即 N % 2 == 1, n = (N+1)/2 即向上取整。 推导可...
  • 二叉树节点数和深度计算

    千次阅读 2020-11-24 22:49:28
    先来计算二叉树节点的个数,首先我们可以根据先序遍历或者中序遍历或者后序遍历的次数,使用一个计数器对节点的个数进行计数操作。这里使用的是先序非递归遍历来实现: int PreOrder(BtNode* ptr) { int sum = 0; ...
  • 二叉树深度计算,首先要判断节点,以下是计算二叉树的详细步骤: 1、一颗树只有一个节点,它的深度是1; 2、二叉树的根节点只有左子树而没有右子树,那么可以判断,二叉树的深度应该是其左子树的深度加1; 3、...
  • 二叉树叶子结点的计算二叉树叶子结点总数等于左子树的叶子结点 + 右子树的叶子结点, 判断是不是叶子结点 , 如果是返回1 ,如果不是叶子结点,继续递归。 线序计算二叉树结点个数: 首先定义一个全局变量...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,131
精华内容 16,452
关键字:

如何计算完全二叉树的深度