`
uule
  • 浏览: 6351581 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

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

 
阅读更多

二叉树的深度优先遍历(DFS)与广度优先遍历(BFS)

Java实现二叉树的深度优先遍历和广度优先遍历算法示例

树的深度优先遍历和广度优先遍历的原理

 

二叉树的深度优先遍历(栈)和广度优先遍历(队列)

 

二叉树的深度优先遍历(DFS广度优先遍历(BFS)

 

深度优先遍历:从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止。

深度优先遍历有先、中、后序方式,方法可以递归和非递归

 

广度优先遍历:从根节点出发,在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。(从根节点开始,一层一层遍历)


DFS:ABDECFG

BFS:ABCDEFG

 

DFS实现:

数据结构:栈

父节点入栈,父节点出栈,先右子节点入栈,后左子节点入栈。递归遍历全部节点即可

 

BFS实现:

数据结构:队列

父节点入队,父节点出队列,先左子节点入队,后右子节点入队。递归遍历全部节点即可

 

package com.test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 树的遍历方式 深度优先遍历:递归和非递归两种 广度优先遍历:
 *
 */
public class PrintTree {
    public static void main(String[] args) {
 
        TreeNode tree = createTree();
        // System.out.println("递归方式先序遍历:");
        // ForeachTree.rePreTree(tree);
        
         //System.out.println("非递归方式先序遍历:");
         //ForeachTree.nRePreTree(tree);
         //System.out.println();
         //ForeachTree.nRePreTree2(tree);
        
        // System.out.println("递归方式中序遍历:");
         //ForeachTree.reInTree(tree);
         
        // System.out.println("非递归方式中序遍历:");
         ForeachTree.nReInTree(tree);
         
        // System.out.println("递归方式后序遍历:");
        // ForeachTree.reEndTree(tree);
         
        // System.out.println("非递归方式后序遍历:");
        // ForeachTree.nReEndTree(tree);
         
        //System.out.println("广度优先遍历:");
        //ForeachTree.BFSTree(tree);
    }
 
    /**
     * 创建一个用作测试的树
     * 
     * @return
     */
    public static TreeNode createTree() {
 
        /*
         * 示例: 
         *          1 
         *      2       3 
         *    4   5    6  7 
         *  8      9
         */
        TreeNode root = new TreeNode(1);
        TreeNode left1Tree = new TreeNode(2);
        TreeNode left2Tree = new TreeNode(4);
        TreeNode left3Tree = new TreeNode(8);
        TreeNode left4Tree = new TreeNode(6);
        TreeNode right1Tree = new TreeNode(5);
        TreeNode right2Tree = new TreeNode(9);
        TreeNode right3Tree = new TreeNode(3);
        TreeNode right4Tree = new TreeNode(7);
        left2Tree.leftNode = left3Tree;
        right1Tree.rightNode = right2Tree;
        left1Tree.leftNode = left2Tree;
        left1Tree.rightNode = right1Tree;
        right3Tree.leftNode = left4Tree;
        right3Tree.rightNode = right4Tree;
        root.leftNode = left1Tree;
        root.rightNode = right3Tree;
        return root;
 
    }
}
 
class ForeachTree {
 
    /**
     * 先序遍历:根左右的顺序--递归方式
     * 
     * @param tree
     */
    public static void rePreTree(TreeNode tree) {
        if (tree != null) {
            System.out.println(tree.val);
            rePreTree(tree.leftNode);
            rePreTree(tree.rightNode);
        }
    }
 
    /**
     * 先序遍历:根左右的顺序--非递归方式
     * 思路:
     * 1. 获取当前节点,首先输出当前节点,然后将其两个节点压入栈中,然后利用栈的先进后出的特性,弹出节点并获取其子节点
     * 2. 在此判断条件为当前节点不为空,若为空则直接结束本次循环然后进行下一次循环
     * @param tree
     */
    public static void nRePreTree(TreeNode tree) {
        // 创建栈,由于深度遍历是
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(tree);
        while (stack != null && !stack.isEmpty()) {
            TreeNode te = stack.pop();
            System.out.println(te.val);
            
            List<TreeNode> trees = te.getChildren();
            if(trees == null) continue;
            for(TreeNode t:trees) {
                if(t!=null) {
                    stack.push(t);
                }
            }
        }
 
    }
    
    public static void nRePreTree2(TreeNode tree) {
        // 创建栈,由于深度遍历是
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(tree);
        while (stack != null && !stack.isEmpty()) {
            TreeNode te = stack.pop();
            System.out.println(te.val);
          
            if(te.rightNode != null){
            	stack.push(te.rightNode);
            }
           
            
            if(te.leftNode != null){
            	stack.push(te.leftNode);
            }
            
        }
 
    }
 
    /**
     * 中序遍历:左根右的顺序--递归方式
     * 
     * @param tree
     */
    public static void reInTree(TreeNode tree) {
        if (tree != null) {
            reInTree(tree.leftNode);
            System.out.println(tree.val);
            reInTree(tree.rightNode);
        }
    }
 
    /**
     * 中序遍历:左根右的顺序--非递归方式
     * 思路:
     * 1. 由于中序遍历方式为左根右,所以先判断当前节点是否有左子节点,若有的话将当前节点的左子节点置为空(防止下次遍历到重复判
     * 断)再压入栈,然后将当前节点的左子节点压入栈,一次类推
     * 2. 直到当前节点没有左子节点时,输出当前节点的值,然后判断是否有右子节点,若有的话则继续进行压栈操作(在此有一技巧之处在
     * 于若该节点的左右子节点都没有的话,则不需要将当前节点压入栈--在第一次获取当前节点时已经将当前节点弹出了)
     * 3. 注:只有在当前节点有左子节点时需要将当前节点压入栈,因为遍历顺序为左中右,所以在当前节点有左节点时,需要再进行回根节
     * 点查找输出根节点的值,若当前节点没有左节点时,则不需要记录上一节点
     * @param tree
     */
    public static void nReInTree(TreeNode tree) {
        // 创建栈,由于深度遍历是
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(tree);
        while(stack != null && !stack.isEmpty()) {
            TreeNode root = stack.pop();
            if(root.leftNode != null) {
                TreeNode left = root.leftNode;
                root.leftNode = null;
                stack.push(root);
                stack.push(left);
            }else {
                System.out.println(root.val);
                if(root.rightNode != null) {
                    TreeNode right = root.rightNode;
                    stack.push(right);
                }
            }
        }
    }
    

 
    /**
     * 后序遍历:左右根的顺序--递归方式
     * 
     * @param tree
     */
    public static void reEndTree(TreeNode tree) {
        if (tree != null) {
            reEndTree(tree.leftNode);
            reEndTree(tree.rightNode);
            System.out.println(tree.val);
        }
    }
 
    /**
     * 后序遍历:左右根的顺序--非递归方式
     * 
     * @param tree
     */
    public static void nReEndTree(TreeNode tree) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(tree);
        while( stack != null && !stack.isEmpty()) {
 
            TreeNode root = stack.pop();
            if(root.leftNode != null) {
                TreeNode left = root.leftNode;
                root.leftNode = null;
                stack.push(root);
                stack.push(left);
            }else if(root.rightNode != null) {
                TreeNode right = root.rightNode;
                root.rightNode = null;
                stack.push(root);
                stack.push(right);
            }else {
                System.out.println(root.val);
            }
        }
    }
 
    /**
     * 广度优先遍历
     * 
     * @param tree
     */
    public static void BFSTree(TreeNode tree) {
        Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.push(tree);
        while (queue != null && !queue.isEmpty()) {
            TreeNode root = queue.pop();
            System.out.println(root.val);
            
            if (root.leftNode != null) {
                queue.add(root.leftNode);
            }
            if (root.rightNode != null) {
                queue.add(root.rightNode);
            }
        }
    }
 
}
 
class TreeNode {
 
    int val;
 
    public TreeNode(int val) {
        this.val = val;
    }
 
    TreeNode leftNode;
    TreeNode rightNode;
 
    /**
     * 获取该节点的所有左右子节点-先右后左
     * 由于所有遍历方式都是从左向右的顺序,所以压入栈时需要先将右子节点压入,后将左子节点压入,
     * 因此在此获取子节点时先添加右子节点,后添加左子节点
     * @return
     */
    public List<TreeNode> getChildren() {
        List<TreeNode> list = new LinkedList<TreeNode>();
        if (this.rightNode != null)
            list.add(this.rightNode);
        if (this.leftNode != null)
            list.add(this.leftNode);
        return list.size() == 0 ? null : list;
    }
 
}

 。。

 

 

 

 

  • 大小: 11.3 KB
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics