在二叉查找树中实现nodeCount（）和folCount（）

Question

我正在尝试将leafCount（）和nodeCount（）实现到这个递归二叉树程序中。在测试时，这两种方法（或它们的测试）都会失败，因此显然它们没有按预期工作。我搞不清自己哪里做错了，哪里想错了。如果有人能解释我做错了什么或指出问题所在，我将非常感激。

public class BSTrec {

    BSTNode tree, parent, curr;
    
    public BSTrec () {
        tree = null;    // the root of the tree
        parent = null;  // keeps track of the parent of the current node
        curr = null;    // help pointer to find a node or its place in the tree
    }
    
    public boolean isEmpty() {
        return tree == null;
    }
    
    private boolean findNodeRec(String searchKey, BSTNode subtree, BSTNode subparent) { 
        
        // recursive help method to find a node or its insertion place
        
        if (subtree == null) { // base case 1: node not found
            curr = null;
            parent = subparent; // the logical parent for the value
            return false;
        }
        else { // we are still in the tree
            if (subtree.info.key.equals(searchKey)) { // base case 2: found the node
                curr = subtree;     // update current to point to the node
                parent = subparent; // update parent to point to its parent
                return true;
            }
            else { // must choose the right subtree to search
                if (searchKey.compareTo(subtree.info.key) < 0) { 
                    // key less than current info: search the left subtree!
                    return findNodeRec(searchKey, subtree.left, subtree);
                }
                else { // key greater than current info: search the right subtree!
                    return findNodeRec(searchKey, subtree.right, subtree);  
                }
            }
        }
    }
    
    
    public NodeInfo retrieveNode(String searchKey) { 
        // retrieve the info part of the node with key
        // if it is in the tree
        if (findNodeRec(searchKey, tree, null)) return curr.info;
        else return null;
       
    }                                     
    
    public void addRec(String keyIn, BSTNode subtree, BSTNode subparent, boolean goLeft) {
        
        if (tree == null) { // a first node will be the new root: base case 1
            tree = new BSTNode(new NodeInfo(keyIn));
            curr = tree;
            parent = null;
        } // the tree was initiated, we got a new root
        else { // insertion in an existing tree
            if (subtree == null) { // we found the insertion place: base case 2
                if (goLeft) { // the new node is to be a left child
                    subparent.left = new BSTNode(new NodeInfo(keyIn));
                    curr = subparent.left;
                    parent = subparent; 
                }
                else { // the new node is to be a left child
                    subparent.right = new BSTNode(new NodeInfo(keyIn));
                    curr = subparent.right;
                    parent = subparent;
                }
            }
            else { // still searching for the insertion place: left or right subtree?
                if (keyIn.compareTo(subtree.info.key) < 0) {
                    addRec(keyIn, subtree.left, subtree, true);
                    // the node must be inserted in the left subtree of the
                    // current node: a recursive call
                }
                else { 
                    addRec(keyIn, subtree.right, subtree, false);
                    // the node must be inserted in the right subtree of the
                    // current node: a recursive call
                }
            }
        }
    }
    
    public void deleteNode(String searchKey) { 
        
        // deletes the node with the given key, uses a recursive search
    
        boolean found = findNodeRec(searchKey, tree, null);
        
        if (!found) // the key is not in the tree
            System.out.println("The key is not in the tree!");
        else { // curr points to the node to be deleted, parent to its parent
            if ((curr.left == null) && (curr.right == null)) // delete a leaf
                if (parent == null)  // delete the last node
                    tree = null;
                else // the leaf to be deleted is not the root   
                    if (curr == parent.left) // delete a left child
                        parent.left = null;
                    else                     // delete a right child
                        parent.right = null;
            else // delete a node with children, one or two
                if ((curr.left != null) && (curr.right != null)) { // two children
                    BSTNode surrogateParent = curr;
                    BSTNode replacement = curr.left;
                    while (replacement.right != null) {
                        surrogateParent = replacement;
                        replacement = replacement.right;
                    }
                // the greatest value of the left subtree is chosen as a replacement
                    curr.info = replacement.info; // the information is copied over
                // replacement must now be deleted. It has no children, or a left child.
                    if (curr == surrogateParent) {
                        // there was no right path in the left subtree
                        curr.left = replacement.left; // curr "adopts" the left
                        // child, if any, of the replacement. The replacement is jumped over.
                        replacement = null;
                    }
                    else  { // there was a right path in the left subtree
                        surrogateParent.right = replacement.left;
                        // replacement, the right child of its parent, is jumped over.
                        // The parent "adopts" its left child, if any.
                        replacement = null;
                    }
                } // End: if two children
                else { // delete a node with one child
                    if (parent == null)   // delete a root with one child
                        if (curr.left != null)  // there is a left child
                            tree = curr.left;   // update root
                        else                    // there is a right child
                            tree = curr.right;  // update root
                    // end: the node to be deleted was a root with one child
                    else  // delete a non-root node with one child
                        if (curr == parent.left)    // delete a left child ...
                            if (curr.right == null) // ... with a left child
                                parent.left = curr.left; 
                                // the parent "adopts" the grandchild           
                            else                    // ... with a right child
                                parent.left = curr.right; 
                                // The parent "adopts" the grandchild 
                        else // delete a right child ...
                            if (curr.right == null) // ... with a left child
                                parent.right = curr.left; 
                                // the parent "adopts" the grandchild
                            else                    // ... with a right child
                                parent.right = curr.right; 
                                // The parent "adopts" the grandchild
                } // end: else a node with one child
                curr = null; // curr no longer points to the deleted node
        }
    } // method
    
                
    public void inOrder(BSTNode root) {
        if (root != null) { // implicit base case: empty tree: do nothing
            inOrder(root.left); // process the left subtree
            System.out.println(root.info.key); // process the node itself
            inOrder(root.right); // process the right subtree
        }
    }
    
    public void preOrder(BSTNode root) {
        if (root != null) { // implicit base case: empty tree: do nothing
            System.out.println(root.info.key); // process the node itself
            preOrder(root.left);  // process the left subtree
            preOrder(root.right); // process the right subtree
        }
    }
    
    public void postOrder(BSTNode root) {
        if (root != null) { // implicit base case: empty tree: do nothing
            postOrder(root.left);  // process the left subtree
            postOrder(root.right); // process the right subtree
            System.out.println(root.info.key); // process the node itself
        }
    }
    
    public int nodeCount() {
    int count = 0;

    if (tree == null) {
        count = 0;
        //throw new NullPointerException();
    }
    else {
    if (tree.left != null) {
        count = 1;
        count += tree.left.nodeCount();
    }
    if (tree.right != null) {
        count = 1;
        count += tree.right.nodeCount();
    }
    }
    return count;
}
    
    public int leafCount() {
        int count = 0;

    if (tree != null && tree.left == null && tree.right==null) {
    return 1;
} else {
    if (tree.left != null) // added check
        count += tree.left.leafCount();
    if (tree.right != null) // added check
        count += tree.right.leafCount();
}

    return count; 
}
    
    private class BSTNode {
        NodeInfo info;
        BSTNode left, right;
        
        BSTNode(NodeInfo dataIn) {
            info = dataIn;
            left = null;
            right = null;
        }

    public int leafCount() {
        // TODO Auto-generated method stub
        return 0;
    }

    public int nodeCount() {
        // TODO Auto-generated method stub
        return 0;
    }
    
        /*
        BSTNode(NodeInfo dataIn, BSTNode l, BSTNode r) { // for test constructions
            info = dataIn;
            left = l;
            right = r;
        }
        */
    }

}

public class NodeInfo { // so that this type can be returned String key; // add other fields as needed!

        NodeInfo() {
                key = null;
        }

        NodeInfo(String keyIn) {
                key = keyIn;
        }

}

import static org.junit.Assert.assertTrue;

import org.junit.Test;


public class BSTrecTest { ```

    @Test
    public void testLeafCount() {
        BSTrec tree = new BSTrec();
        assertTrue("The number of leafs should be 0", tree.leafCount() == 0);
        tree.addRec("b", tree.tree, tree.parent, true);
        assertTrue("The number of leafs should be 1", tree.leafCount() == 1);
        tree.addRec("a", tree.tree, tree.parent, true);
        tree.addRec("e", tree.tree, tree.parent, true);
        tree.addRec("f", tree.tree, tree.parent, true);
        tree.addRec("g", tree.tree, tree.parent, true);
        assertTrue("The number of leafs should be 2", tree.leafCount() == 2);
        tree.addRec("c", tree.tree, tree.parent, true);
        /*
         *   b
         *  / \
         * a   e
         *    / \
         *   c   f
         *        \
         *         g
         */
        assertTrue("The number of leafs should be 3", tree.leafCount() == 3);
    }
    
    @Test
    public void testNodeCount() {
        BSTrec tree = new BSTrec();
        assertTrue("The number of nodes should be 0", tree.nodeCount() == 0);
        tree.addRec("b", tree.tree, tree.parent, true);
        assertTrue("The number of nodes should be 1", tree.nodeCount() == 1);
        tree.addRec("a", tree.tree, tree.parent, true);
        tree.addRec("e", tree.tree, tree.parent, true);
        tree.addRec("f", tree.tree, tree.parent, true);
        tree.addRec("g", tree.tree, tree.parent, true);
        assertTrue("The number of nodes should be 5", tree.nodeCount() == 5);
        tree.addRec("c", tree.tree, tree.parent, true);
        /*
         *   b
         *  / \
         * a   e
         *    / \
         *   c   f
         *        \
         *         g
         */
        assertTrue("The number of nodes should be 6", tree.nodeCount() == 6);
    }
    
}

Answer 1

请按照老师的要求尝试实施以下两种方法：

public int leafCount() {
    // TODO Auto-generated method stub
    return 0;
}

public int nodeCount() {
    // TODO Auto-generated method stub
    return 0;
}

如果你尝试了，但遇到了问题，那么你可以问一个问题。