如何为二叉搜索树编写test LeavesCorrectWhentreIsPerfect（）

Question

我实现了一个二进制搜索树，并为它编写了一个测试类（在JUNIT测试中）。除了一次考试，所有的考试都通过了。当我调试代码时，测试leavesIsTrue tWhenTreeIs完美（）会得到一条消息。

预期：

请记住，所有其他测试都会通过，我不认为这是树代码的问题。

你如何理解测试的描述？

/**
 * A Binary Search tree.
 */
public class Tree <T extends Comparable <T>> implements BinaryTree <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 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;
        }
        if (node.Left == null && node.Right == null) {
            return 0;
        }
        return 1 + 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;
      }
}

测试等级：

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 leavesIsTwoWhenPerfectTreeHasThreeNodes() {
        // Arrange
        Tree<Integer> tree = new Tree<>();
        // root must be smaller than one and larger than the other child
        tree.insert(1338); // root
        tree.insert(1337); // smaller child
        tree.insert(1396); // larger child

        // Act
        int numLeaves = tree.leaves();
        // Assert
        assertThat(numLeaves, equalTo(2));
    }

    @Test
    public void leavesIsCorrectWhenTreeIsPerfect() { //TEST
        // A perfect tree has all leaves at the same depth, and all internal nodes
        // (i.e. non-leaves) have two children
        //
        // This test should assert that a perfect tree with 2*n-1 nodes total,
        // has exactly n leaves (i.e. that Tree.leaves() returns n).
        //
        // An example is the perfect three-node tree from the test above:
        //
        //                        (1338)
        //                        /    \
        //                    (1337)  (1396)

        // You have to construct our own tree here, with n >= 4
        int n = 4;
        int nodes = 2*n-1;
       for(int i = 0; i < nodes ; i++) {
           tree.insert(i);
       }
         int leaves = tree.leaves();
         assertThat(leaves,equalTo(n));
    }

    @Test
    public void leavesIsOneWhenElementsWereInsertedInAscendingOrder() {
        // Arrange
        Tree<Integer> tree = new Tree<>();
        // insert elements in ascending order => all elements are inserted to the right
        int numElements = 100;
        for (int i = 0; i < numElements; i++) {
            tree.insert(i);
        }

        // Act
        int numLeaves = tree.leaves();
        // Assert
        assertThat(numLeaves, equalTo(1));
    }

    // Tests for height
    @Test
    public void heightIsZeroWhenTreeIsEmpty() {
        // Arrange
        Tree<Integer> emptyTree = new Tree<>();
        // Act
        int height = emptyTree.height();
        // Assert
        assertThat(height, equalTo(0));
    }


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

    // Tests for insert/height
    @Test
    public void insertValuesInAscendingOrderIncrementsHeight() {
        // When inserting elements in ascending order, each element is inserted
        // to the right of the deepest node, so the height should increment by
        // 1 for each element inserted.
        Tree <Integer> tree = new Tree<>();
        int val = 100;
        for(int i = 0; i < val; i++){
            tree.insert(i);
        }
            int treeHeight = tree.height();
        treeHeight++;
            assertThat(val,equalTo(treeHeight));
    }
}

Answer 1

leaves方法计算您拥有的假期数。你的期望是有四片叶子。然而，结果是5。你用来数树叶的方法似乎是正确的：

    /**
     * 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);
    }

它基本上统计没有子项的项目（以广度优先的搜索方式）。原因可能是什么？你的主要任务是找出你的树长得有多像。根据您的insert方法：

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

知道测试中的2*n-1是7，所以输入的数字0, 1, 2, 3, 4, 5, 6，在我看来树可能是

            0
           /
          1
         /
        2
       /
      3
     /
    4
   /
  5
 /
6

它将有一个单独的叶子，因为如果节点的值大于您要插入的项目，那么您将其添加到节点的右侧。然而，你的测试结果是不同的。因为某些原因，你有5片叶子。你需要首先找出你的表在结尾的样子，然后用调试器检查insert方法。