java实现二叉树的排序树、深度优先遍历和广度优先遍历

实现了二叉树的深度和广度优先遍历

深度优先遍历:

对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。而二叉树的深度优先遍历分为先序遍历,中序遍历和后续遍历。

  • 先序遍历:先访问根,在访问左子树,最后访问右子树,总结就是“根左右”;
  • 中序遍历:先访问左子树,再访问根,最后访问右子树,总结就是“左根右”;
  • 后序遍历:先访问左子树,再访问右子树,最后访问根,总结就是“左右根”;

通常采用递归的方式实现遍历,非递归方式需要结合栈(后进先出)的特点实现。

广度优先遍历:

又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。

广度优先遍历的非递归的通用做法是采用队列(先入先出)。

用该图来理解深度优先遍历和广度优先遍历:

  • 深度优先遍历:该图为一个无向图,假设我们从A开始进行深度优先搜索,第二点可以是B、C、D中任意一个,假设访问的是B,那么路径为A - B - E,搜索完成后直接退回B,搜索其下一个子节点,完成B之后退到A,搜索C节点,以此类推,直到找出需要的解。
  • 广度优先遍历:假设从A开始探索,第二点可以是B、C、D中任意一个,假设访问的是B,那么接下来再从C、D中选择一个,假设最终的路线是A-B-C-D,然后同理再去遍历B、C、D的子节点,直到所有的点都被遍历鼓过。

二叉排序树:

二叉排序树是一种特殊的二叉树,其树的根节点的左侧总是小于根节点,节点的右侧总是大于根节点。如下图所示。

图解两种遍历算法:

该图为输入了:35 20 15 16 29 28 30 40 50 45 55之后生成的二叉排序树。

先序遍历(递归):35 20 15 16 29 28 30 40 50 45 55
中序遍历(递归):15 16 20 28 29 30 35 40 45 50 55
后序遍历(递归):16 15 28 30 29 20 45 55 50 40 35
先序遍历(非递归):35 20 15 16 29 28 30 40 50 45 55
中序遍历(非递归):15 16 20 28 29 30 35 40 45 50 55
后序遍历(非递归):16 15 28 30 29 20 45 55 50 40 35
广度优先遍历:35 20 40 15 29 50 16 28 30 45 55

程序实现(有注解,不懂的地方可以留言):

/**
*实体类
*/
public class Tree {

    Tree treeLeft;
    Tree treeRight;//创建了树的两个分支,声明类型自己本身树,目的是每新建一个分支依旧为树的一个节点
    int data;

    Tree(int data){
        this.data = data;//data在这里是树节点(或分支)的值
        treeLeft = treeRight = null;
    }
}

/**
*运行主程序
*/
public class TreeMain {

    /**
     * 二叉排序树;左边是小于等于,右边是大于根节点。
     * @param root
     * @param data
     * @return
     */
    public static Tree insert(Tree root, int data) {
        if (root == null) {
            return new Tree(data);//新建树节点
        }else {
            Tree cur;
            if (data <= root.data) {//小的放在左侧
                cur = insert(root.treeLeft,data);//递归一直到root为空时,调用第一个IF实现新建树节点
                root.treeLeft = cur;
            }else {//大的放在右侧
                cur = insert(root.treeRight,data);
                root.treeRight = cur;
            }
            return root;
        }
    }

    /**
     * 深度优先遍历分为,先序、中序和后序遍历
     */

    /**
     * 递归法实现先序遍历,并打印
     * @param root
     */
    public static void preOrder(Tree root){
        if(root == null) return;
        System.out.print(root.data + " ");
        preOrder(root.treeLeft);
        preOrder(root.treeRight);
    }

    /**
     * 递归法实现中序遍历,并打印
     * @param root
     */
    public static void inOrder(Tree root){
        if(root == null) return;
        inOrder(root.treeLeft);//用递归的方法一直找到树的最左侧
        System.out.print(root.data + " ");
        inOrder(root.treeRight);
    }

    /**
     * 递归方法实现后序遍历,并打印
     * @param root
     */
    public static void postOrder(Tree root){
        if(root == null) return;
        postOrder(root.treeLeft);
        postOrder(root.treeRight);
        System.out.print(root.data + " ");
    }

    /**
     * 非递归方法实现先序遍历,并打印
     * @param root
     */
    public static void preOrder2(Tree root){
        LinkedList<Tree> stack = new LinkedList<>();
        Tree currentRoot = null;
        stack.push(root);
        while (!stack.isEmpty()){
            currentRoot = stack.pop();
            System.out.print(currentRoot.data + " ");
            //栈是先入后出,需要先入栈右分支
            if (currentRoot.treeRight != null){
                stack.push(currentRoot.treeRight);
            }
            if (currentRoot.treeLeft != null){
                stack.push(currentRoot.treeLeft);
            }
        }
    }

    /**
     * 非递归方法实现中序遍历,并打印
     * @param root
     */
    public static void inOrder2(Tree root){
        LinkedList<Tree> stack = new LinkedList<>();
        Tree currentRoot = root;
        while (currentRoot !=null || !stack.isEmpty()){
            //遍历到二叉树的最左侧
            while (currentRoot != null){
                stack.push(currentRoot);
                currentRoot = currentRoot.treeLeft;
            }
            currentRoot = stack.pop();
            System.out.print(currentRoot.data + " ");
            currentRoot = currentRoot.treeRight;
        }
    }

    /**
     * 非递归方法实现后序遍历,并打印
     * @param root
     */
    public static void postOrder2(Tree root){
        LinkedList<Tree> stack = new LinkedList<>();
        Tree currentRoot = root;
        Tree rightRoot = null;
        while (currentRoot != null || !stack.isEmpty()){
            while (currentRoot != null){
                stack.push(currentRoot);
                currentRoot = currentRoot.treeLeft;
            }
            currentRoot = stack.pop();
            //当前节点没有右节点或上一个结点(已经输出的结点)是当前结点的右结点,则输出当前结点
            while (currentRoot.treeRight == null || currentRoot.treeRight == rightRoot){
                System.out.print(currentRoot.data + " ");
                rightRoot = currentRoot;
                if (stack.isEmpty()){
                    return;
                }
                currentRoot = stack.pop();
            }
            stack.push(currentRoot);//还有未遍历的右侧节点
            currentRoot = currentRoot.treeRight;
        }
    }

    /**
     * 对列法实现二叉树广度优先遍历,队列遵循先进先出的规则,适合本方法
     * @param root
     */
    public static void levelOrer(Tree root){
        Queue<Tree> queue = new LinkedList<Tree>();//新增队列

        if(root != null){
            queue.add(root);//将根节点加入队列
        }

        while (!queue.isEmpty()){
            Tree cur = queue.peek();//创建cur的目的是在while循环的时候逐层将树带入,如果直接用root,会导致只能输出一级树
            System.out.print(cur.data + " ");
            queue.remove();
            if (cur.treeLeft != null){
                queue.add(cur.treeLeft);//先将左分支加入队列,之后先输出
            }
            if(cur.treeRight != null){
                queue.add(cur.treeRight);
            }
        }

    }

    /**
     * main函数,输入输出,遍历
     * @param args
     */
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数字的个数:");
        int T = sc.nextInt();
        int[] t = new int[T];
        System.out.println("请输入数字,以空格分隔:");
        for (int i = 0; i < T; i++) {
            t[i] = sc.nextInt();
        }

        Tree root = null;
        for (int i = 0; i < T; i++) {
            root = insert(root,t[i]);
        }
        System.out.println("递归先序遍历:");
        preOrder(root);
        System.out.println();
        System.out.println("递归中序遍历:");
        inOrder(root);
        System.out.println();
        System.out.println("递归后序遍历:");
        postOrder(root);
        System.out.println();
        System.out.println("非递归先序遍历:");
        preOrder2(root);
        System.out.println();
        System.out.println("非递归中序遍历:");
        inOrder2(root);
        System.out.println();
        System.out.println("非递归后序遍历:");
        postOrder2(root);
        System.out.println();
        System.out.println("广度优先遍历:");
        levelOrer(root);

    }
}
运行结果:

发表评论