精华内容
下载资源
问答
  • 严格二叉树,这个定义就百度上有,维基百科都没查到。 严格二叉树定义:如果一颗二叉树的每个非终端节点都有且仅有两棵子树,则称这颗二叉树为严格二叉树。摘自百度百科。 简单的说,没有度为1的结点的二叉树,被...

    严格二叉树,这个定义就百度上有,维基百科都没查到。

    严格二叉树的定义:如果一颗二叉树的每个非终端节点都有且仅有两棵子树,则称这颗二叉树为严格二叉树。摘自百度百科。

    简单的说,没有度为1的结点的二叉树,被称之为严格二叉树。如下图就是一颗严格二叉树。

    clipboard

    下图就不是一棵严格二叉树,因为结点5,9的度数都是1.

    192px-Binary_tree.svg

    首先证明一个问题,对于有n个叶子的严格二叉树,必定有n-1个非叶子节点。即严格二叉树中,度数为0的叶子节点有n个,那么度数为2的节点数必定为n-1个。不论树的形态是怎样。

    用数学归纳法证明。

    对于只有2个叶子的严格二叉树,那只有1个根结点。

    如下图:

    clipboard[1]

    假设有k个叶子的严格二叉树有k-1个非叶子节点,那么对k+1个叶子节点的严格二叉树,

    就相当于在k个叶子的严格二叉树上再扩展加一个叶子。如下图是一个有着k个叶子节点的严格二叉树

    clipboard[2]

    要在上面的树上多出一个叶子节点,并且使之仍然是一颗严格二叉树,只能在任意一个叶子节点增加2个叶子节点,这样操作,会,减去原先的一个叶子节点,同时会多出一个非叶子节点。也就是说,总的来说会多一个叶子节点和一个非叶子节点。即原来的k个节点的严格二叉树,有k-1个非叶子节点。而k+1个节点的严格二叉树,会有k个非叶子节点。

    clipboard[3]

    因此对于k+1,也成立。

    因此采用数学归纳法得到证明。\












    本文转自cnn23711151CTO博客,原文链接:http://blog.51cto.com/cnn237111/1051946,如需转载请自行联系原作者




    展开全文
  • 二叉树相关定义

    2016-08-24 12:21:37
    二叉树的相关类型术语并不是严格统一和规范的,不同的文献描述略有不同 [术语] 1.根二叉树(Rooted Binary Tree): 有一个根结点,每个结点至多有两个孩子。 2.满二叉树(Full Binary Tree): 要么是叶子结点(结点的度...

    二叉树的相关类型术语并不是严格统一和规范的,不同的文献描述略有不同
    [术语]
    1.根二叉树(Rooted Binary Tree):
    有一个根结点,每个结点至多有两个孩子。
    2.满二叉树(Full Binary Tree):
    要么是叶子结点(结点的度为0),要么结点同时具有左右子树(结点的度为2)。
    3.完全二叉树(Complete Binary Tree):
    每层结点都完全填满,在最后一层上如果不是满的,则只缺少右边的若干结点。
    4.完美二叉树(Perfect Binary Tree)
    所有的非叶子结点都有两个孩子,所有的叶子结点都在同一层。即每层结点都完全填满。
    5.无限完全二叉树(Infinite Complete Binary Tree):
    每个结点都有两个孩子,结点的层数是无限的。
    6.平衡二叉树(Balanced Binary Tree):
    也称为AVL树,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    [个人理解]
    1.可能由于计算机理论研究的发展,导致相关的术语随之而演化和变迁,目前并没有严格统一的描述,而国内的教材基本都是翻译自国外的资料,所以会出现不同的说法,类似的情况可能还有树的深度的定义,有的根结点从0开始计数,有的从1开始计数。
    2.国内早期教材中,满二叉树一般指 perfect binary tree,所以会有满二叉树是完全二叉树的一个特例的说法。
    3.下面这四种情况都有可能出现,具体可参考罗晟资料
    ·既是Full Binary Tree 又是 Complete Binary Tree
    ·既不是 Bull Binary Tree 又不是 Complete Binary Tree
    ·是 Full Binary Tree 不是 Complete Binary Tree
    ·不是 Full Binary Tree 是 Complete Binary Tree


    图片转自(http://courses.cs.vt.edu/~cs3114/Spring10/Notes/T03a.BinaryTreeTheorems.pdf,应该是Computer Science at Virginia Tech的课件

    文章转自知乎为什么说“满二叉树也是完全二叉树”?


    展开全文
  • 二叉树的基本定义

    2018-10-24 21:27:33
    一、二叉树的递归定义 1.要么二叉树没有根节点,是一颗空树。...而二叉树其左右子树是严格区分的,不能随意交换左子树和右子树位置。 二、二叉树的存储结构 此处二叉树用链表来定义。(对链表不太熟悉的...

    一、二叉树的递归定义

    1.要么二叉树没有根节点,是一颗空树。

    2.要么二叉树由根节点,左子树和右子树组成,且左子树和右子树都是二叉树。

    请注意二叉树与度为2的树的区别:对树来说,结点的子树是不区分左右顺序的。度为2的树只能说明树中所有结点的子结点个数不超过2。而二叉树其左右子树是严格区分的,不能随意交换左子树和右子树位置。

    二、二叉树的存储结构

    此处二叉树用链表来定义。(对链表不太熟悉的可用数组定义二叉树的静态实现)

    struct node{
    int data;    //数据域,可以是任意类型
    node* lchild;    //指向左子树根节点的指针
    node* rchild;    //指向右子树根节点的指针
    };

    在二叉树建树前根节点不存在,其地址一般为NULL

    node* root=NULL;

    新建一个结点:

    node* newNode(int val){
    node* Node=new node;
    Node->data=val;
    Node->rchild=NULL;    //一定要将新创建的结点其左右子树至为NULL,表示无左右子树
    Node->lchild=NULL;
    return Node;
    }
    

    三、二叉树的常用操作

    1、查找。在二叉树中找到所有数据域为给定数据域的结点,并将它们的数据域修改为给定的数据域。

    void search(node* root,int x,int newdata){
        if(root==NULL){    //递归边界,当前结点为空。
            return ;
        }
        if(root->data==x){    //找到该结点。
            root->data=newdata;
        }
        search(root->rchild,int x,int newdata);  //依次向右子树,左子树进行搜索。
        search(root->lchild,int x,int newdata);
    
    }

    2、插入。结点的插入位置取决于数据域需要在二叉树中存放的位置。(例如二叉查找树就要根据插入的数据域跟当前的结点比较大小。)但数据域要插入的地方就是在二叉树中查找失败的位置,此位置确定。

    void insert(node* &root,int x){    //注意此处应是引用该树,负责插入不会成功。
        if(root==NULL){    //若该树为一棵空树,插入结点为根节点。
            root=newNode(x);
            return;
        }
        if(x应该插在左子树的条件成立){
            insert(root->lchild,int x);   
        }else{
            insert(root->rchild,int x);
        }
    ]

    3、创建二叉树。创建过程也就是数据一个个插入的过程。

    node* create(int data[],int n){
        node* root=NULL;    //创建根结点root
        for(int i=0;i<n;++i){
            insert(root,data[i]);
        }
    return root;    // 返回整个创建好的树。
    }

    4、特殊二叉树的存储。

    对完全二叉树而言,假设根结点编号为x,其左子树结点编号肯定为2*x,右子树结点编号为2*x+1,并且其根节点root编号一定从1开始。由于次性质,完全二叉树可用数组存储,用下标表示其左右子树编号。数组开到结点个数+1即可。在完全二叉树中,判断某个结点是否为叶子结点标志为:判断该结点的左孩子结点编号2*x是否大于结点总个数n。大于是叶子结点。判断是否为空结点标志为:该结点下标root大于结点总个数n。

    展开全文
  • 二叉树

    2018-12-19 14:56:59
    二叉树二叉树定义满二叉树完全二叉树 二叉树定义 二叉树是一种特殊的树。二叉树的特点是每个结点最多有两个儿子,左边的叫做左儿子,右边的叫做右儿子,或者说每个结点最多有两棵子树。更加严格的递归定义是:...

    定义

    二叉树要么为空,要么由根结点、左子树和右子树组成,而左子树和右子树分别是一棵二叉树。 下面这棵树就是一棵二叉树。
    二叉树

    满二叉树

    如果二叉树中每个内部结点都有两个儿子,这样的二叉树叫做满二叉树。或者说满二叉树所有的叶结点都有同样的深度。比如下面这棵二叉树,是不是感觉很“丰满”。满二叉树的严格的定义是一棵深度为h且有2h-1个结点的二叉树。
    满二叉树

    完全二叉树

    如果一棵二叉树除了最右边位置上一个或者几个叶结点缺少外其它是丰满的,那么这样的二叉树就是完全二叉树。严格的定义是:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,就是完全二叉树。也就是说如果一个结点有右子结点,那么它一定也有左子结点。例如下面这三棵树都是完全二叉树。 完全二叉树的最典型应用就是:堆
    在这里插入图片描述在这里插入图片描述在这里插入图片描述
    其实完全二叉树类似下面这个形状。
    在这里插入图片描述

    说到这里我们马上就要领略到完全二叉树的魅力了。先想一想一棵完全二叉树如何存储呢?其实完全二叉树中父亲和儿子之间有着神奇的规律,我们只需用一个一维数组就可以存储完全二叉树。首先将完全二叉树进行从上到下,从左到右编号。
    在这里插入图片描述

    通过上图我们发现如果完全二叉树的一个父结点编号为k,那么它左儿子的编号就是2k,右儿子的编号就是2k+1。如果已知儿子(左儿子或右儿子)的编号是x,那么它父结点的编号就是x/2,注意这里只取商的整数部分。在C语言中如果除号‘/’两边都是整数的话,那么商也只有整数部分(即自动向下取整),即4/2和5/2都是2。另外如果一棵完全二叉树有N个结点,那么这个完全二叉树的高度为log2 N简写为log N,即最多有log N层结点。

    二叉查找树/二叉排序树

    满足一下特性:
    1.非叶子节点最多拥有2个子节点
    2.非叶子节点值大于左边子节点、小于右边子节点
    3.没有值相等重复的节点
    二叉查找树
    它的查找时间复杂度为O(logN),当然也存在最差的情况,比如下图,查找的时间复杂度为O(N),跟顺序查找效率一样
    在这里插入图片描述

    二叉平衡树

    在二叉查找树的基础上,又增加了如下的约定:

    树的左右两边层级数相差不超过1

    平衡二叉树的查找效率很快,但是维护一颗平衡二叉树的代价是非常大的,需要1次或者多次的左旋和右旋来得到插入或更新后的平衡性。举例:

    初始平衡二叉树
    平衡二叉树

    插入元素0003
    在这里插入图片描述
    对元素0005进行右旋(将元素0005变为右子节点):
    在这里插入图片描述
    对元素0002进行左旋(将元素0002变为左子节点):
    在这里插入图片描述

    最终得到一个平衡二叉树

    参考:
    http://blog.51cto.com/ahalei/1414035
    http://wiki.jikexueyuan.com/project/easy-learn-algorithm/amazing-priority-array.html
    https://mp.weixin.qq.com/s?__biz=MzIxMzk3Mjg5MQ==&mid=2247483916&idx=1&sn=bfc33b53f8176e6f4d7e64c087ad36a4&chksm=97afe0f8a0d869eeaa14d8b26eca9d6fa09f9fda4557b40cb22ebe75851aa4dfb67d822233d9&scene=0&subscene=90&sessionid=1539434820&ascene=7&devicetype=andro

    展开全文
  • 关于特殊二叉树的一些定义

    千次阅读 2013-10-09 15:52:14
    数算教材上,对于满二叉树定义是所有节点含有0个或2个子节点的二叉树称之为满二叉树。... 经过上网搜索才发现国内的一些定义严格意义上名词的一一对应是否合理。  wikipedia 上对于一些二叉树定义是这样的:
  • 二叉树概念

    2018-03-31 10:38:35
    二叉树中还有连两种特殊的二叉树:满二叉树和完全二叉树二叉树: 满二叉树严格定义是一棵深度为 h 且有 2^h -1 个结点的二叉树完全二叉树严格定义是:若设二叉树的高度为 h,除第 h 层外,其它各层 (1~...
  • 从树的外形来看,满二叉树严格三角形的,大家记住下面的图,它就是满二叉树的标准形态: 所有内部节点都有两个子节点,最底一层是叶子节点。 性质: 1)如果一颗树深度为h,最大层数为k,且深度与最大层数相同...
  • 平衡二叉树严格定义是这样的:二叉树中任意一个节点的左右子树的高度相差不能大于 1(小于等于1)从这个定义来看,上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树,但是非完全二叉树也有可能是平衡二叉树...
  • 平衡二叉树

    2013-12-13 16:58:32
    形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是:  一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令>  (a)平衡二叉树 (b)非平衡二叉树  图8.3 平衡...
  • 形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是:  一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令 hl 和 hr 分别为左、右子树的深度。当且仅当  ①TL 、...
  • 平衡二叉树严格定义是这样的:二叉树中任意一个节点的左右子树的高度相差不能大于 1(小于等于1)从这个定义来看,上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树,但是非完全二叉树也有可能是平衡二叉树...
  • 在介绍孩子兄弟表示法的时候,我们提到一般的树都...❝二叉树的子树有严格的左右之分,其次序不能任意颠倒,否则就变成了另一棵二叉树了。❞分支节点的孩子节点也分为「左孩子」和「右孩子」。二叉树的五种基本形态...
  • 二叉树的先序遍历

    2020-05-10 15:40:09
    二叉树的概念 ...如果一个二叉树除了最右边位置上有一个或者几个叶结点缺少外,其他都是丰满的,那么这样的二叉树就是完全二叉树严格定义是:若二叉树的高度为h,除了第h层以外,其他的各层(1~h

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 278
精华内容 111
关键字:

严格二叉树定义