考研机试 11.二叉树遍历

时间：2021/02/25 

一.题目描述

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

输入描述

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

输出描述

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

题目链接

https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?

tpId=40&tqId=21342&rp=1&ru=%2Fta%2Fkaoyan&qru=%2Fta%2Fkaoyan%2Fquestion-ranking&tab=answerKey

二.算法

题解

首先写一个树节点的静态内部类，然后通过先序遍历创建二叉树，最后通过中序遍历输出二叉树。这里要注意在先序遍历创建二叉树时index需要是一个全局变量，这样才能保证index是递增的，否则index可能会随着递归回到上一个栈的状态。

重点

二叉树的创建及遍历

代码

import java.util.Scanner;

public class Main{

    static int index = 0;

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        while(in.hasNext()){
            String str = in.next();
            TNode root = createTree(str);

            inOrder(root);
            System.out.println();
        }
    }

    public static class TNode{

        char val;
        TNode left;
        TNode right;

        public TNode(char val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }

    public static TNode createTree(String str){

        char ch = str.charAt(index);

        if(ch == '#'){
            return null;
        }
        else{
            TNode t = new TNode(ch);
            index++;
            t.left = createTree(str);
            index++;
            t.right = createTree(str);
            return t;
        }
    }

    public static void inOrder(TNode root){

        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

}