KY11 二叉树遍历

import java.util.*;
public class Main {
    //输入的是一串先序遍历的字符串，根据此字符串建立二叉树，然后在对二叉树输出中序遍历结果
    //1.先定义一下二叉树类
     public static class BTNode{
        char val;
        BTNode left;
        BTNode right;
        public BTNode(char val){
            this.val=val;
        }
    }
    //2.创建二叉树---输入先序遍历字符串
    int index=0;//这里全局变量是为了避免creatTree方法中出现形参值传递不改变实参的现象
    public BTNode creatTree(String s,char inVal){
        BTNode treeNode=null;//先有一个二叉树
        if(index<s.length()&&s.charAt(index)!=inVal){//说明这个结点存在且是合法的值
            //2.1 在二叉树中放入根节点
            treeNode=new BTNode(s.charAt(index));//把参数传进来，进行构造
            //2.2 在二叉树中放入左子树,递归调用，左子树也是下一层的根节点
            ++index;
            treeNode.left=creatTree(s,inVal);
            //2.3 在二叉树中放入右子树,递归调用，右子树也是下一层的根节点
            ++index;
            treeNode.right=creatTree(s,inVal);
        }
        return treeNode;
    }
    //3.实现中序遍历
    public void InOrder(BTNode treeNode){
        //左右根
        if(treeNode!=null){
            InOrder(treeNode.left);
            System.out.print(treeNode.val+" ");
            InOrder(treeNode.right);
        }
    }
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String s=sc.nextLine();
            Main tree=new Main();
            BTNode root=tree.creatTree(s,'#');
            tree.InOrder(root);
        }
        sc.close();
    }
}