二叉树的广度优先搜索与深度优先搜索(前序,中序,后序)

先创建一个简单的二叉树,方便后期验证广度与深度搜索结果

根据数组生成一个二叉树

 /**
      int[] arr = new int[]{1, 2, 4, 0, 0, 5, 0, 0, 3, 6, 0, 0, 7, 0, 0};
     * 根据数组创建二叉树
     */
    public TreeNode<Integer> createTreeNode(int[] tempaar) {
        if (arr.length == 0) {
            return null;
        }
        TreeNode<Integer> treeNode = new TreeNode<>();
        if (count < arr.length) {
            treeNode.data = arr[count++];
            if (treeNode.data == 0) {
                return null;
            }
            treeNode.lTreeNode = createTreeNode(tempaar);
            treeNode.rTreeNode = createTreeNode(tempaar);
        }
        return treeNode;
    }

广度优先搜索

广度优先搜索是按层从左到右遍历,利用队列先进先去的特点.

  /**
     * 广度优先搜索
     * 按层
     *
     * @param root
     */
    public void BFS(TreeNode<Integer> root) {
        Queue<TreeNode<Integer>> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            TreeNode<Integer> poll = queue.poll();
            System.out.println("data==" + poll.getData());
            if (poll.lTreeNode != null) {
                queue.offer(poll.lTreeNode);
            }
            if (poll.rTreeNode != null) {
                queue.offer(poll.rTreeNode);
            }
        }
    }

深度优先搜索(前序,中序,后序) 递归与非递归实现

前序

   /**
     * 深度优先搜索
     * 前序
     * 递归实现
     */
    public void DFSByPreorder(TreeNode<Integer> root) {
        if (root != null) {
            System.out.println("data=" + root.data);
            DFSByPreorder(root.lTreeNode);
            DFSByPreorder(root.rTreeNode);
        }
    }
     /**
     * 深度优先搜索
     * 前序
     * 非递归实现
     *
     * @param root
     */
    public void DFSByPreorder2(TreeNode<Integer> root) {
        Stack<TreeNode<Integer>> stack = new Stack<>();
        TreeNode<Integer> curr = null;
        if (root != null) {
            curr = root;
            while (curr!=null || !stack.isEmpty()) {
                while (curr != null) {
                    System.out.println("data=" + curr.getData());
                    stack.push(curr);
                    curr = curr.lTreeNode;
                }
                TreeNode<Integer> pop = stack.pop();
                curr = pop.rTreeNode;
            }
        }
    }

中序

   /**
     * 深度优先遍历
     * 中序
     * 递归
     * @param root
     */
    public void DFSByInorder(TreeNode<Integer> root){
        if(root!=null){
            DFSByInorder(root.lTreeNode);
            System.out.println("data="+root.getData());
            DFSByInorder(root.rTreeNode);
        }
    }

       /**
     * 深度优先遍历
     * 中序
     * 非递归
     * @param root
     */
    public void DFSByInorder2(TreeNode<Integer> root){
        Stack<TreeNode<Integer>> stack=new Stack<>();
        if(root!=null){
            TreeNode<Integer> curr=root;
            while (!stack.isEmpty() || curr!=null){
                while (curr!=null){
                   stack.push(curr);
                    curr=curr.lTreeNode;
                }
                TreeNode<Integer> pop = stack.pop();
                System.out.println("data="+pop.getData());
                curr=pop.rTreeNode;
            }
        }
    }

后序

 /**
     * 深度优先遍历
     * 后序
     * 递归
     * @param root
     */
    public void DFSByEpilogue(TreeNode<Integer> root){
        if(root!=null){
            DFSByEpilogue(root.lTreeNode);
            DFSByEpilogue(root.rTreeNode);
            System.out.println("data="+root.getData());
        }
    }

     /**
     * 深度优先遍历
     * 后序
     * 非递归
     * @param root
     */
    public void DFSByEpilogue2(TreeNode<Integer> root){
     if(root!=null){
         Stack<TreeNode<Integer>> stack=new Stack<>();
         TreeNode<Integer> pre=null;
         TreeNode<Integer> curr=root;
         while ( curr!=null || !stack.isEmpty()){
             while (curr!=null){
                 stack.push(curr);
                 curr=curr.lTreeNode;
             }
             curr = stack.peek();
             if(curr.rTreeNode!=null && curr.rTreeNode!=pre){
                curr=curr.rTreeNode;
             }else {
                 stack.pop();
                 System.out.println("data="+curr.getData());
                 pre=curr;
                 curr=null;
             }
         }
     }

    }