【数据结构】二叉树遍历（Java实现）

怼烎@ 2023-07-19 05:45 15阅读 0赞

## 题目描述 ##

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

**题目链接：**[https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking][https_www.nowcoder.com_practice_4b91205483694f449f94c179883c1fef_tpId_60_tqId_29483_rp_1_ru_activity_oj_qru_ta_tsing-kaoyan_question-ranking]

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

**输出描述:**

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

示例1

**输入：abc\#\#de\#g\#\#f\#\#\#**

**输出：c b e g d f a**

**方法1：**

利用输入的数组构建一颗二叉树，然后进行中序遍历；构建二叉树利用的是先序遍历的思想

代码如下：

import java.util.*;
    
    
    public class Main{
    
       static int i=0;
        //中序遍历
        public static void inorder(Node root){
            if(root==null){
                return;
            }
            inorder(root.left);
            System.out.printf("%c ",root.value);
            inorder(root.right);
        }
        //建树
        public static Node build(String str){
            Node root=null;
            if(str.charAt(i)!='#'){
                root=new Node(str.charAt(i));
                i++;
                root.left=build(str);
                root.right=build(str);
            }
            else{
                i++;
            }
            return root;
        }
    }

**提示：打印出来的结果中间有空格**

**方法2：**

利用栈，将输入的字符串转换为字符数组，然后把字符放入栈中，如果遇到‘\#’就不放入，把栈顶元素弹出，打印出来的顺序就是中序遍历（参照大佬的想法）

代码：

import java.util.*;
    
    public class Main{
        public static void main(String[] args) {
            Scanner scanner=new Scanner(System.in);
            while(scanner.hasNext()){
                char [] array= scanner.nextLine().toCharArray();
                Stack<Character> stack=new Stack<>();
                stack.push(array[0]);
                for(int i=1;i<array.length-1;i++){
                    if(array[i]=='#'){
                        System.out.print(stack.pop()+" ");
                    }
                    else{
                        stack.push(array[i]);
                    }
                }
            }
        }
    }

[https_www.nowcoder.com_practice_4b91205483694f449f94c179883c1fef_tpId_60_tqId_29483_rp_1_ru_activity_oj_qru_ta_tsing-kaoyan_question-ranking]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking