[数据结构与算法]数据结构之二叉树遍历，非递归算法（Java实现）

public class Sqstack {
    public String data;
    public TowTree next;
    public Sqstack(){
        this.data=null;
        this.next=null;
    }
    public boolean EmpatyStack(Sqstack S){
        if(S.next==null){
            return true;
        }
        return false;
    }
}

public class TowTree {
    String data;
    TowTree lift;
    TowTree right;
    TowTree next;
    TowTree(){
        this.data=null;
        this.lift=this.right=null;
        this.next=null;
    }
/*二叉树例
                A
             B     C
           D   E F   G
输入序列：ABD00E00CF00G00
 */
    public static void main(String[] args) {
        //ABD000C0E00
        TowTree T = new TowTree();
        CreateBiTree(T);
        System.out.println("先序遍历");
        PreOrder(T);
        System.out.println();
        System.out.println("中序遍历");
        InOrder(T);
        System.out.println();
        System.out.println("后序遍历");
        PostOrder(T);
    }
    //先序方式创建二叉树
    public static void CreateBiTree(TowTree T){
        Scanner sc= new Scanner(System.in);
        System.out.println("输入：");
        String x=sc.next();
        //以0表示空结点
        if(x.equals("0")){
            T=null;
        }
        if(T!=null){
            T.data=x;
            TowTree Tl=new TowTree();
            T.lift=Tl;
            TowTree Tr=new TowTree();
            T.right=Tr;
            CreateBiTree(T.lift);
            CreateBiTree(T.right);
        }
    }
    //中序遍历
    public static void InOrder(TowTree T){
        Sqstack S = new Sqstack();
        while (T!=null || !S.EmpatyStack(S)){
            if(T!=null){
                T.next=S.next;
                S.next=T;
                T=T.lift;
            }else {
                if( S.next.data!=null){
                    System.out.print(S.next.data);
                }

                T=S.next.right;
                S.next=S.next.next;
            }
        }
    }
    //先序遍历
    public static void PreOrder(TowTree T){
        Sqstack S = new Sqstack();
        while (T!=null || !S.EmpatyStack(S)){
            if(T!=null){
                if (T.data!=null){
                    System.out.print(T.data);
                }

                T.next=S.next;
                S.next=T;
                T=T.lift;
            }else {


                T=S.next.right;
                S.next=S.next.next;
            }
        }
    }
    //后序遍历
    public static void PostOrder(TowTree T1){
        Sqstack S = new Sqstack();
        TowTree T = new TowTree();
        TowTree t = new TowTree();
        T=T1;
        while (T!=null || !S.EmpatyStack(S)){
            if(T!=null){//从根节点访问左孩子，一直到最左
                T.next=S.next;
                S.next=T;
                T=T.lift;
            }else {
                T=S.next;
                //是否存在右孩子且没有被访问
                if(T.right!=null && T.right!=t){
                    //向右
                    T=T.right;
                }else {
                    //该结点不存在右孩子或右孩子被访问过
                    T=null;
                    //读出栈顶元素
                    if(S.next.data!=null){
                        System.out.print(S.next.data);
                    }
                    //记录最近访问过的结点
                    t=S.next;
                    //出栈
                    S.next=S.next.next;
                }
            }
        }
    }
}