package com.wyy.test;

import java.util.Stack;


public class TransverseTreeWithoutDGTest {
    public static void main(String[] args){
        Tree tree = new Tree();
        tree.insert("A", 30);
        tree.insert("B", 42);
        tree.insert("C", 19);
        tree.insert("D", 22);
        tree.insert("E", 33);
        tree.insert("F", 45);
        tree.insert("G", 20);
        tree.preOrder(tree.root);
        System.out.println();
        tree.midOrder(tree.root);
        System.out.println();
        tree.lastOrder(tree.root);
        System.out.println();
        System.out.println("----------------------------");
        Tree.postOrderWithStack(tree.root);
    }
}
class Node{
    public String name;
    public int count;
    public Node leftChild;
    public Node rightChild;
    public Node(String name,int count){
        this.name = name;
        this.count = count;
    }
}
class Tree{
    public Node root;
    public Tree(){
        root = null;
    }
    public void insert(String name,int count){
        Node newNode = new Node(name,count);
        if(root==null)
            root = newNode;
        else{
            Node current = root;
            Node parent;
            while(true){
                parent = current;
                if(count<current.count){
                    current = current.leftChild;
                    if(current==null){
                        parent.leftChild = newNode;
                        return;
                    }
                }
                else if(count>current.count){
                    current = current.rightChild;
                    if(current==null){
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }
    public Node find(int key){
        Node current = root;
        while(true){
            if(current==null)
                return null;
            if(key==current.count)
                return current;
            else if(key<current.count){
                current = current.leftChild;
            }
            else if(key>current.count){
                current = current.rightChild;
            }
        }
    }
    public void preOrder(Node node){
        if(node!=null){
            System.out.print(node.name);
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }
    public void midOrder(Node node){
        if(node!=null){
            midOrder(node.leftChild);
            System.out.print(node.name);
            midOrder(node.rightChild);
        }
    }
    public void lastOrder(Node node){
        if(node!=null){
            lastOrder(node.leftChild);
            lastOrder(node.rightChild);
            System.out.print(node.name);
        }
    }
    
    public void preOrderWithStack(Node node){
        Stack<Node> s = new Stack<Node>();
        Node current = node;
        while(current!=null||!s.isEmpty()){
            while(current!=null){
                System.out.print(current.name+" ");
                if(current.rightChild!=null){
                    s.push(current.rightChild);
                }
                current = current.leftChild;
            }
            if(!s.isEmpty()){
                current = s.pop();
            }
        }
        
    }
    public void inOrderWithStack(Node node){
        Node current = node;
        Stack<Node> s = new Stack<Node>();
        while(current!=null||!s.isEmpty()){
            while(current!=null){
                s.push(current);
                current = current.leftChild;
            }
            if(!s.isEmpty()){
                current = s.pop();
                System.out.print(current.name+" ");
                current = current.rightChild;
            }
        }
    }
    public static void postOrderWithStack(Node node){
        Node current;
        Node pre = null;
        Stack<Node> s= new Stack<Node>();
        s.push(node);
        while(!s.isEmpty()){
            current = s.peek();
            if((current.leftChild==null&&current.rightChild==null)||(pre!=null&&(pre==current.leftChild||pre==current.rightChild))){
                System.out.print(s.pop().name);//如果节点的左右子节点都为null 或者都被遍历过则可以访问
                pre = current;
            }else{
                if(current.rightChild!=null)
                    s.push(current.rightChild);
                if(current.leftChild!=null)
                    s.push(current.leftChild);
                
            }
            
        }
        
    }
    

}