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

Enjoy233

发布于 2020-09-23 15:19:40

5090

发布于 2020-09-23 15:19:40

文章被收录于专栏：大白技术控的技术自留地大白技术控的技术自留地

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

我们来用之前学到的数据结构知识来刷《剑指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);
}

测试结果：

测试的结果情况如下图：