精华内容
下载资源
问答
  • 【历年真题】严格二叉树已知前序和后序还原这棵树
    2019-10-09 08:16:34

    一颗二叉树,其左右子树都空,或都不空,则为“严格二叉树”,用先序遍历
    和后序遍历能确定一颗严格二叉树,二叉树的前序序列为 ABDECFHIGJLKMN,后序序列为 DEBHIFLJMNKGCA.
    然后输出其中序遍历

    【题解】


    主要就是根据这个二叉树的特点写个递归就好。
    因为如果有左子树一定有右子树。
    所以先序遍历当前节点的下一个节点一定是左子树的根节点。
    那么我们只要在后序遍历中找到这个左子树的根节点就好了。
    然后,在后序遍历中这个左子树的根节点的左边的点肯定就都是它的子树里的节点了。
    那么它后面的点是什么呢?肯定就是当前节点的右子树的后序遍历了(除了最后一个节点即根节点本身外)
    然后递归,找到每个节点的左右儿子节点就行

    【代码】

    #include <cstdio>
    #include <iostream>
    using namespace std;
    
    const int N = 100;
    
    int l[N+10],r[N+10],root,cur;
    char dic[N+10];
    
    //前序后序
    string s1,s2;
    int len1,len2;
    
    //返回和前序中l1..r1后序中l2..r2对应的树的根节点
    int doit(int l1,int r1,int l2,int r2){
        if (l1>r1) return -1;
        char key = s1[l1];
        int now = ++cur;
        dic[now] = key;
        if (l1+1>r1) return now;//如果是叶子节点,就直接返回这个节点
        //不是叶子节点,那么一定有左子树和右子树
        char keyl = s1[l1+1];
        int j;
        for (int i = l2;i <= r2;i++)//在后序中找到key的左子树的根节点
            if (s2[i]==keyl){
                j = i;
                break;
            }
        //则l2..j这一段是key的左子树对应的后序遍历
        int len = j-l2+1;
        l[now] = doit(l1+1,l1+1+len-1,l2,j);
        //而j+1..r2-1这一段是key的右子树对应的后序遍历
        r[now] = doit(l1+1+len,r1,j+1,r2-1);
        return now;
    }
    
    void dfs(int x){
        if (x<=0) return;
        dfs(l[x]);
        printf("%c",dic[x]);
        dfs(r[x]);
    }
    
    int main(){
        //freopen("D:\\rush.txt","r",stdin);
        cin >> s1 >> s2;
        len1 = s1.size();len2 = s2.size();
        root = doit(0,len1-1,0,len2-1);
        dfs(root);//输出其中序遍历
        return 0;
    }
    
    更多相关内容
  • 人们已经提出了一些由一棵二叉树的某两种遍历序列以及某种遍历序列和结点的某种...新的由一棵严格二叉树的某两种遍历序列以及某种遍历序列和结点的某种信息构造该严格二叉树的算法,为 构造严格二叉树提供了更多的途经。
  • 判断二叉树是否为严格二叉树

    千次阅读 2020-03-25 17:25:50
    严格二叉树:如果一颗二叉树的每个非终端节点有且仅有两棵子树,则称这棵二叉树为严格二叉树。 判断二叉树是否为严格二叉树 思路 二叉树层序遍历 c++代码实现 #include <iostream> #include <cstdlib> ...
    题目内容

    严格二叉树:如果一颗二叉树的每个非终端节点有且仅有两棵子树,则称这棵二叉树为严格二叉树。
    判断二叉树是否为严格二叉树

    思路

    二叉树层序遍历

    c++代码实现
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    /*构造二叉树存储结构*/
    typedef int TElemType;
    typedef struct BiTNode
    {
        TElemType data;
        BiTNode *leftc,*rightc;
    }*BiTree;
    /*创建二叉树*/
    void CreatBiTree(BiTree &B,TElemType s[],int n,int &x)
    {
        x ++;
        if(x >= n)
        {
            B = NULL;
            return;
        }
        B = new BiTNode;
        B->data = s[x];
        CreatBiTree(B->leftc,s,n,x);//构造左子树
        CreatBiTree(B->rightc,s,n,x);//构造右子树
    }
    /*判断是否是严格二叉树*/
    bool strict_Bitree(BiTree B)
    {
        if(!B) return true;//空
        else if((!B->leftc && B->rightc) || (!B->rightc && B->leftc)) return false;//判断有没有单孩子结点
        return strict_Bitree(B->leftc) && strict_Bitree(B->rightc);//递归判断左右孩子
    }
    int main()
    {
        TElemType s[] = {1,2,3,4,5,6,7,8,9,10};
        int n=10;
        BiTree B;
        int x=-1;
        CreatBiTree(B,s,n,x);
        bool two = strict_Bitree(B);
        if(two) cout << "是严格二叉树。" <<endl;
        else cout << "不是严格二叉树。" << endl;
        return 0;
    }
    
    
    展开全文
  • 严格二叉树,这个定义就百度上有,维基百科都没查到。 严格二叉树的定义:如果一颗二叉树的每个非终端节点都有且仅有两棵子树,则称这颗二叉树为严格二叉树。摘自百度百科。 简单的说,没有度为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,如需转载请自行联系原作者




    展开全文
  • 自然界中的二叉树 数据结构中的二叉树 特殊的二叉树  满二叉树:一个二叉树,如果每一层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为k,且结点总数是2k-1,则它就是满...

    树的概念及结构

    树的概念

     树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成的一个具有层次关系的集合。把它叫做“树”,是因为它看起来像一颗倒挂的树,也就是说它是根朝上,而叶朝下的。
    在这里插入图片描述
    树的特点:
     有一个特殊的结点,称为根结点,根结点没有前驱结点。
     除根结点外,其余结点被分成M(M>0)互不相交的集合T1,T2…Tm,其中每一个集合Ti(1<=i<=m)又是一颗结构与树类似的子树。
     每棵子树的根结点有且仅有一个前驱,可以有0个或多个后继。
     因此,树是递归定义的。

    树中的专有名词

    结点的度:一个结点含有的子树的个数称为该结点的度。
    叶结点(终端结点):度为0的结点称为叶结点。
    非终端结点(分支结点):度不为0的结点。
    父结点(双亲结点):若一个结点含有子结点,则这个结点称为其子结点的父结点。
    子结点(孩子结点):一个结点含有的子树的根结点称为该结点的子结点。
    兄弟结点:具有相同父结点的结点互称为兄弟结点。
    树的度:一棵树中,最大的结点的度称为树的度。
    结点的层次:从根开始定义起,根为第一层,根的子结点为第二层,以此类推。
    树的高度(树的深度):树中结点的最大层次。
    堂兄弟结点:双亲在同一层的结点互称为堂兄弟结点。
    结点的祖先:从根到该结点所经分支上的所有结点。
    子孙:以某结点为根的子树中任一结点都称为该结点的子孙。
    森林:由m(m>0)棵互不相交的树组成的集合称为森林。
    在这里插入图片描述

    树的表示

     树结构相对于线性表就比较复杂了,要存储和表示起来就比较麻烦了,实际中树有很多种表示方法。如:双亲表示法、孩子表示法、孩子兄弟表示法等等。其中最常用的是孩子兄弟表示法
     孩子兄弟表示法中,所定义的结点类型大致是这样的:

    typedef int DataType
    
    struct Node
    {
    	struct Node* firstChild;   //第一个孩子结点
    	struct Node* nextBrother;  //指向下一个兄弟结点
    	DataType data;             //结点中的数据域
    };
    

    对于任意树,我们都可以用孩子兄弟法访问到树中的每一个结点:
    在这里插入图片描述

    树在实际中的运用(表示文件系统的目录树结构)

    在这里插入图片描述

    二叉树的概念及其重要性质

    二叉树的概念

     二叉树是n个结点的有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。当集合为空时,称该二叉树为空二叉树。

    二叉树的特点:
     每个结点最多有两个棵子树,即二叉树不存在度大于2的结点。
     二叉树的子树有左右之分,其子树的次序不能颠倒。

    自然界中的二叉树

    在这里插入图片描述

    数据结构中的二叉树

    在这里插入图片描述

    特殊的二叉树

    满二叉树:一个二叉树,如果每一层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为k,且结点总数是2k-1,则它就是满二叉树。
    完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至N的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
    在这里插入图片描述
    总结:
    满二叉树:若树的深度为K,那么它的每一层的结点数必须都是满的。
    完全二叉树:若数的深度为K,那么它的前K-1层的结点数必须都是满的,第K层的结点数可以不是满的但是从左到右必须是连续的。

    二叉树的性质(重要!!!)

    性质一:若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2i-1个结点。
    性质二:若规定根结点的层数为1,则深度为h的二叉树的最大结点数为2h-1个。
    性质三:对任何一棵二叉树,如果度为0的叶结点个数为n0,度为2的分支结点个数为n2,则有n0 = n2+1。
    性质四:若规定根结点的层数为1,则具有N个结点的满二叉树的深度h = log2(N+1)。
    性质五:对于具有N个结点的完全二叉树,如果按照从上至下、从左至右的数组顺序对所有结点从0开始编号,则对于序号为i的结点:
     若 i > 0,则该结点的父结点序号为:( i - 1) / 2;若 i = 0,则无父结点。
     若2i + 1 < N,则该结点的左孩子序号为:2i + 1;若2i + 1 >= N,则无左孩子。
     若2i + 2 < N,则该结点的右孩子序号为:2i + 2;若2i + 2 >= N,则无右孩子。
    在这里插入图片描述
    练习一下:
     1.某二叉树共有399个结点,其中199个度为2的结点,则该二叉树中的叶子结点数为( )。
     A.不存在这样的二叉树
     B.200
     C.198
     D.199

     2.在具有2n个结点的完全二叉树中叶子结点个数为( )。
     A.n
     B.n+1
     C.n-1
     D.n/2

     3.一棵完全二叉树的结点数为531,那么这棵树的高度为( )。
     A.11
     B.10
     C.8
     D.12

     4.一个具有767个结点的完全二叉树,其叶子结点个数为( )。
     A.383
     B.384
     C.385
     D.386

    解析:
     1.(答案:B)根据性质三,叶子结点(度为0)的个数200个,由于199+200 = 399(该二叉树的总结点数),所以该二叉树的叶子结点数为200。

     2.(答案:A)根据性质三,度为0的结点数和度为2的结点数之和应为奇数,因为该完全二叉树的结点总数为2n(偶数),所以二叉树中必然存在一个度为1的结点。于是可以推出:度为0的结点和度为2的结点总共有2n-1个。性质三:对任何一棵二叉树,度为0的叶结点个数比度为2的分支结点个数多1,所以该二叉树度为1的结点个数为n-1,度为0的结点数(即叶结点数)为n。
    注意理解:任何一棵完全二叉树中度为1的结点要么有1个,要么就没有度为1的结点。因为完全二叉树的最后一层的结点必须是从左到右连续的,而位于最后一层之前的层数的结点的度均为2。
    在这里插入图片描述
     3.(答案:B)假设该完全二叉树的层数为K,则该完全二叉树的前K-1层的结点总数为2K-1-1,若该完全二叉树是满二叉树,则该满二叉树的结点总数为2K-1,所以深度为K的完全二叉树的结点总数范围为:2K-1-1 < N <= 2K-1。因为29 < 531 <= 210,所以该完全二叉树的高度为10。
    注意记忆:210 = 1024。

     4.(答案:B)该题与第2题的道理是一样的,因为该树的结点总数为767(奇数),所以该树中不存在度为1的结点,度为2的结点个数为383,度为0的结点个数为384,即叶子结点个数为384。

    二叉树的存储结构

    顺序结构

     顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实生活中只有堆(一种二叉树)才会使用数组来存储。二叉树的顺序存储在物理上是一个数组,在逻辑上是一棵二叉树
    在这里插入图片描述

    链式结构

     二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素之间的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来存储该结点左孩子和右孩子所在的结点的地址。
     链式结构又分为二叉链和三叉链,之后我们会用二叉链来实现二叉树的链式存储结构,三叉链运用于更高阶的数据结构,例如红黑树。
    在这里插入图片描述

    展开全文
  • packagecom.example.demo.tree;importcom.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;importorg.omg.PortableInterceptor.INACTIVE;importjava.util.Comparator;/***@authorsteve* @date 2020/4/16 10:0...
  • 二叉树的分类 1.一般树 2.只有左(右)孩子的树:(可改造的单链表) 3.哈夫曼树-应用:哈夫曼编码-权值和最小 4.平衡二叉树 4.1完全二叉树 4.1.1堆 小根堆:根<左,右 大根堆:根>左,右 4.1.2满二叉树...
  • 树形结构 这是我们最熟悉的线性...可以初步看出,二叉树就是每个节点要么没有分枝,要么就是分两根枝,而多叉树的每个节点可以有任意的分枝。 生活中的树形结构 文件夹的管理就是我们生活中最常见的树形结构 ...
  • 完全二叉树判断逻辑: 两个标识:flag标识是否是完全二叉树,isLeaf标识是否遍历到叶子结点 1. 若一个结点无左孩子有右孩子,置flag为false 2. 当一个结点无右孩子时,说明这个结点以后的结点一定是叶子结点,将...
  • 给出一棵二叉树,节点i与2*i和2*i+1相连,i的范围是1~10^18,每一条边有一个权值w(0~10^9),给出q(1~1000)个操作,操作有两种,1:将u-v所有边的权值加上w。2:询问u-v所有边的总的权值。 首先分析u-v,这使...
  • 树、二叉树、完全二叉树的区别与基本概念 一、树 树:不包含回路的连通无向图(树是一种简单的非线性结构)。 树有着不包含回路的特点,所以树就被赋予了很多特性: 1、一棵树中任意两个结点有且仅有唯一的一...
  • 树和二叉树对比

    千次阅读 热门讨论 2020-09-08 17:03:59
    树和二叉树都有一个树字,从结构上来说,都是树状结构,但是它们之间的区别是什么呢?那就拿两者的特点来说一说把。 首先是 树 先看一下树的基本概念和它的一些术语: Root:根节点。 描述:树的顶部节点。 ...
  • 二叉树高度的范围:最坏情况:O(n), 最好情况:O(log n) 怎样确定是否使用递归?主要看递归的深度。因为递归会涉及到stack,占用的stack的空间进程分配到的空间,深度太大会涉及到stackOverflow的问题。 2....
  • 看 空标识 后的元素是否全是 空标识,全是空标识 则是完全二叉树,不全是空标识则是完全二叉树 问题(待解决): 无法实现 得到带有空子树标识的层序遍历序列 的算法,没想到如何将空标识加入到list的适当位置 ...
  •   完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。   它...
  • 平衡二叉树(Balanced Binary Tree)又被称为AVL树,且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。如下面的三棵树:只有中间才是平衡二叉树。...
  • 完全二叉树与满二叉树的区别(有图)

    万次阅读 多人点赞 2015-07-08 08:45:32
    先看图: 完全二叉树:设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数, ...第 h 层所有的结点都连续集中在最左边 ...满二叉树:深度为k且有2^k-1个结点的二叉树称为满二叉树
  • 从树的外形来看,满二叉树严格三角形的,大家记住下面的图,它就是满二叉树的标准形态: 所有内部节点都有两个子节点,最底一层是叶子节点。 性质 : 1) 如果一颗树深度为h,最大层数为k,且深度...
  • 严格二叉树: 树的每个节点都有左孩子右孩子或者没有孩子; 斜树:斜树的每个节点只有一个孩子;若斜树的每个节点都只有左孩子则称为左斜树,若斜树的每个节点只有右孩子则称为右斜树; 满二叉树:所有的父节点都...
  • 完全二叉树和满二叉树的区别

    万次阅读 多人点赞 2015-06-12 14:34:28
    其实满二叉树是完全二叉树的特例,因为满二叉树已经满了,而完全并不代表满。所以形态你也应该想象出来了吧,满指的是出了叶子节点外每个节点都有两个孩子,而完全的含义则是最后一层没有满,并没有满。 下面贴...
  • 二叉树的算法

    2020-06-15 20:54:36
    //二叉树的算法(非原创) //输入为字符 #include<stdio.h> #include<stdlib.h> #include using namespace std; typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*...
  • 显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树。 如果一个完全二叉树的结点总数为768个,求叶子结点的个数。 n0=n2+1,带入768=n0+n1+n2中得:768=n1+2n2+1,因完全二叉树度为1...
  • 遍历二叉树及其应用遍历二叉树及其应用二叉树的遍历算法:1. 前序遍历递归实现:非递归实现:2. 中序遍历递归实现:非递归实现:3. 后序遍历递归实现:非递归实现:4. 层序遍历队列实现:二叉树的恢复:(必考)1. ...
  • 二叉树和平衡二叉树

    2022-04-07 11:36:03
    红黑树:通过舍弃严格的平衡和引入红黑节点,解决了AVL旋转效率过低的问题,但是在磁盘等场景下,树仍然太高,IO次数太多 B树:通过将二叉树改为多路平衡查找树,解决了树过高的问题 B+树:在B树的基础上,将非叶...
  • 二叉树基础及二叉树顺序结构
  • 二叉树

    2021-04-26 10:35:39
    二叉树二叉树的定义 二叉树的定义 二叉树也称为二分树,它是有限的结点集合,这个集合或为空,或由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。 显然,和树的定义一样,二叉树的定义也是一个递归...
  • python二叉树

    万次阅读 多人点赞 2018-02-09 09:00:21
    上述观察实际上给了我们一种严格的定义树的方法: 树是元素的集合。 该集合可以为空。这时树中没有元素,我们称树为空树 (empty tree)。 如果该集合不为空,那么该集合有一个根节点,以及0个或者...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,564
精华内容 9,025
关键字:

严格二叉树

友情链接: IMX_AACPD_3.0.7-2.tar.gz