首页 > 试题广场 >

二叉树遍历

[编程题]二叉树遍历

热度指数：56107 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

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

输出

c b e g d f a

算法知识视频讲解

Java

牛客274406799号

不去模拟二叉树
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == '#') {
                ch[i] = '1';
                while (i >= 0 && ch[i] == '1') {
                    i--;
                }
                if (i >= 0) {
                    System.out.printf("%c ",ch[i]);
                    ch[i] = '1';
                }else {
                    i = 0;
                }
            }
        }
    }
}

编辑于 2024-01-29 15:55:28 回复(0)

Java

愛夜

import java.util.Scanner;

class TreeNode {

public char val;

public TreeNode left;

public TreeNode right;

public TreeNode(char val) {

this.val = val;

}

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNextLine()) {

Main a=new Main();

String str=in.nextLine();

TreeNode root=a.createTree(str);

a.inOrder(root);

}

public int i=0;

public TreeNode createTree(String s){

TreeNode root=null;

if(s.charAt(i)!='#'){

root=new TreeNode(s.charAt(i));

i++;

root.left=createTree(s);

root.right=createTree(s);

}else{

i++;

}

return root;

}

public void inOrder(TreeNode root){

if(root==null){

return;

}

inOrder(root.left);

System.out.print(root.val+" ");

inOrder(root.right);

}

发表于 2022-09-30 08:39:47 回复(0)

Java

会越来越强的哒哒

import java.util.*;
class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        
        public TreeNode(char val) {
            this.val = val;
        }
}

public class Main {
    public static int i = 0;
    public static TreeNode CreateBinaryTree(String str) {
        if(str==null) {
            return null;
        }
        TreeNode root = new TreeNode(str.charAt(i));
        i++;
        if(root.val!='#') {
            if(root.left==null) {
                root.left = CreateBinaryTree(str);
             }
             if(root.right==null) {
                root.right =CreateBinaryTree(str);
             }
        }
        return root;
    }
    public static void inOrder(TreeNode root) {
        if(null == root) {
            return;
        }
        inOrder(root.left);
        if(root.val!='#') {
            System.out.print(root.val+" ");
        }
        inOrder(root.right);
    }
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextLine()) {
            String s = scanner.nextLine();
            TreeNode treenode = CreateBinaryTree(s);
            inOrder(treenode);
        }
}
}

发表于 2022-07-14 16:34:30 回复(0)

Java

cxzO_o

import java.util.*;

class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(char val){
        this.val=val;
    }
}

public class Main{
    public static int i=0;
    
    public static TreeNode createTree(String str){
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else{
            i++;
        }
        return root;
    }
    
    public static void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNextLine()){
            String str=scanner.nextLine();
            TreeNode root=createTree(str);
            inOrder(root);
        }
    }
}

发表于 2022-05-20 18:55:49 回复(0)

Java

许七安X

发表于 2022-02-13 19:35:15 回复(0)

Java

无忧♜

import java.util.*;
class TreeNode{
    public char val;
    public TreeNode left;//二叉树的左孩子
    public TreeNode right;//二叉树的右孩子

    public TreeNode(char val) {
        this.val = val;
    }
}
public class Main {
    
    public static int i = 0;
    public static TreeNode createTree(String str){
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            //所给字符串为先序遍历，顺序为根->左->右
            root.left = createTree(str);
            root.right = createTree(str);
        }else{
            //能走到这一步，说明下一个数为空
            i++;
        }
        return root;
    }
    
    public static void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inOrder(root);
        }
    }
}

发表于 2022-02-11 17:29:47 回复(0)

Java

bswaterb

此题最大的难点就在于如何把题目所给的 abc##de#g##f###转换为对应的二叉树，这个步骤涉及到一种经典算法，没接触过的 coder 理解模板代码即可（模板不唯一，但思想大致相同）

private static int index = 0;
private static Tree createTree(String str){
        if(index >= str.length() || str.charAt(index)=='#') {
            index++;
            return null;
        }
        Tree treeNode = new Tree(str.charAt(index++));
        treeNode.left = createTree(str);
        treeNode.right = createTree(str);
        return treeNode;
    }

tips:
部分 coder 初次接触时可能会有疑问：为什么仅凭前序遍历序列就能确定对应的二叉树呢？其实是因为此类前序序列以 '#' 的形式给出了空结点所在的位置，因此可以唯一确定此树形态，若缺少空结点的信息，则单个遍历序列不能唯一确定一颗二叉树，需以前+中，或中+后，或其他组合才能唯一确定树的形态。

当确定出树的结构后，进行简单的中序遍历即可得出答案。

private static void inorderPrintTree(Tree tree){
        if(tree==null) return;
        inorderPrintTree(tree.left);
        System.out.print(tree.value+" ");
        inorderPrintTree(tree.right);
    }

以下是完整代码

import java.util.*;
public class Main {
    static class Tree{
        Tree left;
        Tree right;
        char value;
        Tree(char value){this.value = value;}
    }
    private static int index = 0;

    private static Tree createTree(String str){
        if(index >= str.length() || str.charAt(index)=='#') {
            index++;
            return null;
        }
        Tree treeNode = new Tree(str.charAt(index++));
        treeNode.left = createTree(str);
        treeNode.right = createTree(str);
        return treeNode;
    }

    private static void inorderPrintTree(Tree tree){
        if(tree==null) return;
        inorderPrintTree(tree.left);
        System.out.print(tree.value+" ");
        inorderPrintTree(tree.right);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str = in.next();
            Tree root = createTree(str);
            inorderPrintTree(root);
        }
    }
}

发表于 2022-01-18 11:27:02 回复(0)

Java

热火

import java.util.*;


class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(char val){
        this.val=val;
    }
}

public class Main{
      public static int i=0;
    public static TreeNode createTree(String str){
        if(str==null) return null;
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else{
            i++;
        }
        return root;
    }
    
    
    public static void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
        
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
       TreeNode root= createTree(str);
        inorder(root);
    }
}

发表于 2021-12-20 22:08:09 回复(0)

Java

牛客161939620号

import java.util.*;
public class Main {

    // 树节点结构
    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        
        public TreeNode() {
            super();
        }
        
        public TreeNode(char val) {
            this.val = val;
        }
    }
    
    static int p = 0;   // 指向字符串参数的当前字符

    // 递归终止条件不再是 root == null, 而变为 str.charAt(p) = '#'
    private static TreeNode createTree(String str) {
        if(str == null || str.length() == 0)
            return null;
        char val = str.charAt(p);
        p++;
        if(val == '#') {
            return null;
        }

        TreeNode root = new TreeNode(val);
        root.left = createTree(str);
        root.right = createTree(str);
        return root;
    }
    
    
    public static void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        TreeNode root = createTree(str);
        inOrder(root);
        
    }
}

发表于 2021-10-11 11:05:13 回复(0)

Java

赢锋尹

import java.util.Scanner;

class TreeNode {//定义节点
    public char val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(char val) {//提供构造方法
        this.val = val;
    }
}

public class Main{
    public static int i = 0;
    
    //这个函数的步骤是：先根，再左，再右
    public static TreeNode creatTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {//创建的i下标的元素不为#
            root = new TreeNode(str.charAt(i));//new一个不为#的，前进过程中每一个节点都是根
            i++;
            root.left = creatTree(str);
            root.right = creatTree(str);
        }else {//创建的i下标的元素为#
            i++;
        }
        return root;
    }
    
    public static void inorder(TreeNode root) {//中序遍历
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);//注意在上面导入包
        String str = scanner.nextLine();
        TreeNode root = creatTree(str);//定义一个root节点
        inorder(root);//用中序遍历把结果输出
    }
}

发表于 2021-05-15 11:16:57 回复(0)

Java

我想请你睡午觉

import java.util.Scanner;
class Node{
    char val;
    Node left;
    Node right;
    Node(char val){ this.val = val;}
}

public class Main{
    private static int index = 0;
    //用来建立树的函数
    public static Node buildTree(String input){
        if(input.charAt(index) == '#'){
            index++;
            return null;
        }
        Node node = new Node(input.charAt(index));
        index++;
        node.left = buildTree(input);
        node.right = buildTree(input);
        return node;
    }
    //中序遍历二叉树的代码
    public static void inOrder(Node root){
        if(root != null){
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextLine()){
            String input = scanner.nextLine();
            index = 0;
            Node root = buildTree(input);
            inOrder(root);
        }
        
    }
}

发表于 2020-04-24 12:04:04 回复(0)

Java

成程晨

import java.util.*;
public class Main{
    private static List<Character> l = new ArrayList<>();
    public static int index = 1;
    private static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            char[] a = in.nextLine().toCharArray();
            TreeNode root = new TreeNode(a[0]);
            generateTree(a,root);
            inOrder(root);
            for(int i = 0;i < l.size();i++){
                System.out.print(l.get(i) + " ");
            }
            System.out.println();
        }
    }
    public static void generateTree(char[] a,TreeNode r){
        if(r.val != '#'){
            r.left = new TreeNode(a[index++]);
            generateTree(a,r.left);
            r.right = new TreeNode(a[index++]);
            generateTree(a,r.right);
        }
    }
    public static void inOrder(TreeNode r){
        if(r.val == '#') return;
        inOrder(r.left);
        l.add(r.val);
        inOrder(r.right);
    }
}

发表于 2019-01-13 22:43:16 回复(0)

Java

中南的小菜鸡

//鄙人之见，一个栈可以做到。将输入转为字符数组，依次push入栈，遇到字符#不push而是pop
//结果恰为中序遍历


import java.util.Scanner;

import java.util.Stack;



public class Main{

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){

            char[] ch = sc.nextLine().toCharArray();

            Stack<Character> st = new Stack<>();

            st.push(ch[0]);

            for(int i=1;i<ch.length-1;i++){

                if(ch[i] == '#'){

                    System.out.print(st.pop()+" ");

                }else{

                        st.push(ch[i]);

                }

            }

            System.out.println();

        }

    }

}

发表于 2018-08-05 01:17:56 回复(2)

Java

/xinCupid☆

不用建树，直接用两个栈就可，思路类似于中缀表达式

import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        while (in.hasNext()) {
            Stack<Character> st = new Stack<Character>();
            Stack<Character> symbol = new Stack<Character>();
            String line = in.nextLine();
            for (int i = 0; i < line.length(); ++i) {
                if (!(line.charAt(i) == '#')) {
                    while (symbol.size() > 0) {
                        symbol.pop();
                        System.out.print(st.peek() + " ");
                        st.pop();
                    }
                    st.push(line.charAt(i));
                } else {
                    symbol.push(line.charAt(i));
                }
            }
            while (st.size() > 0) {
                System.out.print(st.peek() + " ");
                st.pop();
            }
        }
    }
}

发表于 2018-03-23 22:49:33 回复(1)