【数据结构与算法】十九二叉树遍历 BFS 广度优先迭代算法

你的名字 2022-07-21 01:59 102阅读 0赞

# **【数据结构与算法】十九 二叉树遍历 BFS 广度优先 迭代算法** #

# **DFS - Depth First Search** 迭代算法 #

上一篇我们DFS , 深度优先算法往往使用栈来实现 , 通过栈来保存过去走过的路线 , 这样将可以回来继续知道路线, 接下来我们来使用一个队列来实现一个广度优先的算法 , 对一个二叉树逐层遍历 , 逐层遍历在[【数据结构与算法】十六 二叉树遍历 BFS 广度优先 递归算法][_ BFS _]中也介绍过 , 但是用的是递归算法 ,接下来我们用队列实现 , 迭代算法 .

![这里写图片描述][20160621220151029]

**Java实现**

package com.cn.mark.algorithm.binarytree;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    /**
     * Created by mark on 7/12/16.
     */
    public class BSTBSFQueue {
        
        TreeNode root = null;
    
        class TreeNode {
            int value;
            int position;
            TreeNode left = null, right = null;
    
            TreeNode(int value, int position) {
                this.value = value;
                this.position = position;
            }
        }
    
        /**
         * 暴露添加方法
         * @param value
         * @param position
         */
        public void add(int value, int position) {
            if (root == null) {
                root = new TreeNode(value, position);
            } else {
                add(value, position, root);
            }
        }
    
        /**
         * 内部add方法
         * @param value
         * @param position
         * @param node
         */
        private void add(int value, int position, TreeNode node) {
            if (node == null)
                throw new RuntimeException("treenode cannot be null");
            if (node.value == value)
                return; //ignore the duplicated value
            if (value < node.value) {
                if (node.left == null) {
                    node.left = new TreeNode(value, position);
                } else {
                    add(value, position, node.left);
                }
            } else {
                if (node.right == null) {
                    node.right = new TreeNode(value, position);
                } else {
                    add(value, position, node.right);
                }
            }
        }
    
    
        /**
         * 层级输出
         * @param root
         */
        private void levelOrder(TreeNode root){
            Queue q = new LinkedList();
            q.add(root);
            while(!q.isEmpty()){
                TreeNode currentNode = (TreeNode) q.poll();
                System.out.print(currentNode.value);
                if(currentNode.left!=null)
                    q.add(currentNode.left);
                if(currentNode.right!=null)
                    q.add(currentNode.right);
            }
        }
    
        public static void main(String[] args) {
    
            BSTBSFQueue bst = new BSTBSFQueue();
            int a[] = {
       3, 7, 8, 4, 2, 5, 9, 0, 6, 1};
            for (int i = 0; i < a.length; i++) {
                bst.add(a[i], i);
            }
    
            System.out.print("levelOrder :");
            bst.levelOrder(bst.root);
            System.out.println();
    
        }
    
    
    }

# **运行结果** #

![这里写图片描述][20160713002025987]

[_ BFS _]: http://blog.csdn.net/maguochao_mark/article/details/51291035
[20160621220151029]: /images/20220720/21517a0606334941a67c1f07e30f0ed1.png
[20160713002025987]: /images/20220720/333f2b2627d54c53ab3c84855fff78cd.png