【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 | 从上到下打印二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。