精华内容
下载资源
问答
  • 数据结构:满二叉树,完全二叉树,非完全二叉树 的区别前言一、满二叉树二、完全二叉树三、非完全二叉树总结 前言 记录下满二叉树,完全二叉树,非完全二叉树的区别 一、满二叉树 如上图所示,这就是一个满二叉树...

    数据结构:满二叉树,完全二叉树,非完全二叉树 的区别


    前言

    记录下满二叉树,完全二叉树,非完全二叉树的区别


    一、满二叉树

    在这里插入图片描述
    如上图所示,这就是一个满二叉树的示例图,从字面上也很好理解,叶子节点外,所有节点都有两个子节点。

    二、完全二叉树

    在这里插入图片描述
    完全二叉树就和名字有点不太一样了,除最后一层节点外,其他层节点都必须要有两个子节点,并且最后一层节点都要左排列。
    要满足两个条件:

    1.除最后一层节点外,其他层节点都必须要有两个子节点
    2.最后一层节点都要左排列

    像下面这两种都不能称为完全二叉树
    中间层的节点没有满足两个子节点
    在这里插入图片描述
    最后一层节点没有左排列
    在这里插入图片描述

    三、非完全二叉树

    其实上面的没有满足完全二叉树的例子就可以称为非完全二叉树。


    总结

    欢迎大佬多多来给萌新指正,欢迎大家来共同探讨。
    如果各位看官觉得文章有点点帮助,跪求各位给点个“一键三连”,谢啦~

    声明一下:本博文章若非特殊注明皆为原创原文链接
    https://blog.csdn.net/Wrinkle2017/article/details/118728106
    ————————————————————————————————

    版权声明

    版权声明:本博客为非营利性个人原创
    所刊登的所有作品的著作权均为本人所拥有
    本人保留所有法定权利,违者必究!
    对于需要复制、转载、链接和传播博客文章或内容的
    请及时和本博主进行联系
    对于经本博主明确授权和许可使用文章及内容的
    使用时请注明文章或内容出处并注明网址
    转载请附上原文出处链接及本声明

    展开全文
  • 满二叉树 满足以下两个条件,缺一不可 1 所有分支结点都有左子树和右子树; 2 所有叶子结点在同一层上 如图所示,(a)图就是一棵满二叉树,(b)图则不是满二叉树... 完全二叉树与满二叉树的区别(有图)_Android_Ape-CS

    满二叉树

    满足以下两个条件,缺一不可

    1 所有分支结点都有左子树和右子树;
    2 所有叶子结点在同一层上
    

    如图所示,(a)图就是一棵满二叉树,(b)图则不是满二叉树,因为该二叉树的D,F,G,H,I叶子结点未在同一层上
    在这里插入图片描述

    完全二叉树

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

    b不是完全二叉树,因为B结点没有右子树
    在这里插入图片描述

    满二叉树和完全二叉树的应用

    待续

    参考

    完全二叉树与满二叉树的区别(有图)_Android_Ape-CSDN博客_完全二叉树

    展开全文
  • 二叉树:搜索二叉树和完全二叉树

    千次阅读 2017-05-02 22:34:07
    二叉树:搜索二叉树和完全二叉树

    搜索二叉树又叫作二叉树查找树或者二叉排序树,


    所谓搜索二叉树是指对于任何一个结点,它的左子树的所有结点都比这个根结点要小,它的右子树的所有结点都比这个根结点要大。注意是根结点与左右子树上所有的结点进行比较而不是仅仅与左右孩子结点进行比较,因此根据这个定义,那么当按照中序遍历来遍历一棵搜索二叉树时,必然是单调递增的,即是有序的序列,反之,如果一棵二叉树按照中序遍历得到的序列时有序的,那么这棵二叉树一定是搜索二叉树,因此对于搜索二叉树通常总是进行中序遍历的操作。

    红黑树、平衡搜索二叉树(AVL树)等其实都是搜索二叉树的不同实现,它们都努力使得搜索二叉树的搜索效率更高,调整代价更小。

    题目:判断一棵二叉树是否是搜索二叉树

    思路:根据定义检查在进行中序遍历时结点值是否递增即可,如果一旦出现减小,必然不是搜索二叉树。

    可以使用递归也可以不使用递归,当使用递归时注意,由于每次遍历到的结点需要与上一个结点进行比较,因此要保留上一个结点的值,因此在递归外面要设置一个成员变量temp(不能是局部变量)用来记住上一次遍历到的结点值,如果本次结点>=temp表示符合要求,再将temp替换为当前的值即可。并且,为了使得当遇到<temp的结点时停止,因此要设置一个falg变量作为标记符,每次判断当前值与temp时如果不符合要去就将falg设置为false,然后结束方法。

    package com.caicainiao.nowcoder;
    //主函数
    public class SearchBinaryTree {
    	public static void main(String[] args) {
    		TreeNode node1=new TreeNode(1);
    		TreeNode node2=new TreeNode(2);
    		TreeNode node3=new TreeNode(3);
    		TreeNode node4=new TreeNode(4);
    		TreeNode node5=new TreeNode(5);
    		TreeNode node6=new TreeNode(6);
    		TreeNode node7=new TreeNode(7);
    		node4.left=node2;
    		node4.right=node6;
    		node2.left=node1;
    		node2.right=node3;
    		node6.left=node5;
    		node6.right=node7;
    		new SearchBinaryTree().checkIsSearch(node4);
    	}
    	
    	//辅助变量:成员变量,所有递归栈共享
    	int temp;
    	boolean flag=true;
    	
    	//判断是否是搜索二叉树,中序遍历
    	public void checkIsSearch(TreeNode treeNode ){
    		temp=Integer.MIN_VALUE;
    		this.inOrderRecru(treeNode);
    		if(flag){
    			System.out.println("是搜索二叉树");
    		}else{
    			System.out.println("不是搜索二叉树");
    		}
    	}
    	
    	//中序遍历,同时判断是否递增
    	 private void inOrderRecru(TreeNode treeNode){
    		 //这是一个递归方法,要有结束的边界条件,当没有子节点时返回
    	        if(treeNode==null) return;
    	        //①先遍历子树的左子树
    	        this.inOrderRecru(treeNode.left);
    	        //②与前一个结点值比较
    	        if(treeNode.val<temp){
    	        	flag=false;
    	        	return;
    	        }
    	        temp=treeNode.val;
    	        //③遍历子树的右子树
    	        this.inOrderRecru(treeNode.right);
    	    }
    }

    满二叉树与完全二叉树

    所谓的满二叉树是指一棵二叉树中除了最后一层的结点没有任何子节点之外,剩下每一层上的结点都有2个子节点,即直观地看,满二叉树没有任何确实的结点。对于满二叉树,它的结点数目与层数存在直接的对应关系,如果层数为L,那么满二叉树的结点数目为N=2^L-1,反之L=log2(N+1)

     

    所谓完全二叉树是指除了最后一层之外,其他每一层的结点数目都是满的,如果最后一层也满了就是满二叉树,如果最后一层不满那么结点全部集中在左侧。满二叉树是一棵特殊的完全二叉树,对于完全二叉树这种特殊的结构,它可以使用数组来表示各个结点,此时每个结点与它的子节点的位置下标之间存在直接的对应关系,即从数组中i=1开始存放元素,于是对于某个结点i,它的左孩子下标是2*i,它的右孩子结点时2*i+1,它的父节点下标是i/2。堆(优先队列)就是一种完全二叉树结构。



    展开全文
  • 判断完全二叉树

    2018-01-03 17:52:51
    判断完全二叉树的充分必要条件 完全二叉树 深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中的编号为1~n的结点相对应,则这个二叉树为完全二叉树. 满二叉树 深度为k 且有...

    完全二叉树

    深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中的编号为1~n的结点相对应,则这个二叉树为完全二叉树.

    满二叉树

    深度为k 且有2^k-1个结点的二叉树. 结点的编号约定为:从根结点起从上至下,自左向右地顺序编号.

    判断完全二叉树的充分必要条件

    (1)如果一棵完全二叉树的深度为k,那么在第k-1层中的结点中,
    (a)一旦有一个结点的右孩子为空,则同层中后继编号结点的左右孩子都为空;
    (b)一旦有一个结点的左孩子为空,则该结点的右孩子,以及同层中后继编号结点的左右孩子都为空。

    (2)如果一棵完全二叉树的深度为k,则第1层~第k-2层的结点都必须既有左孩子又有右孩子,即第1层~第k-1层中的所有结点构成一棵满二叉树。

    程序如下:

    #inclue"stdio.h"
    
    typedef struct BiTNode{
      char data;
      struct BiTNode *lchild,*rchild;
     }BiTNode,BiTree;
    
    //创建一棵二叉树
    /*level1用来记录二叉树的深度,level2始终记录的是当前访问的结点在二叉树中的深度,由于level1是要返回的参数,作为justicBTree()的一个参数,所以要用指针传递的方法作为参数进行传递。*/
    
    CreatBiTree(BiTree *T,int *level1,int level2)
    { 
         char c;
         scanf("%c",&c);
         if(c==' ')  *T=NULL;
         else {
            *T=(BiTNode *)malloc(sizeof(BiTNode));
            (*T)->data=c;
            if(*level1<level2)  
            {
                 *level1=level2;
            }
          CreatBiTree(&((*T)->lchild),&(*level1),level2+1);
          CreatBiTree(&((*T)->rchild),&(*level1),level2+1);
     }
    
    
    /* 判断是否为完全二叉树*/
    /*是:返回1*/
    /*不是:返回0;*/
    /*T为根结点指针,level为当前访问的结点所在的层数,nk-1,其中k为二叉树的深度,flag为一个标志变量,用来记录第k-1层的结点的右孩子是否为空*/
    
    int justicCompleteBiTree(BiTree T,int level,int n,int flag)
    {
            if(!T) return 1;
            if(level==n)
            {
                  if(T->lchild==NULL&&T->rchild!=NULL)  return 0;
                  if(*flag==0)
                  {
                      if(T->lchild==NULL) *flag=1;
                  }
                  else if(*flag==1)
                  {
                      if(T->lchild!=NULL||T->rchild!=NULL)
                              return 0;
                  }
            }
    
          if(level!=n&&level!=n+1)
          {
                if(T->lchild==NULL||T->rchild==NULL)    return 0;
          }
          if(!justicCompleteBiTree(T->lchild,level+1,n,flag)) return 0;
          if(!justicCompleteBiTree(T->rchild,level+1,n,flag)) return 0;
          return 1;
    }
    
    
    main()
    {
       BiTree T;
       int flag=0;
       int level1=0;
    
       printf("Please type some character to creat a  binary tree\n ");
       CreatBiTree(&T,&level1,0);  //创建一棵二叉树,返回深度
       if(justicCompleteBiTree(T,0,level1-1,&flag))
              printf("It is a complete binary tree");
       else
              printf("It is not a complete binary tree");
       getche();
    }   
    展开全文
  • 树 树的定义 树的结点相关概念 二叉树 二叉树的定义 满二叉树 完全二叉树 二叉树的性质 完全二叉树的两个特性 二叉树的存储结构 遍历二叉树 Java实现
  • 给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入 {2,1,3} 返回值 [true,true] 备注: n≤500000n \leq 500000n≤500000 假设一个二叉搜索树具有...
  • 判断二叉树是否为完全二叉树 完全二叉树看起来就像是满二叉树右下角缺了一口。 思路: 需要引入一个标志位来区分两个阶段 1.先对该树进行层序遍历,会出现两种阶段 a):任何一个节点都有两颗子树 当遇到一个结点...
  • 完全二叉树是指除了最后一层之外,其他每一层的每个节点都是同时含有左右子树。当最后一层的每个节点也都含有左右子树的时候,则为满二叉树,同时也是完全二叉树。如果最后一层不满的时候,非满结点(即没有满足同时...
  • 1.判断一颗树是不是完全二叉树 思路解析 程序测试 2.完全二叉树应用
  • 首先,完全二叉树的含义就是从左到右依次排满一行再排一行,各节点之间都是相邻的。 判断他是否是完全二叉树, 分情况判断: ① 一个节点有右子树,但是没有左子树那么他一定不是完全二叉树 ② 一个节点的...
  • 如果没有 “完全二叉树” 这个条件,那么就用一般的,二叉树计算节点数的方法来做。考虑深度优先遍历,每一颗二叉树都可以由其根节点、左子树、右子树组成。考虑这个递归模式,从根节点开始计算,然后每一轮都带上该...
  • 判断一颗二叉树是否是完全二叉树

    千次阅读 2019-05-23 22:56:03
    判断一颗二叉树是否是完全二叉树 方法一,采取标记的方法 非完全二叉树的三种情况 思路分析: 通过层序遍历来遍历树中的每一个非空结点 遍历到的每一个结点都分为四种情况 1.既有左孩子也有右孩子 操作:将左...
  • /*判别二叉树T是否为完全二叉树*/ 定义:深度为k且含有n个结点的二叉树,如果其每个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应,则成为完全二叉树。 判断条件: 1. 左、右子树都是完全二叉树 2. ...
  • 建立完全二叉树

    千次阅读 2019-07-18 15:00:37
    完全二叉树 对于完全二叉树,按顺序1~n编号,若父节点为i;则左孩子为2i,右孩子为2i+1;若树深度为k,则前k-1为满二叉树;因此判定当2i<=n时,建立左子树,当2i+1<=n时,建立又子树 #include<iostream>...
  • 所以判断完全二叉树须满足两个条件: 1所有叶子节点处的深度均为二叉树的深度 2不存在只有右孩子而没有孩子的节点 求深度即可,主要是递归有点绕 递归一次,深度加一,返回一次,深度减一 #include<iostream> ...
  • 算法题—完全二叉树

    千次阅读 2019-05-04 19:00:14
    判断一棵二叉树是否为完全二叉树 完全二叉树 完全二叉树,即每一层都是要按从左往右,依此填满,最后一层可以不满,但是所有节点都集中在最左边,如图,图中1,2,3,4层节点的方向都是从左往右依此填充,每一层...
  • 完全二叉树概念:   完全二叉树是从满二叉树而来的,满二叉树即每一个节点都有两个子节点或者没有子节点。   完全二叉树是指若树的深度为 n,那么1 ~ (n-1) 层的节点都达到最大个数,即1 ~ (n-1) 层是满二叉树,...
  • 判断一个二叉树是否为完全二叉树

    万次阅读 多人点赞 2018-05-27 20:33:33
    完全二叉树 注意:完全二叉树与节点的标号没有关系 其中4号,5号,6号,7号节点为叶节点 判断完全二叉树 首先每个节点都会有以下4种情况: 情况一: 情况二:  情况三:  情况四:    我们...
  • 判断是否是完全二叉树 思路: 首先要明白,若一个结点有右孩子没有左孩子,则直接返回false。 若一个结点有左孩子没有右孩子,或者左右孩子都没有,则该结点后续所有结点都为叶结点才是完全二叉树。 public static ...
  • 1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树;...判别给定二叉树是否为完全二叉树。两个要求写了一份代码
  • 这里我们需要先明确什么是完全二叉树,以及普通二叉树和完全二叉树的区别。 我们先不考虑完全二叉树,而是按照普通二叉树的思路来全部遍历并统计。 这道题目的递归法和求二叉树的深度写法类似, 而迭代法,用层序...
  • 满二叉树和完全二叉树的概念 满二叉树:一个二叉树,如果每一个层的节点都达到了最大值,这个二叉树就是满二叉树。 完全二叉树: 1.对二叉树进行层序遍历 2.遍历过程中针对二叉树的判定分成两个阶段来看待 a)第一...
  • 本文介绍了判断一颗二叉树是不是平衡、完全、满二叉树,并给出C++代码。
  • 判断是否是完全二叉树(JAVA)

    千次阅读 2018-11-04 20:00:45
    判断一个树是否属于完全二叉树可以从以下2个条件来判断: -层次遍历二叉树 1 任何一个结点如果右孩子不为空,左孩子却是空,则一定不是完全二叉树 2 当一个结点出现右孩子为空时候,判断该结点的层次遍历后继...
  • 完全二叉树不要误以为是满二叉树 概念混淆: 一棵深度为k且有 2^k -1个结点的二叉树称为满二叉树。 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,则这棵二叉树称为完全二叉树...
  • 完全二叉树 完全二叉树:对于一个树高为h的二叉树,如果其第0层至第h-1层的节点都满。如果最下面一层节点不满,则所有的节点在左边的连续排列,空位都在右边。这样的二叉树就是一棵完全二叉树。 二 堆 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,030
精华内容 17,212
关键字:

完全二叉树条件