排序二叉树的遍历

所谓排序二叉树是指树中的每个节点大于其左子节点，小于其左子节点。
排序二叉树的遍历大体上可以分为三种，分别是前序遍历、中序遍历和后续遍历

• 前序遍历：先父节点，然后再左右子节点
• 中序遍历：先左子节点，然后父节点，最后右子节点
• 后续遍历：先左右子节点，然后再父节点
  实现三种遍历的核心思想是采用递归。

代码实现：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
    
    private static class BinaryNode<AnyType>{
        AnyType element;
        BinaryNode<AnyType> left;
        BinaryNode<AnyType> right;
        BinaryNode(AnyType theElement){
            this(theElement,null,null);
        }
        BinaryNode(AnyType theElement, BinaryNode<AnyType>lt, BinaryNode<AnyType> rt){
            element = theElement;
            left =lt;
            right =rt;
        }
        
    }
    private BinaryNode<AnyType> root;
    public void insert(AnyType x){
        root = insert(x,root);
    }
    public boolean isEmpty(){
        return root==null;
    }
    public BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> 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<AnyType>Node){
        if(Node!=null){
            System.out.print(Node.element+" ");
            preOrder(Node.left);
            preOrder(Node.right);
        }
    }
    /*中序遍历*/
    public void midOrder(BinaryNode<AnyType>Node){
        if(Node!=null){
            midOrder(Node.left);
            System.out.print(Node.element +" ");
            midOrder(Node.right);
        }
    }
    /*后续遍历*/
    public void postOrder(BinaryNode<AnyType>Node){
        if(Node!=null){
            postOrder(Node.left);
            postOrder(Node.right);
            System.out.print(Node.element+" ");
        }
    }
       /*按层遍历*/
     public void levelOrder(BinaryNode<AnyType> Node) {
            if (Node == null) {
                return;
            }

            int depth = depth(Node);

            for (int i = 1; i <= depth; i++) {
                levelOrder(Node, i);
            }
        }
    
     private void levelOrder(BinaryNode<AnyType> Node, int level) {
            if (Node == null || level < 1) {
                return;
            }
            if (level == 1) {
                System.out.print(Node.element + "  ");
                return;
            }
            levelOrder(Node.left, level - 1);
            levelOrder(Node.right, level - 1);
      }
    public int depth(BinaryNode<AnyType> 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 static void main( String[] args )
    {
        int[] input = {4, 2, 6, 1, 3, 5, 7, 8, 10};
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        for(int i = 0; i < input.length; i++)
        {
            tree.insert(input[i]);
        }
        System.out.print("递归前序遍历 ：");
        tree.preOrder(tree.root);
        System.out.print("\n递归中序遍历 ：");
        tree.midOrder(tree.root);
   
        System.out.print("\n递归后序遍历 ：");
        tree.postOrder(tree.root);
     
        System.out.print("\n递归层序遍历：");
        tree.levelOrder(tree.root);
    }

}