精华内容
下载资源
问答
  • 严格二叉树:如果一颗二叉树的每个非终端节点有且仅有两棵子树,则称这棵二叉树为严格二叉树。 判断二叉树是否为严格二叉树 思路 二叉树层序遍历 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;
    }
    
    
    展开全文
  • 人们已经提出了一些由一棵二叉树的某两种遍历序列以及某种遍历序列和结点的某种...新的由一棵严格二叉树的某两种遍历序列以及某种遍历序列和结点的某种信息构造该严格二叉树的算法,为 构造严格二叉树提供了更多的途经。
  • 一颗二叉树,其左右子树都空,或都不空,则为“严格二叉树”,用先序遍历 和后序遍历能确定一颗严格二叉树,二叉树的前序序列为 ABDECFHIGJLKMN,后序序列为 DEBHIFLJMNKGCA. 然后输出其中序遍历 【题解】 主要就是...

    一颗二叉树,其左右子树都空,或都不空,则为“严格二叉树”,用先序遍历
    和后序遍历能确定一颗严格二叉树,二叉树的前序序列为 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;
    }
    
    展开全文
  • 严格二叉树,这个定义就百度上有,维基百科都没查到。 严格二叉树的定义:如果一颗二叉树的每个非终端节点都有且仅有两棵子树,则称这颗二叉树为严格二叉树。摘自百度百科。 简单的说,没有度为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,如需转载请自行联系原作者




    展开全文
  • 给出一棵二叉树,节点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,这使...

    Lorenzo Von Matterhorn

     

    给出一棵二叉树,节点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,这使我们很容易想到LCA,但是数据范围太大,所以利用二叉树的性质:i的父亲为(i>>1),再加上LCA的思想,就可以做出框架,但还是由于数据范围太大,所以只能用map储存各个边的值(map[i]表示i-(i>>1)的值)。

     

     

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <map>
    #define LL long long
    using namespace std;
    map<LL,LL>s;
    LL u,v,w;
    void update(LL u,LL v,LL w){
    	while(u != v){
    		if(u > v){
    			s[u] += w;
    			u >>= 1;
    		}
    		if(u < v){
    			s[v] += w;
    			v >>= 1;
    		}
    	}
    }
    
    LL query(LL u,LL v){
    	LL res = 0;
    	while(u != v){
    		if(u > v){
    			res += s[u];
    			u >>= 1;
    		}
    		if(u < v){
    			res += s[v];
    			v >>= 1;
    		}
    	}
    	return res;
    }
    
    int main(){
    	int q,op;
    	scanf("%d",&q);
    	for(int i = 1;i <= q;++i){
    		cin>>op>>u>>v;
    			if(op == 1){
    			cin>>w;
    			update(u,v,w);
    		}
    		else{
    			cout<<query(u,v)<<endl;
    		}
    	}
    	return 0;
    }
    

      

     

    转载于:https://www.cnblogs.com/xgtao984/p/5680186.html

    展开全文
  • 若二叉树BT的每个结点,其左、右子树都为空,或者其左、右子树都不空,这种二又树有时称为“严格二叉树”。由“严格二叉树”的前序序列和后序序列可以唯一确定该二叉树。设“严格二叉树”BT的前序遍历序列为:...
  • 二叉树

    2021-02-10 20:53:17
    更加严格的递归定义是:二叉树要么为空,要么是由根结点、左子树和右子树分别是一棵二叉树。下面这棵树就是一棵二叉树。 一棵多叉树也可以转化为二叉树二叉树中还有两种特殊的二叉树,叫做满二叉树和完全二叉树...
  • 从树的外形来看,满二叉树严格三角形的,大家记住下面的图,它就是满二叉树的标准形态: 所有内部节点都有两个子节点,最底一层是叶子节点。 性质: 1)如果一颗树深度为h,最大层数为k,且深度与最大层数相同...
  • 二叉树概念

    2018-03-31 10:38:35
    二叉树中还有连两种特殊的二叉树:满二叉树和完全二叉树二叉树: 满二叉树严格的定义是一棵深度为 h 且有 2^h -1 个结点的二叉树完全二叉树严格的定义是:若设二叉树的高度为 h,除第 h 层外,其它各层 (1~...
  • 二叉树简介

    2018-12-25 11:25:32
    二次树不区分左右子树,二叉树严格区分左右子树 满二叉树: 所有的分支结点都有左右孩子结点,叶子结点在最下面一层 非空满二叉树特点:1.叶子结点在最下面一层 2.只有度为0和2的点 完全二叉树:一层一层从左往右...
  • 二叉树:是由n>=0个节点所构成的有限集合。当n=0时,此二叉树为空树;...2.树中的子树是不分顺序的,而二叉树中的子树有严格的左右之分。 3.相同节点数所能组成的不同形态的树和二叉树的数目不同。 下面介绍两种
  • 而且在遍历过程中,只有两个子树的根节点对称了,继续比较左右子树是否对称才有意义,因此我们使用"中序遍历"(其实不是严格的中序遍历,只是我们先比较根节点) 按照遍历依赖的不同,可以分为以下三类方法: 递归...
  • 平衡二叉树

    2020-07-15 12:00:08
    声明:下面的代码只是一个最基础的实现,没有经过严格的测试。 /** * 平衡二叉树(AVL) * 1,可以保证查询效率,它是一棵空树或者它的左右两个子树的高度差不超过1,并且左右两个子树都是一颗平衡二叉树。 * 2,...
  • 形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是:  一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令 hl 和 hr 分别为左、右子树的深度。当且仅当  ①TL 、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,500
精华内容 600
关键字:

严格二叉树