java - 计算 BST 中的节点数

Question

各位，我已经实现了用于计算二叉树中节点总数的代码，该方法如下所示:

public int countNodes(Node root){
        int count = 0;

        if(root == null){
            System.out.println("The tree is empty!");
            return -1;
        }
        else{
            count = 1;
            Node current = root;

            if(current.leftChild != null){
                count += countNodes(current.leftChild);
            }

            else if(current.rightChild != null){
                count += countNodes(current.rightChild);
            }
        }
        System.out.print("The total number of nodes in the tree is ");
        return count;
    }

该方法的参数包含 Node root 但我的问题是，当我尝试从 main 类运行该方法时，我应该传递什么作为参数？ 我应该在此处的参数中添加什么？: int countNodes = tree1.countNodes("???????????????");

package BST;

public class Node {

    int data;
    Node leftChild;
    Node rightChild;

    public void displayNode(){
        System.out.println("The data is " + this.data);
    }
}

class Tree{
    private Node root;

    public Tree(){
        this.root = null;
    }

    public Node find(int key){
        Node current = root;
        while(current.data != key){
            if(key < current.data){
                current = root.leftChild;
            }
            else{
                current = root.rightChild;
            }
            if(current == null){
                System.out.println("The Node contatining the key " + key + " does not exist!");
                return null;
            }

        }
        return current;
    }

    public void insert(int key){
        Node newNode = new Node();

        if(root == null){
            root = newNode;
        }
        else{
            Node current = root;
            Node parent;

            while(true){
                parent = current;
                if(current.data > key){
                    current = current.leftChild;
                    if(current == null){
                        parent.leftChild = newNode;
                        return;
                    }
                }
                else{
                    current = current.rightChild;
                    if(current == null){
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }

    }

    public Node findMin(){
        if(root == null){
            System.out.println("The tree is empty!");
            return null;
        }
        else{
            Node current = root.leftChild;
            Node last = root; 
            while(current != null){
                last = current;
                current = current.leftChild;
            }
            return last;
        }
    }

    public Node findMax(){
        if(root == null){
            System.out.println("The tree is empty!");
            return null;
        }
        else{
            Node current = root.rightChild;
            Node last = root;
            while(current != null){
                last = current;
                current = current.rightChild;
            }
            return last;
        }
    }

    public int countNodes(Node root){
        int count = 0;

        if(root == null){
            System.out.println("The tree is empty!");
            return -1;
        }
        else{
            count = 1;
            Node current = root;

            if(current.leftChild != null){
                count += countNodes(current.leftChild);
            }

            else if(current.rightChild != null){
                count += countNodes(current.rightChild);
            }
        }
        System.out.print("The total number of nodes in the tree is ");
        return count;
    }

MainTester 类

class MainTester{

    public static void main(String[] args){

        Tree tree1 = new Tree();
        tree1.insert(1);
        tree1.insert(2);
        tree1.insert(3);
        tree1.insert(4);
        tree1.insert(5);
        tree1.insert(6);
        tree1.insert(7);
        tree1.insert(8);
        tree1.insert(9);
        tree1.insert(10);

        int countNodes = tree1.countNodes("?????????????");

    }
}

Answer 1

您可以使用树的根节点。根据您的示例，您可以从方法 find() 中获取它

int countNodes = tree1.countNodes(tree1.find(1));

您还可以使用其他节点，例如

int countNodes = tree1.countNodes(tree1.find(5));