二叉搜索树，一个测试不通过

Question

我写了一个二叉搜索树的代码，扩展了comparable并实现了一个接口。叶子的代码和辅助方法 countLeaves（包含在此处）确保除了一个 heightIsLogOfNumLeavesTreeIsPerfect() 之外的所有测试都通过。

// TODO：查看 Leaves 和 leaves 的辅助方法，看看我应该如何更改它以便此测试也能通过。

//编辑：我添加了整棵树 class

java.lang.AssertionError: 
Expected: <2>
     but: was <0>
Expected :<2>
Actual   :<0>

import org.junit.Test;
import org.junit.Before;
import org.junit.Rule;
import org.junit.rules.Timeout;
import static org.junit.Assert.*;

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.CoreMatchers.*;
import java.util.Arrays;
import java.util.stream.IntStream;
/**
 * Test class for a tree.
 */
public class TreeTest{
    @Rule public Timeout globalTimeout = Timeout.seconds(5);

    Tree<Integer> tree;
    int[] elementsInTree;
    int[] elementsNotInTree;

    @Before
    public void setUp() {
        /**
         * This tree should look like this:
         *
         *               8
         *             /  \
         *            3   10
         *           / \    \
         *          1   6    14
         *             / \   /
         *            4   7 13
         */
        tree = new Tree<>();
        elementsInTree = new int[] {8, 10, 14, 13, 3, 1, 6, 4, 7};
        for (int elem : elementsInTree) {
            tree.insert(elem);
        }
        elementsNotInTree = new int[] {34, -3, -10, 12, 74, 5};
    }

    @Test
    public void heightIsLogOfNumLeavesTreeIsPerfect() {
        // For a perfect tree, tree.height() == log2(tree.leaves()

        // Arrange
        Tree<Integer> tree = new Tree<>();
        int[] elements = new int[] {8, 3, 10, 1, 6, 9, 14};
        int numLeaves = 4;
        int logNumLeaves = (int) Math.round(Math.log(numLeaves) / Math.log(2));
        for (int elem : elements) {
            tree.insert(elem);
        }

        // Act
        int height = tree.height();
        // Assert
        assertThat(height, equalTo(logNumLeaves));
    }
}

**
 * An interface describing a generic Comparable
 */

public interface BSTInterface <T>{

    boolean search(T elem);
   
    boolean insert(T elem);

        int size();

    int height();
   
    int leaves();
}

/**
 * An Binary Search tree implementation of the comparable interface.
 * @param <T>
 */
public class Tree <T extends Comparable <T>> implements BSTInterface <T>{
    private int size;
    private Node root;
    public class Node{
        private Node Left;
        private Node Right;
        private T data;

        public Node(T data){
            this.data = data;
        }
        public Node getRight(){
            return Right;
        }

        public Node getLeft() {
            return Left;
        }

        public T getData() {
            return data;
        }
    }
    public Tree (){
        size = 0;
        root = null;
    }


    /**
     * Test for presence of a value.
     * @param elem
     * @return true/false
     */
    @Override
    public boolean search(T elem) {
        if(root == null ||elem == null){
        return false;
        }
        Node node = root;
        while(true){
            if(node.data.compareTo(elem) > 0){
                if(node.Right == null){
                    return false;
                } else{
                    node = node.Right;
                }
            } else if(node.data.compareTo(elem) == 0){
                break;
            } else{
                if(node.Left== null){
                    return false;
                }
                else{
                    node = node.Left;
                }
            }
        }
        return true;
    }

    /**
     * Add value to tree; duplicates are not allowed.
     * Return true if the element is not already present (and is thus inserted),
     * false otherwise.
     *
     * @param elem
     * @return true/false
     */
    @Override
    public boolean insert(T elem) {
        if (elem == null){
            return false;
        }
        if (root == null){
            root = new Node(elem);
            size++;
            return true;
        }
        Node node = root;
        while (true){
            if (node.data.compareTo(elem) > 0) {
                if (node.Right == null){
                    node.Right = new Node(elem);
                    size++;
                    break;
                } else {
                    node = node.Right;
                }

            } else if (node.data.compareTo(elem) == 0) {
                return false;
            } else {
                if (node.Left == null){
                    node.Left = new Node(elem);
                    size++;
                    break;
                } else {
                    node = node.Left;
                }
            }
        }
        return true;
    }


    /**
     * the number of elements in the tree
     * @return size.
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * The height of the tree.
     * The empty tree and the tree with only the root node both have height 0.
     * @return the height of the tree.
     */
    @Override
    public int height() {
        return countHeight(root);
    }
    /**
     * Helper method for height
     */
    private int countHeight(Node node){
        if(node == null) {
            return 0;
        }
        return Math.max(countHeight(node.Left), countHeight(node.Right));
    }

    /**
     * The number of leaves in the tree.
     * @return the amount of leaves the tree have.
     */
    @Override
    public int leaves() {
        return countLeaves(root);
    }
    /**
     * Helper method for leaves
     */
    private int countLeaves(Node node) {
        if (node == null) {
            return 0;
        }
        if (node.Left == null && node.Right == null) {
            return 1;
        }
        return countLeaves(node.Left) + countLeaves(node.Right);
    }


    /**
     * A string describing the tree
     * @return
     */
    public String toString(){
        String str = "[" + helpToString(root);
        if (str.length() > 1) {
            str = str.substring(0, str.length() - 2);
        } return str + "]";
    }

    /**
     * Helper method for toString
     */
    private String helpToString(Node node) {
        String str = "";
        if (node != null) {
            str += helpToString(node.Right);
            str += node.data + ", ";
            str += helpToString(node.Left);
        }
        return str;
      }
}

Answer 1

您的 countHeight 方法可以 return 零个或最多两个 return ，并且其中没有其他操作。仅使用 max 函数无法从零中获取大于零的值。

对于空树，您应该 return -1，否则 max(height(left) + 1, height(right) + 1)。每个 +1 占相应 parent-child 边的长度。

（从数学上讲，“空”树的高度通常是不确定的，但在这种情况下将其定义为 -1 会有很大帮助，所以让我们坚持下去。）

二叉搜索树，一个测试不通过

Binary Search Tree, one test does not go through

java

junit