java - 如何打印二叉树中节点数最多的级别？

Question

class CS6085BTolani {

static Lab5BTMethods one = new Lab5BTMethods();
static int array[] ;
static int counter=0;
static int level = 0;
static int right = 0;
static int left  = 0;
static int numberOfNodesInLevel = 0;
static int levelWithMaxNodes = -1;

public static void main(String[] args) 
{
    new MyInfo().identity();
    one.createBinaryTree();
    array = new int[numberOfNodes(one.root)];
    System.out.println();
    System.out.println("Pre Order Travesal");
    one.preOrder(one.root);
    System.out.println("\n");
    System.out.println("Height of the Tree = "+one.height(one.root));
    System.out.print("\nThe Level Order of the Tree");
    one.displayTree(one.root);
    System.out.println("\n");
    System.out.println("Number of nodes in the tree : "+numberOfNodes(one.root));
    System.out.println("\nLargest Value in the tree : "+largest(one.root));
    System.out.println();
    System.out.println("Sum of Elements : " + sumOfElements(one.root));
    System.out.println();
    int x = 10;//search element
    System.out.println("Search for Number " + x +" : "+searchFor(one.root,x));
    System.out.println();
    setLargestNumberOfNodes(one.root);
    level=0;
    levelWithLargestNumberOfNodes(one.root);
    //System.out.println("Max Number of Nodes in any Level : "+(numberOfNodesInLevel+1));
    //System.out.println(levelWithMaxNodes);
}
static int numberOfNodes(Lab5BTNode root)
{
        if(root == null)
        return 0;
    else 
        return(numberOfNodes(root.right) + numberOfNodes(root.left) + 1);
}
static void toArray(Lab5BTNode root)
{

    if(root!=null)
    {
        array[counter++] = root.element;
        toArray(root.left);
        toArray(root.right);
    }
}
static int largest(Lab5BTNode root)
{
    int large = 0;
    counter=0;
    toArray(root);
    for (int i =0; i<array.length; i++) {
        if(array[i]>large){
            large = array[i];
        }
    }
    return large;
}

// program for Assignment B
static int sumOfElements(Lab5BTNode root)
{
    counter=0;
    toArray(root);
    int sum=0;
    for (int i = 0; i < array.length; i++) {
        sum = sum + array[i];
    }
    return sum;
}
static boolean searchFor(Lab5BTNode root, int n)
{
    counter=0;
    toArray(root);
    for (int i =0; i<array.length; i++)
        if(array[i]==n)
            return true;
    return false;
}
static void setLargestNumberOfNodes(Lab5BTNode root)
{
    right=0;
    left = 0;
    if (root == null) return;
    else
    {
        setLargestNumberOfNodes(root.right);
        right++;

        setLargestNumberOfNodes(root.left);
        left++;
        level++;

        if((left+right) > numberOfNodesInLevel)
        {
            numberOfNodesInLevel = left+right;

        }

    }

}
static void levelWithLargestNumberOfNodes(Lab5BTNode root)
{
 //Please Help with this code.
 //this function should print the levels with the largest number of nodes in the BT
    right=0;
    left = 0;
    if (root == null) return;
    else
    {
        levelWithLargestNumberOfNodes(root.right);
        right++;

        levelWithLargestNumberOfNodes(root.left);
        left++;
        level++;

        if((left+right) == numberOfNodesInLevel)
        {
            System.out.println("Level with largest number of Nodes: "+ (level));

        }

    }

}

}

我正在尝试使用我的教授提供的 .class 文件来运行 BT，但我无法真正打印 BT 中节点数量最多的关卡。我将放置运行该文件时得到的输出。

输出

Pre Order Travesal
17 55 24 37 44 15 27 12 11 10 18 16 39 38 29 14 37 51 98 71 63 20 46 30 26 

Height of the Tree = 7

The Level Order of the Tree
17 
55 39 
24 37 38 29 
44 15 14 37 
27 16 51 26 
12 11 98 71 
10 18 63 30 
20 46 

Number of nodes in the tree : 25

Largest Value in the tree : 98

Sum of Elements : 848

Search for Number 10 : true

level With largest Nodes: 6
level With largest Nodes: 9
level With largest Nodes: 20
level With largest Nodes: 25

我的树高度是7，但是这些值都是错误的。请帮忙。谢谢。

Answer 1

我没有测试它，但你应该了解它是如何工作的。基本上，您需要始终知道您的方法处于树的哪一层，并增加适当的计数器。我没有使用 map 等更高级的语言功能，因为看起来您只在作业中使用数组。我也只是打印了结果，尽管最佳实践可能是该方法返回整数。

static void levelWithLargestNumberOfNodes(Lab5BTNode root)
{
    int height = one.height(root);
    int[] levelCounters = new int[height];
    updateCounters(root,0, levelCounters);
    int levelWithMaxNodes = findMaxIndex(levelCounters);
    System.out.println("Level with largest number of Nodes: "+ levelWithMaxNodes);
}

private static void updateCounters(Lab5BTNode root, int currentLevel, int[] levelCounters){
    if(root!=null){
        levelCounters[currentLevel]++;
        updateCounters(root.left, currentLevel+1, levelCounters);
        updateCounters(root.right, currentLevel+1, levelCounters);
    }
}

private static int findMaxIndex(int[] levelCounters) {
    int maxIndex = -1;
    int maxNodes = -1;
    for(int i = 0; i<levelCounters.length; ++i){
        if(levelCounters[i]>maxNodes){
            maxNodes = levelCounters[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}