精华内容
下载资源
问答
  • 出题:输入一个整数数组,判断该数组是否符合一个二元查找树的后序遍历(给定整数数组,判定其是否满足某二元查找树的后序遍历); 分析:利用后序遍历对应到二元查找树的性质(序列最后一个元素必定是根节点,从...

    出题:输入一个整数数组,判断该数组是否符合一个二元查找树的后序遍历(给定整数数组,判定其是否满足某二元查找树的后序遍历);

    分析:利用后序遍历对应到二元查找树的性质(序列最后一个元素必定是根节点,从左向右第一个比根节点大的元素开始直到根节点之前的所有元素必定在右子树,之前的所有元素必定在左子树);

    解题:

     1 bool PostOrderCheck(int *array, int i, int j) {
     2         /**
     3          * 如快速排序一样,解决小子文件
     4          * */
     5         if(j-i+1 == 3) {
     6                 if(array[i]<=array[i+2] && array[i+2]<=array[i+1])
     7                         return true;
     8                 else
     9                         return false;
    10         } else if(i-i+1 == 2) {
    11                 if(array[i]<=array[i+1] || array[i]>=array[i+1])
    12                         return true;
    13                 else
    14                         return false;
    15         }
    16 
    17         int left=i, right=j-1;
    18         /**
    19          * 一共有四种情况:指针交叉后跳出,指针未交叉即跳出,left到达最右边,right到达最左边
    20          * 如果第二种情况成立则判定必定失败
    21          * */
    22         while(left<j) {
    23                 if(array[left]>array[j])
    24                         break;
    25                 left++;
    26         }
    27         while(right>=i) {
    28                 if(array[right]<array[j])
    29                         break;
    30                 right--;
    31         }
    32         /**
    33          * 两种特殊情况:只有左子树或者只有右子树的递归
    34          * */
    35         if(left==j || right<i)
    36                 return PostOrderCheck(array, i, j-1);
    37         /**
    38          * 另外两种跳出情况,break,此时left和right不可能重合
    39          * */
    40         if(left>right) {
    41                 /**
    42                  * 如果left比right大,说明成功交叉
    43                  * */
    44                 return PostOrderCheck(array, i, right) || PostOrderCheck(array, left, j-1);
    45         } else {
    46                 /**
    47                  * 如果left比right小,说明左子树中有元素比根节点大,或者右子树中有元素比根节点小
    48                  * */
    49                 return false;
    50         }
    51 }

     

    出题:输入一个英文句子,其中的单词以空格符号隔开;要求翻转句子中单词的顺序,但是单词内字符顺序不变(简单起见,标点符号和普通字母一样处理);

    分析:两次翻转,全局翻转(针对所有字符)和局部翻转(针对两个空格符之间的字符)

    解题:

     1 /**
     2  * 借用之前已经实现的全局翻转函数reverse
     3  * */
     4 void reverse(char* target, int length) {
     5         char temp;
     6         int i;
     7         for(i=0;i<length/2;i++) {
     8                 temp=*(target+i);
     9                 *(target+i)=*(target+(length-i-1));
    10                 *(target+(length-i-1))=temp;
    11         }
    12 }
    13 void DoubleTransfer(char *target, int length) {
    14         /**
    15          * 首先进行全局翻转,得到!tneduts a ma i
    16          * */
    17         reverse(target, length);
    18         char *part=NULL;
    19         int partLength;
    20         /**
    21          * 然后进行局部翻转,从第一个非空格符的字符开始计算
    22          * 子子序列的长度,直到第一个空格符号结束,然后
    23          * 调用reverse进行局部翻转,最后进入下一个iteration
    24          * */
    25         for(int i=0;i<length;i++) {
    26                 partLength=0;
    27                 while(target[i] == ' ' && i<length) i++;
    28                 part=target+i;
    29                 while(target[i] != ' ' && i<length) {
    30                         i++;
    31                         partLength++;
    32                 }
    33                 reverse(part, partLength);
    34         }
    35 }

     

    转载于:https://www.cnblogs.com/leo-chen-2014/p/3735575.html

    展开全文
  • 输出利用先序遍历创建的二叉树的后序遍历序列 利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的...

    输出利用先序遍历创建的二叉树的后序遍历序列

    利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#“时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树的后序遍历序列。需要注意输入数据序列中的”#“字符和非”#"字符的序列及个数关系,这会最终决定创建的二叉树的形态。

    输入

    输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串(用于创建对应的二叉树)。

    输出

    对应的二叉树的后序遍历序列。

    样例输入

    A##
    ABC####
    AB##C##
    ABCD###EF##G###
    A##B##

    样例输出

    A
    CBA
    BCA
    DCFGEBA
    A

    #include<stdio.h>
    #include<string.h>
    #include<malloc.h>
    typedef struct node
    {
    	char data;
    	struct node *lchild,*rchild;
    }Node,* pTree;
    pTree Create()
    {
        char ch;
        pTree T;
        scanf("%c",&ch);
        if(ch=='#')
    		T=NULL;
        else
       {
            T = (pTree)malloc(sizeof(Node));
            T->data = ch;
            T->lchild = Create();
            T->rchild = Create();
        }
        return T;
    }
    int t=0;
    void func(pTree T)
    {
    	if(T!=NULL)
    	{
    		func(T->lchild);
    		func(T->rchild);
    		printf("%c",T->data);
    	}
    }		
    int main()
    {
    	pTree T;
    	T=Create();
    	func(T);
    	return 0;
    }
    
    展开全文
  • 后序遍历

    2019-03-08 22:51:46
    有多组数据,每组分为两行输入,第一行表示指定二叉树的先序序列,第二行表示该二叉树的中序序列,序列元素均为大写英文字符,表示二叉树的结点。 输出描述 对于每组数组,在一行上输出该二叉树的后序序列。 ...

    题目描述

    已知某二叉树的先序序列和中序序列,编程计算并输出该二叉树的后序序列。

    输入描述

    有多组数据,每组分为两行输入,第一行表示指定二叉树的先序序列,第二行表示该二叉树的中序序列,序列元素均为大写英文字符,表示二叉树的结点。

    输出描述

    对于每组数组,在一行上输出该二叉树的后序序列。
    

    输入

    ABDGCEFH
    DGBAECHF

    输出

    GDBEHFCA
    #include<bits/stdc++.h>
    using namespace std;
    
    typedef struct Node {
        char data;
        struct Node *lchild;
        struct Node *rchild;
        Node(char ch) {
            data = ch;
            lchild = NULL;
            rchild = NULL;
        }
    } Node;
    
    
    
    void postOrder(Node *root) {
        if (root->lchild) postOrder(root->lchild);
        if (root->rchild) postOrder(root->rchild);
        cout << root->data;
    }
    
    Node *buildTree(string pre, string in) {
        int len = pre.length();
        if (len <= 0) return NULL;
        Node *root = new Node(pre[0]);
        int p = in.find(pre[0]);
        root->lchild = buildTree(pre.substr(1, p), in.substr(0, p));
        root->rchild = buildTree(pre.substr(p+1, len-p-1), in.substr(p+1, len-p-1));
        return root;
    }
    
    int main() {
        string in, pre;
        while (cin >> pre) {
            cin >> in;
            Node *root = buildTree(pre, in);
            postOrder(root);
            cout << endl;
        }
        return 0;
    }

     

    展开全文
  • #1049后序遍历

    2017-12-07 19:39:28
    题目:hihocoder #1049 输入每个测试点(输入文件)有且仅有一组测试数据。每组测试数据的第一行为一个由大写英文...输出对于每组测试数据,输出一个由大写英文字母组成的字符串,表示还原出的二叉树的后序遍历的结果

    题目:hihocoder #1049
    输入

    每个测试点(输入文件)有且仅有一组测试数据。

    每组测试数据的第一行为一个由大写英文字母组成的字符串,表示该二叉树的前序遍历的结果。

    每组测试数据的第二行为一个由大写英文字母组成的字符串,表示该二叉树的中序遍历的结果。

    对于100%的数据,满足二叉树的节点数小于等于26。

    输出

    对于每组测试数据,输出一个由大写英文字母组成的字符串,表示还原出的二叉树的后序遍历的结果。

    样例输入

    AB
    BA

    样例输出

    BA
    import java.util.Scanner;
    public class PostorderTraver {//post_order(str1, str2)=post_order(str1l, str2l)+post_order(str1r, str2r)+root
     public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
       String s1 = sc.nextLine();
       String s2 = sc.nextLine();
       System.out.println(post_order(s1,s2));
     }
      private static String post_order(String str1,String str2){//str1 先序遍历的结果 str2 中序遍历
         String res = "";
         if(str1.length() == 1){//叶子节点  l = 1
           return str1;
         }
         if(str1.length() == 0){//为空 l = 0
              return str1;
          }
          String root = "" + str1.charAt(0);
         String str1l;
         String str1r;
         String str2l;
         String str2r;
         str2l = str2.substring(0, str2.indexOf(""+str1.charAt(0)));//根据root位置切割
         str2r = str2.substring(str2.indexOf(""+str1.charAt(0))+1, str2.length());
         str1l = str1.substring(1,str2l.length()+1);//左子串
         str1r = str1.substring(str2l.length()+1,str1.length());
         res = post_order(str1l,str2l)+post_order(str1r,str2r)+root;//左 右 根
         return res;
      }
    }
    

    初次接触hihocoder,有提示,测评也很温和,不会卡过于细节的地方,评测的contest希望能坚持下来,给自己一段空闲时间挑战一下。上面的后序遍历已用java实现,希望能对有疑惑的小伙伴提供帮助。

    展开全文
  • 输出利用先序遍历创建的二叉树的后序遍历序列 1000(ms) 10000(kb) 2473 / 3692利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对...
  • 输出利用先序遍历创建的二叉树的后序遍历序列(0979)利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据...
  • 输出利用先序遍历创建的二叉树的后序遍历序列 输入 输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串(用于创建对应的二叉树)。 输出 对应的二叉树的后序遍历序列。 样例输入 A## ABC#### ...
  • 利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的...
  • 输出利用先序遍历创建的二叉树的后序遍历序列 1000(ms) 10000(kb) 利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问...
  • 输出利用先序遍历创建的二叉树的后序遍历序列 利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的...
  • 有时候做一件事不是...给出一棵二叉树,返回其节点值的后序遍历。 您在真实的面试中是否遇到过这个题?  Yes 样例 给出一棵二叉树 {1,#,2,3}, 1 \ 2 / 3 返回 [3,2,1] /**  * Defi
  • 二叉树的先序中序后序遍历 - 非递归算法(英文注释,慎点)
  • 145. Binary Tree Postorder Traversal(二叉树的后序遍历)1. 题目描述2. 递归(Recursion)2.1 解题思路2.2 实例代码3. 迭代(Iteration)3.1 解题思路3.2 实例代码 1. 题目描述 给定一个二叉树,返回它的 后序 ...
  • 二叉树的前序,中序,后序遍历规则 Tree Traversals: 前序遍历(preorder):根节点–>左子树–>右子树 中序遍历(inorder):左子树–>根节点–>右子树 后续遍历(postorder):左子树–>右子树–&...
  • BNU的基础题,数据结构的基础题,顺便搞下. 二叉树是一种常用的数据结构。我们可以用大写的英文字母表示二叉树的节点。 如下: B / \ / \ C A \ \ D 对于二叉树,有前...
  • 【Hihocoder】#1049 : 后序遍历

    千次阅读 2016-09-17 12:56:27
    题目描述: ...小Ho在这一周遇到的问题便是:给出一棵二叉树的前序和中序遍历的结果,还原这棵二叉树并输出其后序遍历的结果。...每组测试数据的第一行为一个由大写英文字母组成的字符串,表示该二叉树的前序遍历
  • 概述: ...2.Review:阅读并点评至少一篇英文技术文章 3.Tip:学习至少一个技术技巧 4.Share:分享一篇有观点和思考的技术文章 Algorithm 题目概述: Given a binary tree, return thepostor...
  • 下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出为一个整数,即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 #include<stdio.h...
  • 下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出为一个整数,即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 代码 #include&...
  • PAT 1020 Tree Traversals

    2020-06-21 10:44:39
    给定二叉树的后序遍历 和 中序遍历序列,请输出二叉树的层次遍历 注意:我们假定二叉树中节点的值都是 唯一的正整数 第一行输入为 N,第二行为后序遍历,第三行为 中序遍历 N<=30 样例 思路分析 此问题分为三...
  • 利用先序递归遍历算法创建二叉树并计算该二叉树的深度。 先序递归遍历建立二叉树的方法为: 按照先序递归遍历的思想将对二叉树结点的...最后再统计创建完成的二叉树的深度(使用二叉树的后序遍历算法)。 需要注...
  •  题目中给出一个二叉树的前序遍历和中序遍历,输出这个二叉树的后序遍历。二叉树中的结点是大写英文字母,最多有26个结点。   解题思路:  这道题涉及到一种重要的数据结构——二叉树,题目很简单,但是考查了...
  • 题目根据给出的二叉树的前序遍历和中序遍历输出后序遍历。输入每个测试点(输入文件)有且仅有一组测试数据。每组测试数据的第一行为一个由大写英文字母组成的字符串,表示该二叉树的前序遍历的结果。每组测试数据的...
  • 题目大意:给定二叉树先序和中序遍历,输出二叉树后序遍历。 方法:将英文字母映射为数字,利用数组存储,先序第一个节点是父节点,然后再从中序遍历中找到位置。注意边界。代码也很简单一次ac。 #include&lt...
  • 利用先序递归遍历算法创建二叉树并计算该...最后再统计创建完成的二叉树的深度(使用二叉树的后序遍历算法)。需要注意输入数据序列中的”#“字符和非”#"字符的序列及个数关系,这会最终决定创建的二叉树的形态。
  • 3.最后后序遍历算法统计二叉树深度 注: 1.求根节点左和右子树的深度,最后比较两者要加1 题目描述 利用先序递归遍历算法创建二叉树并计算该二叉树的深度。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想...
  • PAT A1020. Tree Traversals

    2020-02-27 10:46:03
    给出一棵二叉树的后序遍历序列和中序遍历序列,求这棵二叉树的层序遍历序列(每个结点的值均不相同)。 输入样例 假设有一棵二叉树如下: 对应该树的输入样例如下: 7 //结点个数 2 3 1 5 7 6 4 //后序遍历序列 ...
  • #1049 : 后序遍历 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Ho在这一周遇到的问题便是:给出一棵二叉树的前序和中序遍历的结果,还原这棵二叉树并输出其后序遍历的结果。 提示:分而治之——化大为...

空空如也

空空如也

1 2 3
收藏数 58
精华内容 23
关键字:

后序遍历英文