精华内容
参与话题
问答
  • 一串字符串:ABC空格空格DE空格GF空格空格空格 用先序创建二叉树。 ``` #include #include #define maxsize 100 //递归法创建二叉树 //规则:对一串字符串挨个读取遇到空格完成对当前树的创建 typedef struct ...
  • 题目描述编一个程序,读入用户输入的一串先序遍历字符串根据字符串建立一个二叉树(以指针方式存储)。例如如下的先序遍历字符串:ABC##DE#G##F###其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后...

    题目描述

    编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。例如如下的先序遍历字符串:ABC##DE#G##F###其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

    输入描述:

    输入包括1行字符串,长度不超过100。

    输出描述:

    可能有多组测试数据,对于每组数据,
    输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。
    每个输出结果占一行。
    示例1

    输入

    abc##de#g##f###
    

    输出

    c b e g d f a 
    

    代码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define N 101
     
    struct Node{
        Node *lchild;
        Node *rchild;
        char c;
    };
     
    Node *CreateNode()//创建新节点,返回结点指针
    {
        Node *ret=(Node*)malloc(sizeof(Node));
        ret->lchild=NULL;
        ret->rchild=NULL;
        return ret;
    }
     
    void InOrder(Node *T)//中序遍历
    {
        if(T->lchild!=NULL) 
    		InOrder(T->lchild);
        printf("%c ", T->c);
        if(T->rchild!=NULL)
    		InOrder(T->rchild);
    }
    
    void Del(Node *T)//删除树
    {
        if(T->lchild!=NULL)//删除左子树
        {
            Del(T->lchild);
            T->lchild=NULL;
        }
        if(T->rchild!=NULL)//删除右子树
        {
            Del(T->rchild);
            T->rchild=NULL;
        }
        free(T);//删除根节点
    }
     
    unsigned pos;//标记字符串处理到哪了
    char str[N];//读取的字符串
     
    Node *BuildTree()//根据字符串创立二叉树,并返回根节点指针
    {
        if(pos>=strlen(str)) 
    		return NULL;//字符串处理完了就歇着吧
        if(str[pos]=='#')//创建空树,即返回空指针
        {
            pos++;//准备处理下一个字符
            return NULL;
        }
        Node *p=CreateNode();//创建一个空节点
        p->c=str[pos++];//先序,先获取根节点的字符信息
        p->lchild=BuildTree();//创建左子树
        p->rchild=BuildTree();//创建右子树
        return p;//完事,返回根节点指针
    }
     
    int main()
    {
        while(gets(str))
        {
            pos=0;//标记字符串处理到哪了
            Node *T=BuildTree();//根据字符串构建整棵树
            InOrder(T);//中序遍历并输出
            printf("\n");
        }
    }


    展开全文
  • 你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。 空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 示例 1: 输入: ...

    https://leetcode-cn.com/problems/construct-string-from-binary-tree/
    你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。

    空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
    示例 1:

    输入: 二叉树: [1,2,3,4]
           1
         /   \
        2     3
       /    
      4     
    
    输出: "1(2(4))(3)"
    
    解释: 原本将是“1(2(4)())(3())”,
    在你省略所有不必要的空括号对之后,
    它将是“1(2(4))(3)”。
    

    示例 2:

    输入: 二叉树: [1,2,3,null,4]
           1
         /   \
        2     3
         \  
          4 
    
    输出: "1(2()(4))(3)"
    
    解释: 和第一个示例相似,
    除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
    
    /* 思路
    根据示例,可知左右子树前后有括号,如果左子树为空且右子树不为空,则需拼接(); 
    如果右子树为空,则不拼接,如果左右子树都为空,则不拼接左右子树的();
    
    注意: 拼接使用strcat, 不能用snprintf,原因snprintf拼接自身时不安全,需建立缓冲区。
    */
    
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
    
    void get_len(struct TreeNode* t, int *len){
        if(!t){ return;} 
        
        char tmp[20] = {0};
        snprintf(tmp, 20, "%d", t->val);
        *len += strlen(tmp);
       
        if(NULL != t->left){
            *len += 2;
            get_len(t->left, len);
        }
        if(NULL == t->left && NULL != t->right){ *len += 2;}
        if(NULL != t->right){
            *len += 2;
            get_len(t->right, len);
        }
    }
    
    
    void traversing(struct TreeNode* t, char *ret){
        if(!t){
            return;
        } 
        
        char tmp[20] = {0};
        snprintf(tmp, 20, "%d", t->val);
        strcat(ret,tmp);
        
        if(NULL != t->left){
            strcat(ret, "(");
            traversing(t->left, ret);
            strcat(ret, ")");
        }
        if(NULL == t->left && NULL != t->right){
            strcat(ret, "()");
        }
        if(NULL != t->right){
            strcat(ret, "(");
            traversing(t->right, ret);
            strcat(ret, ")");
        }
    }
    
    char * tree2str(struct TreeNode* t){
        int len = 0;
        get_len(t, &len); // 获取组成的字符串长度
        
        char *ret = (char *)calloc(len + 1, sizeof(char));
        traversing(t, ret);  // 根据长度开空间,并拼接字符串
         
        return ret;
    }
    
    
    展开全文
  • LintCode880—字符串创建二叉树(C++) <第一次记录代码,如有错误欢迎指正> 你需要根据一个由括号和整数组成的字符串中构造一颗二叉树。 输入的整个字符串表示一个二叉树。它包含一个整数,以及其后跟随的0~2...

    LintCode880—字符串创建二叉树(C++)

    <第一次记录代码,如有错误欢迎指正>

    你需要根据一个由括号和整数组成的字符串中构造一颗二叉树。
    输入的整个字符串表示一个二叉树。它包含一个整数,以及其后跟随的0~2对括号。该整数表示根的值,而一对括号里的字符串代表一个具有相同结构的子二叉树。
    如果一个节点含有子节点,你应该先构造它的左子节点。
    /*
    你需要根据一个由括号和整数组成的字符串中构造一颗二叉树。

    输入的整个字符串表示一个二叉树。它包含一个整数,以及其后跟随的0~2对括号。
    该整数表示根的值,而一对括号里的字符串代表一个具有相同结构的子二叉树。

    如果一个节点含有子节点,你应该先构造它的左子节点。

    样例
    样例1:

    输入: -4(2(3)(1))(6(5))
    输出: -4,2,6,3,1,5
    说明:
    输出应该如下所示:
    -4
    /
    2 6
    / \ /
    3 1 5

    样例2:

    输入: 1(-1)
    输出: 1,-1
    说明:
    输出应该如下所示:
    1
    /
    -1
    注意事项
    在输入字符串中只有’(’,’)’,’-‘和’0’ ~ ‘9’。
    空树表示为" “而不是”( )"。

    */

    /**
     * Definition of TreeNode:
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode *left, *right;
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = this->right = NULL;
     *     }
     * }
     */
    
    class Solution {
    public:
        /**
         * @param s: a string
         * @return: a root of this tree
         */
         /*将字符串分解为一个整数,两个子字符串*/
        void split(string str, int &num, string &sstr1, string &sstr2)
    	{
    		if (str == "")
    			return;
    
    		int k = 0;//记录第一个“(”的位置
    
    		while (str[k] != '('&&k<str.length())
    		{
    			k++;
    		}
    		string first = str.substr(0, k);
    		num = stoi(first);
    		
    		str.erase(str.begin(), str.begin() + k);
    		if (str.empty())		   //判断是否只有数字
    		{
    			sstr1 = "";
    			sstr2 = "";
    			return;
    		}
    
    		stack<char>sta;
    		int L,R; //记录每一个字串的左右括号位置
    		for (int i = 0; i < str.length(); i++)
    		{
    			if (str[i] == '(')
    			{
    				sta.push(str[i]);
    				if (sta.size() == 1)
    					L = i;		   //每个字串的第一个位置
    			}
    			if (str[i] == ')')
    			{
    				sta.pop();
    				if (sta.empty())
    				{
    					R = i;			  //记录每个字串的最后一个位置
    					if (sstr1 == "")//先保存左子树
    						sstr1 = str.substr(L+1, R - L-1);
    					else if (sstr2 =="")
    						sstr2 = str.substr(L + 1, R - L - 1);
    				}
    					
    			}
    		}
    	}
    
        
        TreeNode * str2tree(string &s) {
            // write your code here
           if (s.empty())//递归边界条件
    			return nullptr;
    		TreeNode*tree;
    		int num;
    		string sstr1, sstr2;
    		split(s, num, sstr1, sstr2);
    		tree = new TreeNode(num);//创建根节点
    		TreeNode*left=str2tree(sstr1);//递归创建左子树
    		TreeNode*right = str2tree(sstr2);//递归创建右子树
    		tree->left = left;
    		tree->right = right;
    		return tree;
        }
    };
    
    展开全文
  • 编一个程序,读入用户输入的一串先序遍历字符串根据字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再...

    题目网址:https://www.nowcoder.com/questionTerminal/4b91205483694f449f94c179883c1fef

    编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
    例如

    输入:abc##de#g##f###
    输出:c b e g d f a

    其中空格字符串表示空树


    其实这题的意思就是给你一棵二叉树先序遍历的结果,然后建立一个二叉树,再输出它中序的遍历结果。
    如果只给我们一个先序的遍历结果,我们是无法建立起这棵树,
    如何才能建立一棵树

    • 给中序遍历结果和先序遍历结果
    • 给中序遍历结果和后序遍历结果

    但这题有点特殊,因为它用 # 代表了空树就可以建立起这颗树了
    以题目的例子

    abc##de#g##f###
    用这个字符串还原一棵树,也是先序遍历,再递归创建左子树,递归创建右子树
    这个例子:a为根节点,递归左子树,b为左子树根节点,再递归左子树,从为根节点……
    这个过程自己试一下就会,就根先序遍历一颗树是一样的。

    package package11_10;
    
    import java.util.Scanner;
    
    public class Test11_10 {
        static class TreeNode{
            public char val;
            public TreeNode left;
            public TreeNode right;
    
            public TreeNode(char val) {
                this.val = val;
            }
        }
        static int index = 0;
        public static TreeNode buildTree(String line){
            index = 0;
            return createTreePrevOrder(line);
        }
        public static TreeNode createTreePrevOrder(String line){
            char c = line.charAt(index);
            if(c == '#'){
                return null;
            }
            TreeNode root = new TreeNode(c);
            index++;
            root.left = createTreePrevOrder(line);
            index++;
            root.right = createTreePrevOrder(line);
            return root;
        }
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext()){
                String line = scanner.next();
                TreeNode root = buildTree(line);
                inOrder(root);
            }
        }
        public static void inOrder(TreeNode root){
            if(root == null){
                return;
            }
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }
    }
    
    

    记住在这种在线OJ做题目,很多都是没有代码框架的,就需要自己写,我将这个代码分为4个主要部分

    1. main方法,系统输入字符串,我们创建树,输出中序结果
    2. 创建树,buildTree,这里用了下标index来记录我们遍历到哪个字符了,每次调用到这个方法,index都要初始化为0
    3. 根据先序字符串结果创建左子树,这是需要递归的
    4. 中序遍历这棵创建好的树

    这道题的核心思路是递归遍历字符串创建一颗小树(只有三个节点的小树)
    每递归一次,index++指向后面的那个字符,以那个字符为根节点,有两个分支,两个分支为左右子树,再依次递归遍历。在这里插入图片描述

    展开全文
  • 题目网址:...你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * ...
  • 举例来说,二叉树[root,left,right],则转换为root(left)(right)。如果只有left为空节点,则输出root()(right);如果只有right为空节点则可以忽略右节点的(),输出为root(left)。 //涉及的知识点是二叉树的递归遍历...
  • 你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。 空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 示例 1: 输入: ...
  • 一、题目描述 You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair ...
  • 606. 根据二叉树创建字符串

    千次阅读 2019-05-26 07:12:04
    你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。 空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。 示例 1: 输入: ...

空空如也

1 2 3 4 5 ... 13
收藏数 250
精华内容 100
关键字:

根据字符串创建二叉树