C#刷剑指Offer | 从上到下打印二叉树

【C#刷题】| 作者 / Edison Zhou

这是EdisonTalk的第288篇原创内容

---

我们来用之前学到的数据结构知识来刷《剑指Offer》的一些核心题目（精选了其中30+道题目），希望对你有帮助！本文题目为：从上到下打印二叉树。

1题目介绍

题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。例如输入下图中的二叉树，则依次打印出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解题思路与实现

思路：

这道题实质是考查树的层次遍历（广度优先遍历）算法：

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

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

实现：

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);}} }

3单元测试

准备工作

为了方便地进行单元测试代码编写，这里封装了几个公用方法：

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);} }

单元测试用例：

// 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); }

测试结果：

测试的结果情况如下图：

Ref参考资料

何海涛，《剑指Offer》

后台回复：剑指offer，即可获得pdf下载链接哟！

????扫码关注EdisonTalk

设为星标，不再失联！

往期推文合集：2020年上半年推文合集

总结

以上是生活随笔为你收集整理的C#刷剑指Offer | 从上到下打印二叉树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。