数据结构与算法-- 广度优先打印二叉树

叁歲伎倆 2022-11-16 05:53 154阅读 0赞

#### 广度优先打印二叉树 ####

*  题目：从上往下打印出二叉树的每一个节点，同一层节点按照从左到右顺序打印，例如下图中二叉树，依次打印出是8,6,10,5,7,9,11

![在这里插入图片描述][20210406172759375.png]

*  如上题中二叉树的节点定义我们用之前文章 [二叉树实现原理][Link 1]中定义的节点结构。
 *  此处提议就是广度优先原则的一个遍历，但是需要一个从左到右的打印规则，和我们之前二叉树的前序，中序，后续遍历都不一样，
 *  可能开始想到的是中序遍历，每次都打印根节点，但是中序遍历比如左子树中所有节点在右子树之前，和题意不符合。
 *  广度优先原则的话我们想起之前文章：[图论，最短路算法，拓扑排序算法][Link 2]，其中拓扑排序算法，和最短路径算法的优化版本都是用的广度优先原则去遍历图。我们依然可以用相同的思路应对
 *  先打印根，然后将根链接的所有节点依据从左到有原则依次加入队列
 *  不断从队列中取出节点打印，并重复上一步，直到队列为空。

*  依据以上分析可得一下代码：

/** * 从上到下，按层打印树 * @author liaojiamin * @Date:Created in 16:29 2021/4/2 */
    public class PrintBinaryTopToBottom { 
        public static void printBinaryTopToEnd(BinaryNode binaryNode){ 
            if(binaryNode == null){ 
                return;
            }
            LinkedList<BinaryNode> myQueue = new LinkedList<BinaryNode>();
            myQueue.addFirst(binaryNode);
            while (myQueue.size() > 0){ 
                BinaryNode temp = myQueue.removeFirst();
                if(temp != null){ 
                    System.out.print(temp.getElement());
                    System.out.print(",");
                    myQueue.addLast(temp.getLeft());
                    myQueue.addLast(temp.getRight());
                }
            }
        }
    
        public static void main(String[] args) { 
            BinaryNode node = new BinaryNode(null, null, null);
            BinarySearchTree searchTree = new BinarySearchTree();
            Random random = new Random();
            for (int i = 0; i < 20; i++) { 
                int num = random.nextInt(100);
                node = searchTree.insert(num, node);
                System.out.print(num+",");
            }
            System.out.println();
            printBinaryTopToEnd(node);
        }
    }

[上一篇：数据结构与算法–举例分析法- 栈的压入弹出序列][-]  
[下一篇：数据结构与算法-- 二叉树后续遍历序列校验][--]

[20210406172759375.png]: /images/20221022/59ab0aa3535740ecb6bf1b4379b3535c.png
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/111043418
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/112277213
[-]: https://blog.csdn.net/liaojiamin0102/article/details/115461380
[--]: https://blog.csdn.net/liaojiamin0102/article/details/115479539