精华内容
下载资源
问答
  • 深度为k的完全二叉树最少的节点数!!!理解不到啊!求教!为什么是2的k-1 次方
  • 完全二叉树的深度

    千次阅读 2019-09-25 20:00:59
    二叉树的深度为k=log2(n+1) 证明: 假设两种极端情况 该树为满二叉树时,结点n1=2^k-1 此时k=log2(n1+1) 当该树为满二叉树附加一个结点时,n2=2^(k-1),此时k=log2n2 +1, 并且log2(n1+1)=log2n2 +1 对任意...

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

    证明:

    假设两种极端情况

    1. 该树为满二叉树时,结点n1=2^k-1

    此时k=log2(n1+1)

    1. 当该树为满二叉树附加一个结点时,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

     

    展开全文
  • 1、完全二叉树与满二叉树的区别: ...在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。 计算完全二叉树深度公式-推导证明: 假设两种极端情况 <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
    


     

    展开全文
  • 问题: 1.求二叉树叶子节点的个数 2.求二叉树深度 3.判断二叉树是否为完全二叉树 ...树的深度定义:树中所有节点的层次的最大值称为该树的深度,其中规定根节点的层次为0 ...深度为k的,有n个结点的二叉树, 当...
    • 问题:

    1.求二叉树叶子节点的个数

    2.求二叉树深度

    3.判断二叉树是否为完全二叉树

     

    • 预备知识:

    叶子:没有左右孩子的结点。

    树的深度定义:树中所有节点的层次的最大值称为该树的深度,其中规定根节点的层次为0 其他节点的层次为双亲节点层次+1。

    完全二叉树:对满二叉树的结点进行连续编号,约定编号从根结点起,自上而下,自左至右。深度为k的,有n个结点的二叉树,

    当且仅当其每一个结点都与深度为k的满二叉树编号从1至n的结点对应时,称为完全二叉树。

    满二叉树:一颗深度为k且有2^k-1个节点的二叉树称为满二叉树。

     

    • 思路:

    1.选取某种遍历方式遍历二叉树 判断当前访问的结点是否均没有左右子树,若均无,则计数器加一,直至遍历结束。

    2.递归方式求二叉树的深度,设置max为所求的最大深度

    递归出口:是否为叶子节点,若是回溯而且比较计数器与max值

    递归逻辑:每访问一个结点计数器加1

    递归调用:调用该函数

    3.层次遍历+队列

    若针对此二叉树

    下图中以#代表空

    最后判断队列是否全为空即可,若不为空,说明在空节点后还存在着非空节点,则不为完全二叉树。(理解完全二叉树的定义)

     

    #include<iostream>
    #include<string>
    #include<queue>
    using namespace std;
    int maxn = 0;//最大深度
    int leaf = 0;//叶子结点个数
    int sum = 0;//二叉树的节点个数
    typedef struct TNode {
        char data;
        TNode *leftchild, *rightchild;
        //构造函数
        TNode(char d):data(d),leftchild(NULL),rightchild(NULL){}
    //析构函数 };
    void CreateTree(TNode **T) { char st='0'; cin >> st; if (st== '#')*T = NULL; else { *T = new TNode(st); //构造根节点 CreateTree(&(*T)->leftchild);//构造左子树 CreateTree(&(*T)->rightchild);//构造右子树 } } void Pre(TNode *t)//先序遍历顺序 先根节点 再左子树 再右子树 { TNode *T = t; if (T != NULL) { if (T->leftchild == NULL&&T->rightchild == NULL)leaf++; sum++;//根节点 Pre(T->leftchild);//左子树 Pre(T->rightchild);//右子树 } }//count声明为全局变量 出现问题 因为命名空间std有一个count函数

    void Depth(TNode *t,int k) { TNode *T = t; if (T != NULL) { if (T->leftchild == NULL&&T->rightchild == NULL) { if (k > maxn)maxn = k; }//k值随着回溯会发生改变 Depth(T->leftchild,k+1); Depth(T->rightchild, k+1); } }
    bool Level(TNode *t) { /*利用层次遍历该树,遇到NULL停止遍历 ,若为完全二叉树,则此时队列中全为空指针*/ bool panduan=1; TNode *T = t; TNode *tem = NULL; queue<TNode *>q; q.push(T); tem = q.front(); q.pop(); while (tem != NULL) { q.push(tem->leftchild); q.push(tem->rightchild); tem = q.front(); q.pop(); } while (!q.empty()) { TNode *te; te = q.front(); q.pop(); if (te != NULL) { panduan = 0; break; } } return panduan; }
    
    

    int main()
    {
      TNode *t;
      //以先序遍历方式创建二叉树
      CreateTree(&t);

      Pre(t);
      cout << "叶子节点的个数:" <<leaf << endl;
      cout << "二叉树的结点个数:" << sum << endl;
      int k= 0;
      Depth(t,k);
      cout << "树的深度:" << maxn << endl;
      if (Level(t))cout << "该树为完全二叉树\n";
      else cout << "该树不是完全二叉树\n";

    
    

    }

     

     偶然间看到求二叉树深度更为简洁的递归方式

     

    转载于:https://www.cnblogs.com/zlspace/p/6803365.html

    展开全文
  • 若一棵深度为k的,有n个结点的二叉树,当且仅当其每一个点都与深度为k的满二叉树(2^k - 1 个结点)中编号为1到n的的结点一一对应时称之为完全二叉树。 也可以理解为:k-1层为满二叉树,k层所有叶子结点左边靠齐。 2....

    1.什么是完全二叉树
    对满二叉树的结点进行连续编号,约定编号从根结点起,自上而下,自左而右。

    若一棵深度为k的,有n个结点的二叉树,当且仅当其每一个点都与深度为k的满二叉树(2^k - 1 个结点)中编号为1到n的的结点一一对应时称之为完全二叉树。

    也可以理解为:k-1层为满二叉树,k层所有叶子结点左边靠齐。

    2.算法的实现
    在 c实现链式存储二叉树和层次遍历 的层次遍历

    若以NULL存储结点的左右子结点时树的描述如下

    例1:
    在这里插入图片描述

    该树为深度k为3的非完全二叉树,层次遍历为:1 2 3 4 NULL 6 NULL NULL NULL NULL NULL

    例2:在这里插入图片描述
    该树为深度k为3的完全二叉树,层次遍历为: 1 2 3 4 5 6 NULL NULL NULL NULL NULL NULL NULL

    这里我们假设若是从后往前看当不为空时,再继续往前看若无NULL,则为完全二叉树,反之则为非完全二叉树

    这只假设,所以问一问一颗完全二叉树为什么不为空的元素之前就一定无NULL呢

    完全二叉树的可以理解为:k-1层满二叉树的,第k层所有结点左靠齐,所以只有k层前有那层结点存在缺左或右或左右结点都缺的那么不空元素之前一定存在NULL。k层结点左靠其,若中间有NULL则说明k-1层有结点缺儿子。若为完全二叉树则:k-1层满二叉树的,第k层所有结点左靠齐,层次遍历不为NULL结点前无NULL,之后全为空。

    各种情况可以动手画画就知道了

    #1. 这里我们可以用栈存按储遍历结果(即BITreeNode指针,空指针即空结点)实现如算法1

    #2. 我们也可指针数组(BiTNode* node[MAX_SIZE])存储遍历结果,倒叙判断 实现如算法2

    算法1:

    Status IsCompleteBiTree(BiTree T){
    	printf("\n判断是否为完全二叉树");
    	SqQueueP sq;InitQueue(sq); //用于遍历使用的队列
    	SqStackP ss;InitStack(ss); //用于存储遍历结果的栈
    	EnQueue(sq, T);
    	while(!QueueEmpty(sq)){
    		BiTNode* temp = DeQueue(sq);
    		ss.Push(temp);
    		if(temp) {
    			printf(" %d ",temp->data);
    			EnQueue(sq, temp->lchird);
    			EnQueue(sq, temp->rchird);
    		}
    	}
        //判断不NULL元素前是否有NULL
        BiTNode* ptnode;
        while(1){
            ptnode=Pop(ss);
            if(ptnode) break;
        }
        while(1){
            ptnode=Pop(ss);
    	    if(!ptnode) return FALSE; 
        }
    	return TRUE;
    }
    

    算法2:

     
    Status IsCompleteBiTree(BiTree T){
    	printf("\n判断是否为完全二叉树");
    	SqQueueP sq;InitQueue(sq); //用于遍历使用的队列
    	BiTNode* node[MAX_SIZE];
    	EnQueue(sq, T);
    	int i = 0;
    	while(!QueueEmpty(sq)){
    		BiTNode* temp = DeQueue(sq);
    		node[i++] = temp;
    		if(temp) {
    			printf(" %d ",temp->data);
    			EnQueue(sq, temp->lchird);
    			EnQueue(sq, temp->rchird);
    		}
    	}
    	// 当前倒序判断指针存在后,之后的倒序判断若存在NULL则该树为不完全树
    	printf("\n判断结果(Yse or No) :");
    	int j = i-1;
    	for(; j >=0; j--){
    		if(node[j]) break;
    		else continue;
    	}
    	for(; j >= 0; j--){
    		if(node[j]) continue;
    		else{
    			printf("No");
    			return FALSE;
    		}
    	}
    	if(j==-1){
    		printf("Yse");
    	}
    	return TRUE;
    }
    
    展开全文
  • 定义补充: 完全二叉树:设二叉树深度为h,除第 h 层外,其它各层 (1~h-1) 结点数都达到最大个数, 第 h 层所有结点都连续集中在最左边 ...满二叉树:深度为k且有2^k-1个结点二叉树称为满二叉树...
  • 完全二叉树定义:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。...
  • 完全二叉树的结构

    2021-06-01 17:49:14
    深度为k,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时,称之为完全二叉树
  • 完全二叉树的定义

    2021-04-04 17:47:52
    深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。 从满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一...
  • 完全二叉树 满二叉树

    2020-05-03 23:59:36
    完全二叉树 满二叉树 1.定义 ①满二叉树:除最后一层无任何节点外,每一层上的所有节点都有两...②完全二叉树完全二叉树是效率很高的数据结构,对于深度为K的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中...
  • 1、完全二叉树是深度为k,有n个结点的二叉树,当且仅当其每一个结点,都与深度为k的满二叉树中编号从1至n的结点逐一对应的二叉树; 2、完全二叉树的叶子结点只可能在层次最大的两层上出现; 3、对任一结点,若其右...
  • 对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 算法思想 判断树是否是空树,若为空树则为完全二叉树 若树为非空完全二叉树,则...
  • 深度为K的完全二叉树,有2**n-1个节点 所以可以使用Python自带的math.log() 函数来求以2为底的二叉树的深度。 m为n个节点所对应的二叉树的深度。 m=(int(math.log(n+1,2))) import math n=int(input()) ls=list(map...
  • 完全二叉树叶子结点算法

    千次阅读 2013-12-20 16:10:01
    noip中经常会遇到求完全二叉树叶子结点的问题,比如第十一届全国青少年信息学奥林匹克联赛初赛试题的第四... 结论:如果一棵具有n个结点的深度为k的完全二叉树,其叶子结点数和总结点数有这样的关系:n(叶子)=(n总
  • 完全二叉树

    2020-01-12 17:33:19
    对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 (1)所有的叶结点都出现在第k层或k-l层(层次最大的两层) (2)对任一结...
  • 完全二叉树的判断

    千次阅读 多人点赞 2017-05-04 23:51:44
    完全二叉树(Complete Binary Tree...对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树。 注意:满二叉树一定是完全二叉树,但完全二叉
  • 对于深度为K的,有n个节点的二叉树,当且仅当每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时称之为完全二叉树。 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。 完全二叉树的特点...
  • 完全二叉树的判定

    2020-05-19 23:24:47
    对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 (1)所有的叶结点都出现在第k层或k-l层(层次最大的两层) (2)对任一结点,如果其右...
  • 完全二叉树(Complete Binary Tree):深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时,称为完全二叉树。 用了两个辅助方法,递归实现,C# codes as below: ...
  • 教科书中对完全二叉树的定义为: 对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 题目 给定一个二叉树的头节点head,判断一棵树...
  • 若一棵深度为k的,有n个结点的二叉树,当且仅当其每一个点都与深度为k的满二叉树(2^k - 1 个结点)中编号为1到n的的结点一一对应时称之为完全二叉树。 也可以理解为:k-1层为满二叉树,k层所有叶子结点左边靠齐。 2...
  • 完全二叉树的特点

    千次阅读 2017-08-01 02:14:31
    对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。一棵二叉树至多只有最下面的一层上的结点的度数可以小于2,并且最下层上的结点都集中...
  • 满二叉树 完全二叉树

    2018-03-20 16:54:00
    深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树编号 从1至n的结点对应时,称为完全二叉树。如图所示: 转载于:https://www.cnblogs.com/wll560/p/8610424.html...
  • 二叉树和完全二叉树的性质

    千次阅读 2019-04-17 11:21:30
    2.深度为k的二叉树至多有个结点(k>=1) 3.叶子结点数为,度为2的结点数为,则=+1。(证明:) 下面是完全二叉树的性质 特点:叶子结点在层次最大的两层出现;对于任意结点,右分支下的子孙的最大层次为k,左...
  • 完全二叉树与满二叉树区别

    万次阅读 多人点赞 2019-02-21 21:16:43
    满二叉树:指深度为k且有2^k-1个结点二叉树,如上图。   完全二叉树 完全二叉树:当二叉树深度为h时,它h层节点必须都是连续靠左并不可隔开(满二叉树也符合),并且1~h-1层结点数都达到最大个数(即...
  • 我们都知道满二叉树是分为国际标准和国内标准的,我们在这...深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树完全二叉树与满二叉树 ...
  • 对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 ...
  • 要判断一颗二叉树是否为完全二叉树,首先应该看一下完全二叉树的定义: 完全二叉树(来自数据结构课本定义):约定从根起,自上而下,自左而右,给满二叉树中每...深度为k且且含n个结点二叉树,如果其每个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 837
精华内容 334
关键字:

深度为k的完全二叉树