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

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

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

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

Answer 2

解决方案使用的文件和 PrintWriter（适用于高度为 10 的 BT）

static File f1;
static PrintWriter pw;

static void levelWithLargestNumberOfNodes(Lab5BTNode root) throws Exception
{

    f1 = new File("temp.txt");
    pw = new PrintWriter("temp.txt");
    boolean b1 = f1.createNewFile();
    //System.out.println(b1);
    if(!b1){
        for(int i = 0 ; i < (one.height(root)); i++)
        {
            printElementsOnALevel(one.root,i);
            pw.println();
        }
        pw.flush(); pw.close();
    }

    boolean b2 = f1.exists();
    //System.out.println(b2);

    if(b2)
    {
        Scanner sc = new Scanner(f1);
        int count = 0;
        String lev0="",lev1="",lev2="",lev3="",lev4="",lev5="",lev6="",lev7 = "",lev8 = "",lev9 = "",lev10 = "";
        while (sc.hasNextLine())
        {
            if(count==0)
                lev0 = sc.nextLine();
            if(count==1)
                lev1 = sc.nextLine();
            if(count==2)
                lev2 = sc.nextLine();
            if(count==3)
                lev3 = sc.nextLine();
            if(count==4)
                lev4 = sc.nextLine();
            if(count==5)
                lev5 = sc.nextLine();
            if(count==6)
                lev6 = sc.nextLine();
            if(count==7)
                lev7 = sc.nextLine();
            if(count==8)
                lev8 = sc.nextLine();
            if(count==9)
                lev9 = sc.nextLine();
            if(count==10)
                lev10 = sc.nextLine();
            count++;
        }
        StringTokenizer tokens = new StringTokenizer(lev0," ");
        int firstcount = tokens.countTokens();
        //System.out.println(firstcount);

        StringTokenizer tokens1 = new StringTokenizer(lev1," ");
        int secondcount = tokens1.countTokens();

        StringTokenizer tokens2 = new StringTokenizer(lev2," ");
        int thirdcount = tokens2.countTokens();

        StringTokenizer tokens3 = new StringTokenizer(lev3," ");
        int fourthcount = tokens3.countTokens();

        StringTokenizer tokens4 = new StringTokenizer(lev4," ");
        int fifthcount = tokens4.countTokens();

        StringTokenizer tokens5 = new StringTokenizer(lev5," ");
        int sixthcount = tokens5.countTokens();

        StringTokenizer tokens6 = new StringTokenizer(lev6," ");
        int seventhcount = tokens6.countTokens();

        StringTokenizer tokens7 = new StringTokenizer(lev7," ");
        int eighthcount = tokens7.countTokens();

        StringTokenizer tokens8 = new StringTokenizer(lev8," ");
        int ninthcount = tokens8.countTokens();

        StringTokenizer tokens9 = new StringTokenizer(lev9," ");
        int tenthcount = tokens9.countTokens();

        StringTokenizer tokens10 = new StringTokenizer(lev10," ");
        int eleventhcount = tokens10.countTokens();

        int temp[] = {firstcount,secondcount,thirdcount,fourthcount
            ,fifthcount,sixthcount,seventhcount,eighthcount,ninthcount,tenthcount,eleventhcount};

            int maxValue = temp[0]; 

    for(int i=1;i < temp.length;i++)
    { 
        if(temp[i] > maxValue)
        { 
            maxValue = temp[i]; 

        }
    }System.out.println("Levels with max number of Nodes i.e "+maxValue+" nodes are as follows : " );

            if(maxValue == firstcount)
                System.out.println(lev0);
            if(maxValue == secondcount)
                System.out.println(lev1);
            if(maxValue == thirdcount)
                System.out.println(lev2);
            if(maxValue == fourthcount)
                System.out.println(lev3);
            if(maxValue == fifthcount)
                System.out.println(lev4);
            if(maxValue == sixthcount)
                System.out.println(lev5);
            if(maxValue == seventhcount)
                System.out.println(lev6);
            if(maxValue == eighthcount)
                System.out.println(lev7);
            if(maxValue == ninthcount)
                System.out.println(lev8);
            if(maxValue == tenthcount)
                System.out.println(lev9);
            if(maxValue == eleventhcount)
                System.out.println(lev10);
        f1.delete();
    }

}

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

how to print the level with largest number of nodes in a Binary Tree?

java

recursion

binary-tree