编写一个打印二叉树及其每个节点级别编号的方法。

Question

我需要编写一个使用递归打印二叉树的方法。该方法的签名必须为：

public static void level(Node n)

因此，该方法只能获取节点n，并且不应返回任何内容，只需在屏幕上打印。

我的问题是：我需要每个树级别都打印出自己的级别编号，但我不知道如何做到这一点，因为如果我放一个计数整数，它会在每次递归开始时清零。

这是我尝试过的：

public static void level(Node n)
{
    if (n.getLeftSon() == null && n.getRightSon() == null)
        System.out.println(n.getNumber());
    else
    {
        System.out.println(n.getNumber()); 
        if (n.getLeftSon() != null)
            level(n.getLeftSon());
        if (n.getRightSon() != null)
            level(n.getRightSon()); 
    }

}

这段代码可以打印出树形结构，但是没有为每个节点显示层级数。

在论坛上得到帮助后，我修改了这个方法：

public static void level(Node n)
{
    levelAndNumbers(n,0);
}

private static void levelAndNumbers(Node n, int i)
{
    if (n.getLeftSon() == null && n.getRightSon() == null)
        System.out.println(n.getNumber()+"=>"+i);
    else
    {
        System.out.println(n.getNumber()+"=>"+i); 
        if (n.getLeftSon() != null)
            levelAndNumbers(n.getLeftSon(), i+1);
        if (n.getRightSon() != null)
            levelAndNumbers(n.getRightSon(), i+1); 
    }

}

目前为止一切进展顺利！

所以，从我的理解来看，在公共方法中没有其他做法吗？我需要再添加一个私有方法，并且也需要计数器吗？

- Yuval Levy

Answer 1

几乎与您已经所做的相同，但需要进行以下修复。

public static void level(Node n) {
    level(n, 0);
}

private static void level(Node n, int level) {
   ///..............your logic
   level(n.getLeftSon(), level + 1);
   //...............
   level(n.getRightSon(), level + 1);
}

顺便说一下，在谈论分层结构时更有用的名称不是“儿子”，而是“子元素”。

- AlexR