精华内容
下载资源
问答
  • 一棵二叉搜索可被递归地定义为具有下列性质的二叉树:对于任一结点, ...给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索或其镜像进行前序遍历的结果。 输入格式: 输入的第一行给出正整...

    一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,

    • 其左子树中所有结点的键值小于该结点的键值;
    • 其右子树中所有结点的键值大于等于该结点的键值;
    • 其左右子树都是二叉搜索树。

    所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。

    给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

    输入格式:

    输入的第一行给出正整数 N(≤1000)。随后一行给出 N 个整数键值,其间以空格分隔。

    输出格式:

    如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出 YES ,然后在下一行输出该树后序遍历的结果。数字间有 1 个空格,一行的首尾不得有多余空格。若答案是否,则输出 NO

    输入样例 1:

    7
    8 6 5 7 10 8 11
    

    输出样例 1:

    YES
    5 7 6 8 11 10 8
    

    输入样例 2:

    7
    8 10 11 8 6 7 5
    

    输出样例 2:

    YES
    11 8 10 7 5 6 8
    

    输入样例 3:

    7
    8 6 8 5 10 9 11
    

    输出样例 3: 

    NO

    思路: 

           拿到这个题,想到的就是用数据结构学的二叉搜索树,去建树,前序遍历,然后比对,在反转,前序遍历,再比对,比对成功就后序遍历输出,不成功就输出NO。写的比较繁琐,比较菜,希望各位巨巨指正orz

    AC代码

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<string>
    #include<map>
    #define INF 0x3f3f3f3f
    #define rep(i,a,n) for(int i=a;i<n;i++)
    #define per(i,a,n) for(int i=n-1;i>=a;i--)
    #define fori(x) for(int i=0;i<x;i++)
    #define forj(x) for(int j=0;j<x;j++)
    #define memset(x,y) memset(x,y,sizeof(x))
    #define memcpy(x,y) memcpy(x,y,sizeof(y))
    #define sca(x) scanf("%d", &x)
    #define scas(x) scanf("%s",x)
    #define sca2(x,y) scanf("%d%d",&x,&y)
    #define sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define scl(x) scanf("%lld",&x)
    #define scl2(x,y) scanf("%lld%lld",&x,&y)
    #define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
    #define pri(x) printf("%d\n",x)
    #define pri2(x,y) printf("%d %d\n",x,y)
    #define pris(x) printf("%s\n",x)
    #define prl(x) printf("%lld\n",x)
    //#include <bits/stdc++.h>
    
    typedef long long ll;
    const int maxn=1e6+7;
    const int mod=1e9+7;
    const double eps=1e-8;
    
    using namespace std;
    
    int a[maxn];
    int pre1[maxn];
    int pre2[maxn];
    int post1[maxn];
    int post2[maxn];
    typedef struct BiTree
    {
        int data;
        BiTree *left,*right;
    }tree;
    tree* creatbtree(int a[],int n)
    {
    	tree *p,*pa,*c,*root;
    	//创建根节点
    	root=(tree*)malloc(sizeof(tree));
    	root->data=a[0];
    	root->left=root->right=NULL;
    	for(int i=1;i<n;i++){
    		p=(tree*)malloc(sizeof(tree));
    		p->data=a[i];
    		p->left=p->right=NULL;
    		c=root;
    		while(c){
    		pa=c;
    		if(c->data>p->data)
    		c=c->left;
    		else
    		c=c->right;
    	}
    		if(pa->data>p->data)
    	    pa->left=p;
    	    else
        	pa->right=p;
    	}
       	return root;
    }
    void swaptree(tree *&T)
    {
      if(T == NULL)
        return;
      else
        {
          swaptree(T->left);
          swaptree(T->right);
          tree *temp;
          temp = T->left;
          T->left = T->right;
          T->right = temp;
        }
    }
    int pos;
    void PreOrderTraverse(tree *T,int a[])
    { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。有改动
      // 操作结果:先序递归遍历T,对每个结点访问一次
       if(T)
       {
           a[pos++] = T->data;
           //printf("%d ",T->data);
           PreOrderTraverse(T->left,a);
           PreOrderTraverse(T->right,a);
       }
    }
    void PostOrderTraverse(tree *T,int a[])
    { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
      // 操作结果:后序递归遍历T,对每个结点访问一次
       if(T)
       {
           PostOrderTraverse(T->left,a);
           PostOrderTraverse(T->right,a);
           a[pos++] = T->data;
       }
    }
    int main()
    {
    
      string temp;
        int n;
        sca(n);
        rep(i,0,n)
        {
          sca(a[i]);
        }
        tree *root;
        root = creatbtree(a,n);
        pos = 0;
        PreOrderTraverse(root, pre1);
        int flag1 = 1, flag2 = 1;
        rep(i,0,n)
          {
            if(pre1[i] == a[i])
              continue;
            else
              {
                flag1 = 0;
                break;
              }
          }
        if(flag1)
        {
          printf("YES\n");
          pos = 0;
          PostOrderTraverse(root, post1);
          rep(i,0,n)
          {
            printf("%d%c",post1[i],i==n-1?'\n':' ');
          }
          flag2 = 0;
        }
        if(flag2)
          {
            swaptree(root);
            pos = 0;
            PreOrderTraverse(root, pre2);
            rep(i,0,n)
            {
              if(pre2[i] == a[i])
                continue;
              else
                {
                  flag2 = 0;
                  break;
                }
            }
          }
        if(flag2)
        {
          printf("YES\n");
          pos = 0;
          PostOrderTraverse(root, post2);
          rep(i,0,n)
          {
            printf("%d%c",post2[i],i==n-1?'\n':' ');
          }
        }
        if(flag1+flag2 == 0)
        {
          printf("NO\n");
        }
        return 0;
    }
    

     

    展开全文
  • L2-004 这二叉搜索吗? (25 分) 一棵二叉搜索可被递归地定义为具有下列性质的二叉树:对于任一结点, ...给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索或其镜像进行前...

     

    L2-004 这是二叉搜索树吗? (25 分)
    一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,

    其左子树中所有结点的键值小于该结点的键值;
    其右子树中所有结点的键值大于等于该结点的键值;
    其左右子树都是二叉搜索树。
    所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。

    给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

    输入格式:

    输入的第一行给出正整数 N(≤1000)。随后一行给出 N 个整数键值,其间以空格分隔。

    输出格式:

    如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出 YES ,然后在下一行输出该树后序遍历的结果。数字间有 1 个空格,一行的首尾不得有多余空格。若答案是否,则输出 NO。

    输入样例 1:

    7
    8 6 5 7 10 8 11
    输出样例 1:

    YES
    5 7 6 8 11 10 8
    输入样例 2:

    7
    8 10 11 8 6 7 5
    输出样例 2:

    YES
    11 8 10 7 5 6 8
    输入样例 3:

    7
    8 6 8 5 10 9 11
    输出样例 3:

    NO

    
    #include <iostream>
    #include <vector>
    using namespace std;
    const int maxn = 505;
    #define mem(a) memset(a,0,sizeof(a))
    #define inf 0x3f3f3f3f
    struct node{
        int data;
        node *lchild,*rchild;
    };
    void create(node* &T,int data)//建树
    {
       if(T == NULL)
       {
           T = new node;
           T->data=data;
           T->lchild = T->rchild = NULL;
           return ;
       }
       if(data < T->data)
           create(T->lchild,data);
       else
           create(T->rchild,data);
    }
    void preorder(node* T,vector<int> &vi)//前序遍历二叉树
    {
        if(T == NULL)return;
        vi.push_back(T->data);
        preorder(T->lchild,vi);
        preorder(T->rchild,vi);
    }
    void pre_mirror(node* T,vector<int>&vi)//得到前序镜像二叉树遍历结果
    {
        if(T == NULL)
            return;
        vi.push_back(T->data);
        pre_mirror(T->rchild,vi);
        pre_mirror(T->lchild,vi);
    }
    void postorder(node* T,vector<int> &vi)//后序遍历二叉树
    {
        if(T == NULL)return;
        postorder(T->lchild,vi);
        postorder(T->rchild,vi);
        vi.push_back(T->data);
    }
    void post_mirror(node* T,vector<int>&vi)//得到后序镜像二叉树遍历结果
    {
        if(T == NULL)
            return;
        post_mirror(T->rchild,vi);
        post_mirror(T->lchild,vi);
        vi.push_back(T->data);
    }
    vector<int> initial,pre,pre_m,post,post_m;
    int main()
    {
        int n,data;
        node* T = NULL;
        cin>>n;
        for(int  i = 0;i  <n;i++)
        {
            cin>>data;
            initial.push_back(data);
            create(T,data);//建立二叉搜索树
        }
        preorder(T,pre);
        pre_mirror(T,pre_m);
        postorder(T,post);
        post_mirror(T,post_m);
        if(initial == pre)//给定树与二叉搜索树的前序遍历或镜像的前序遍历相同,则为二叉搜索树
        {
            puts("YES");
            for(int i = 0;i < post.size();i++)
            {
                if(i)
                    cout<<" ";
                cout<<post[i];
            }
        }
        else if(initial == pre_m)
        {
            puts("YES");
            for(int i = 0;i < post_m.size();i++)
            {
                if(i)
                    cout<<" ";
                cout<<post_m[i];
    
            }
        }
        else
            puts("NO");
    
        return  0;
    }

     

    展开全文
  • L2-004这二叉搜索吗?(25分) 一棵二叉搜索可被递归地定义为具有下列性质的二叉树:对于任一结点, ...给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索或其镜像进行前序...

    L2-004 这是二叉搜索树吗? (25 分)

    一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,

    • 其左子树中所有结点的键值小于该结点的键值;
    • 其右子树中所有结点的键值大于等于该结点的键值;
    • 其左右子树都是二叉搜索树。

    所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。

    给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

    输入格式:

    输入的第一行给出正整数 N(≤1000)。随后一行给出 N 个整数键值,其间以空格分隔。

    输出格式:

    如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出 YES ,然后在下一行输出该树后序遍历的结果。数字间有 1 个空格,一行的首尾不得有多余空格。若答案是否,则输出 NO

    输入样例 1:

    7
    8 6 5 7 10 8 11
    

    输出样例 1:

    YES
    5 7 6 8 11 10 8
    

    输入样例 2:

    7
    8 10 11 8 6 7 5
    

    输出样例 2:

    YES
    11 8 10 7 5 6 8
    

    输入样例 3:

    7
    8 6 8 5 10 9 11
    

    输出样例 3:

    NO

    思路:建立线索二叉树,进行先序遍历,检查是否与原序列相同,相同则输出后序序列

     

    #include<iostream>
    #include<vector>
    using namespace std;
    struct Node {
    	int data = 0;
    	Node *left = NULL, *right = NULL;
    };
    vector<int> preOrder, judge, out;
    void insert(Node *head, int tmp) {   //构建搜素树
    	Node *r;
    	if (head != NULL) {
    		r = tmp < head->data ? head->left : head->right;
    		if (r != NULL)	insert(r, tmp);
    		else
    			(tmp < head->data ? head->left : head->right) = new Node({ tmp });
    	}
    }
    void Order(Node *head, const int& key) {
    	if (head != NULL) {
    		judge.push_back(head->data);
    		if (!key)		Order(head->left, key);		
    		Order(head->right, key);
    		if (key)		Order(head->left, key);		//镜像判断
    		out.push_back(head->data);  //存储后序
    	}
    }
    int main() {
    	int n, tmp;
    	cin >> n >> tmp;
    	Node *head = new Node({ tmp });
    	preOrder.assign({ tmp });
    	for (int i = 1; i < n; i++) {
    		cin >> tmp;
    		preOrder.push_back(tmp);
    		insert(head, tmp);
    	}
    	for (int i = 0; i < 2; i++) {
    		judge.clear();
    		out.clear();
    		Order(head, i);
    		if (judge == preOrder) {
    			cout << "YES" << endl;
    			for (int j = 0; j < out.size(); j++)
    				cout << (j ? " " : "") << out[j];
    			return 0;
    		}
    	}
    	cout << "NO" << endl;
    	return 0;
    }

     

    展开全文
  •   平衡二叉树又被称为AVL,它具有以下性质:它一棵空或它的左右子树的高度差的绝对值不超过1,并且左右两个子树都一棵平衡二叉树; 相关概念: 平衡因子:左右子树高度差的绝对值; 最低不平衡节点:用A...
    二叉搜索树已经足够完美了吗?

      比如 插入1、2、3、4、5、6、7、8;形成的二叉搜索树如下:
    在这里插入图片描述

    性质

      平衡二叉树又被称为AVL树,它具有以下性质:它是一棵空树或它的左右子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树;
    在这里插入图片描述

    相关概念:

    • 平衡因子:左右子树高度差的绝对值;
    • 最低不平衡节点:用A表示最低不平衡节点,则A的祖先节点可能有不平衡的, 但是其所有后代节点都是平衡的;
    • 失去平衡的最小子树:距离插入节点最近且平衡因子绝对值大于1的节点 作为根的子树;

    不平衡的四种情形

    1、对A的左儿子的左子树进行一次插入 ,称为LL型
    2、对A的左儿子的右子树进行一次插入,称为LR型
    3、对A的右儿子的右子树进行一次插入,称为RR型
    4、对A的右儿子的左子树进行一次插入,称为RL型
    在这里插入图片描述

    平衡调整的实现方法

    • 单旋:右旋(LL型)、左旋(RR型)
    • 双旋:左右旋(LR型)、右左旋(RL型)
    右旋

    在这里插入图片描述

    左旋

    在这里插入图片描述

    左右旋

    在这里插入图片描述

    右左旋

    在这里插入图片描述

    展开全文
  • 我用二叉哈夫曼代码改的,但是无法实现,首先叶子节点和节点数没法表示,然后就算自己输入固定节点也无法正确实现,请问怎么实现三叉哈夫曼呢 #include #include #include #include using namespace ...
  • 线段入门教程

    2018-08-14 08:36:00
    线段树是什么? 二叉树大家知道吗?就是每一个节点会有左右两个子节点,子节点又有子节点……总起来就是二叉树。二叉树在玄学数据结构中会经常用到,比如splay,treap,乃至红黑树等等魔法玩意。这些不用管,就...
  • 符合条件的数据结构就有图、和其它。 嗯~了解一下就行。我们进入正题: 数组 数组一种线性结构,以十二生肖(鼠、牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪)排序为例:...
  • 以下题目对于不熟悉数据结构的同学的天梯赛部分题解(我就是不懂数据结构的一个),全部采用数组来求结果,希望大家能起到作用,欢迎大家评论指出我的不足。 这二叉搜索吗?(25) 链接 一棵二叉搜索可被...
  • 1.2.8 大数据平台中的元数据管理怎么理解的,元数据收集管理体系怎么样的,会大数据应用有什么样的影响 1.2.9 你理解常见如阿里,和友商大数据平台的技术体系差异以及发展趋势和技术瓶颈,在存储和计算两...
  • SqlToolBox 1.8.2

    2010-05-22 10:25:56
    成功连接到数据库以后,数据库的Schema和table结构会在画面的左边以的形式展现出来,如果展现的内容过多,您还可以在上方的“过滤器”输入栏中输入关键字以缩小展现范围。在这颗中,表格(table)以小圆点的...
  • 6. JavaScript 数据结构与算法之美 - 非线性表(、堆) 7. JavaScript 数据结构与算法之美 - 冒泡排序、选择排序、插入排序 8. JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序 9. ...
  • (10KB)<END><br>46,treestore.zip 将结构存入一个文本文件,可以读出及写入数的结构。(41KB)<END><br>47,MultControl.zip 这一个多列的/列表控制类库(87KB)<END><br>48,printctrl.zip 一个支持打印...

空空如也

空空如也

1 2 3
收藏数 56
精华内容 22
热门标签
关键字:

树是左右结构对吗