剑指Offer面试题:21.从上到下打印二叉树

一、题目:从上到下打印二叉树

题目:从上往下打印出二叉树的每个结点,同一层的结点按照从左到右的顺序打印。例如输入下图中的二叉树,则依次打印出8、6、10、5、7、9、11。

  二叉树节点的定义如下,采用C#语言描述:

    public class BinaryTreeNode
    {
        public int Data { get; set; }
        public BinaryTreeNode leftChild { get; set; }
        public BinaryTreeNode rightChild { get; set; }

        public BinaryTreeNode(int data)
        {
            this.Data = data;
        }

        public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right)
        {
            this.Data = data;
            this.leftChild = left;
            this.rightChild = right;
        }
    }

二、解题思路

2.1 核心步骤

  这道题实质是考查树的层次遍历(广度优先遍历)算法:

  每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。

扩展:如何广度优先遍历一个有向图?这同样也可以基于队列实现。树是图的一种特殊退化形式,从上到下按层遍历二叉树,从本质上来说就是广度优先遍历二叉树。

2.2 代码实现

    static void PrintFromTopToBottom(BinaryTreeNode root)
    {
        if (root == null)
        {
            return;
        }

        Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
        queue.Enqueue(root);

        while (queue.Count > 0)
        {
            BinaryTreeNode printNode = queue.Dequeue();
            Console.Write("{0}\t", printNode.Data);

            if (printNode.leftChild != null)
            {
                queue.Enqueue(printNode.leftChild);
            }

            if (printNode.rightChild != null)
            {
                queue.Enqueue(printNode.rightChild);
            }
        }
    }

三、单元测试

  本次测试封装了几个辅助测试的方法,实现如下:

    static void TestPortal(string testName, BinaryTreeNode root)
    {
        if (!string.IsNullOrEmpty(testName))
        {
            Console.WriteLine("{0} begins:", testName);
        }

        Console.WriteLine("The nodes from top to bottom, from left to right are:");
        PrintFromTopToBottom(root);
        Console.WriteLine("\n");
    }

    static void SetSubTreeNode(BinaryTreeNode root, BinaryTreeNode lChild, BinaryTreeNode rChild)
    {
        if (root == null)
        {
            return;
        }

        root.leftChild = lChild;
        root.rightChild = rChild;
    }

    static void ClearUpTreeNode(BinaryTreeNode root)
    {
        if(root != null)
        {
            BinaryTreeNode left = root.leftChild;
            BinaryTreeNode right = root.rightChild;

            root = null;

            ClearUpTreeNode(left);
            ClearUpTreeNode(right);
        }
    }

3.1 功能测试

    //            10
    //         /      \
    //        6        14
    //       /\        /\
    //      4  8     12  16
    static void Test1()
    {
        BinaryTreeNode node10 = new BinaryTreeNode(10);
        BinaryTreeNode node6 = new BinaryTreeNode(6);
        BinaryTreeNode node14 = new BinaryTreeNode(14);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node8 = new BinaryTreeNode(8);
        BinaryTreeNode node12 = new BinaryTreeNode(12);
        BinaryTreeNode node16 = new BinaryTreeNode(16);

        SetSubTreeNode(node10, node6, node14);
        SetSubTreeNode(node6, node4, node8);
        SetSubTreeNode(node14, node12, node16);

        TestPortal("Test1", node10);

        ClearUpTreeNode(node10);
    }

    //               5
    //              /
    //             4
    //            /
    //           3
    //          /
    //         2
    //        /
    //       1
    static void Test2()
    {
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node1 = new BinaryTreeNode(1);

        node5.leftChild = node4;
        node4.leftChild = node3;
        node3.leftChild = node2;
        node2.leftChild = node1;

        TestPortal("Test2", node5);

        ClearUpTreeNode(node5);
    }

    // 1
    //  \
    //   2
    //    \
    //     3
    //      \
    //       4
    //        \
    //         5
    static void Test3()
    {
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node1 = new BinaryTreeNode(1);

        node1.rightChild = node2;
        node2.rightChild = node3;
        node3.rightChild = node4;
        node4.rightChild = node5;

        TestPortal("Test3", node1);

        ClearUpTreeNode(node5);
    }

    // 树中只有1个结点
    static void Test4()
    {
        BinaryTreeNode node1 = new BinaryTreeNode(1);

        TestPortal("Test4", node1);

        ClearUpTreeNode(node1);
    }

    // 树中木有结点
    static void Test5()
    {
        TestPortal("Test5", null);
    }

3.2 测试结果

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

CRC校验码

循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码也叫(N,K)码。对于一个给定的(N,K)码,可以证明...

33860
来自专栏Flutter入门到实战

老司机带你重构Android的v4包的部分源码

版权声明:本文为博主原创文章,未经博主允许不得转载。https://www.jianshu.com/p/a08d754944c4

20110
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(二):基本操作(判断、运算、基本函数)

SAS生成新变量 SAS支持基本的加减乘除,值得一提的是它的**代表指数,而不是^。 * Modify homegarden data set with ass...

53640
来自专栏算法修养

pta 习题集5-18 打印学生选课清单

假设全校有最多40000名学生和最多2500门课程。现给出每门课的选课学生名单,要求输出每个前来查询的学生的选课清单。 输入格式: 输入的第一行是两个正整...

336100
来自专栏CreateAMind

coach 模块化最好的强化学习框架

11540
来自专栏五分钟学算法

LeeCode题目图解

There is an English version of README here. just click it!

18120
来自专栏desperate633

LeetCode Fizz Buzz题目分析代码

Write a program that outputs the string representation of numbers from 1 to n.

9310
来自专栏一个会写诗的程序员的博客

计算机中的数学【水仙花数】求解自然数中所有的水仙花数

在数论中,水仙花数(Narcissistic number),也被称为超完全数字不变数(pluperfect digital invariant, PPDI)、...

20920
来自专栏函数式编程语言及工具

Cats(1)- 从Free开始,Free cats

  cats是scala的一个新的函数式编程工具库,其设计原理基本继承了scalaz:大家都是haskell typeclass的scala版实现。当然,cat...

245100
来自专栏Albert陈凯

2018-04-17 Java的Collection集合类3分钟搞掂Set集合前言

3分钟搞掂Set集合 前言 声明,本文用的是jdk1.8 现在这篇主要讲Set集合的三个子类: HashSet集合 A:底层数据结构是哈希表(是一个元素为链...

31370

扫码关注云+社区

领取腾讯云代金券