Java实现树的遍历以及打印（递归，非递归）

import java.util.LinkedList;
import java.util.Stack;

public class BinarySearchTree1<E extends Comparable <? super E>>{

    private static class BinaryNode<E> {

        E element;
        BinaryNode<E> left;
        BinaryNode<E> right;

        BinaryNode(E theElement) {
            this(theElement, null, null);
        }

        BinaryNode(E theElement, BinaryNode<E> lt, BinaryNode<E> rt) {
            element = theElement;
            left = lt;
            right = rt;
        }

    }

    private BinaryNode<E>root;
    public void insert(E x){
        root = insert(x,root);
    }

    private BinaryNode<E> insert(E x, BinaryNode<E> t){

        if (t == null){
            return new BinaryNode<>(x,null,null);
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0){
            t.left = insert(x,t.left);
        }else if (compareResult > 0){
            t.right = insert(x,t.right);
        }else {
            ;
        }
        return t;

    }

//        前序遍历递归
    public void PreOrder(BinaryNode<E> Node){
        if (Node != null){
            System.out.print(Node.element + " ");
            PreOrder(Node.left);
            PreOrder(Node.right);
        }
    }
//        前序遍历非递归
    public void preOrder(BinaryNode<E> Node){
        if (Node == null){
            return;
        }
        Stack<BinaryNode<E>> s = new Stack<>();
        while (Node != null || !s.empty()) {
            if (Node != null) {
                System.out.print(Node.element + " ");
                s.push(Node);
                Node = Node.left;
            } else {
                Node = s.pop();
                Node = Node.right;
            }
        }
    }
//        中序遍历递归
    public void MidOrder(BinaryNode<E> Node){
        if (Node != null){
            MidOrder(Node.left);
            System.out.print(Node.element + " ");
            MidOrder(Node.right);
        }
    }
//        中序遍历非递归
    public void midOrder(BinaryNode<E> Node){
        if (Node == null){
            return;
        }
        Stack<BinaryNode<E>> s = new Stack<>();
        while (Node != null || !s.empty()){
            if (Node != null) {
                s.push(Node);
                Node = Node.left;
            }else {
                Node = s.pop();
                System.out.print(Node.element + " ");
                Node = Node.right;
            }
        }
    }
//        后序遍历递归
    public void PosOrder(BinaryNode<E> Node){
        if (Node != null){
            PosOrder(Node.left);
            PosOrder(Node.right);
            System.out.print(Node.element + " ");
        }
    }
//        后序遍历非递归
    public void posOrder(BinaryNode<E> Node){
        if (Node == null){
            return;
        }
        Stack<BinaryNode<E>> s = new Stack<>();
        BinaryNode<E> NowNode;
        BinaryNode<E> BefNode;
        NowNode = Node;
        BefNode = Node;
        //把NowNode移到左子树下边
        while (NowNode != null){
            s.push(NowNode);
            NowNode = NowNode.left;
        }
        while (s != null){
            NowNode = s.pop();
            //无右子树或右子树已被访问
            if (NowNode.right != null && NowNode.right != BefNode){
                s.push(NowNode);
                NowNode = NowNode.left;
                if (NowNode != null){
                    s.push(NowNode);
                    NowNode = NowNode.left;
                }
            }else {
                System.out.print(NowNode.element + " ");
                BefNode = NowNode;
            }
        }
    }
//        层序遍历队列
    public void levelOrder(BinaryNode<E> Node){
        LinkedList<BinaryNode<E>> list = new LinkedList<>();
        list.add(Node);
        while (!list.isEmpty()){
            Node = list.poll();
            System.out.print(Node.element + " ");
            if (Node.left != null){
                list.offer(Node.left);
            }
            if (Node.right != null){
                list.offer(Node.right);
            }
        }

    }

    //    树的深度
    public int Depth(BinaryNode<E> Node){

        if (Node == null){
            return 0;
        }
        int l = Depth(Node.left);
        int r = Depth(Node.right);
        if (l > r){
            return l+1;
        }else {
            return r+1;
        }

    }

    //    桉树状打印二叉树
    public void PrintTree(BinaryNode<E> Node,int high){
        if (Node == null){
            return;
        }
        PrintTree(Node.right,high+1);
        for (int i = 0 ; i < high ; i++) {
            System.out.print(" ");
        }
            System.out.println(Node.element + " ");
            PrintTree(Node.left,high+1);
    }

    public static void main(String[] args) {
        int [] input = {4,2,6,1,3,5,7,8,10};
        BinarySearchTree1<Integer> tree = new BinarySearchTree1<>();
        for (int i = 0 ; i < input.length ; i++){
            tree.insert(input[i]);
        }
        System.out.print("递归前序遍历：  ");
        tree.PreOrder(tree.root);
        System.out.println();
        System.out.print("非递归前序遍历：");
        tree.preOrder(tree.root);
        System.out.println();
        System.out.print("递归中序遍历：  ");
        tree.MidOrder(tree.root);
        System.out.println();
        System.out.print("非递归中序遍历：");
        tree.midOrder(tree.root);
        System.out.println();
        System.out.print("递归后序遍历：  ");
        tree.PosOrder(tree.root);
        System.out.println();
//        System.out.print("非递归后序遍历：");
//        tree.posOrder(tree.root);
//        System.out.println();
        System.out.print("队列层序遍历：  ");
        tree.levelOrder(tree.root);
        System.out.println();
        tree.PrintTree(tree.root,tree.Depth(tree.root));
    }

}