Java - 平衡 BinarySearchTree 的 JUnit 测试

Question

我已经编写了一个可用的二叉搜索树，并希望构建一些 JUnit 测试来配合它。我正在研究三项:一项用于查找最大值(按序遍历)，一项用于删除该最大值，一项用于检查我的二叉树是否平衡。我已经写了前两个，但不太清楚如何完成最后一个测试——检查平衡。我希望得到一些指导，因为我觉得我忽略了一些东西。

我的测试方法:

public class BSTreePreLabTest {
@Test
public void testFindMax() {
    BSTree<Integer> tree = new BSTree<Integer>();
    tree.addElement(15);
    tree.addElement(16);
    tree.addElement(17);
    tree.addElement(18);
    tree.addElement(19);
    tree.addElement(20);    
    assertEquals("20", tree.findMax().toString());
}


@Test
public void testRemoveMax() {
    BSTree<Integer> tree = new BSTree<Integer>();
    tree.addElement(15);
    tree.addElement(16);
    tree.addElement(17);
    tree.addElement(18);
    tree.addElement(19);
    tree.addElement(20);    
    tree.removeMax();
    assertEquals("Inorder traversal: [15, 16, 17, 18, 19]", tree.toString());
}

还有我的主要 BinarySearchTree 方法，供引用(如果需要):

public class BSTree<T> {

private BSTreeNode<T> root = null;
private int count;

public BSTree(T element) {
    root = new BSTreeNode<T>(element);
    count = 1;
}

public BSTree() {
    root = null;
    count = 0;
}

public void addElement(T element) {
    if (isEmpty()) {
        root = new BSTreeNode<T>(element);
    } 
    else {
        BSTreeNode<T> current = root;
        BSTreeNode<T> previous = null;
        Comparable<T> comparableElement = (Comparable<T>) element;
        while (current != null) {
            if (comparableElement.compareTo(current.getElement()) < 0) {
                previous = current;
                current = current.getLeft();
            } 
            else {
                previous = current;
                current = current.getRight();
            }
        }
        BSTreeNode<T> newNode = new BSTreeNode<T>(element);
        if (comparableElement.compareTo(previous.getElement()) < 0) 
            previous.setLeft(newNode);          
        else
            previous.setRight(newNode);
    }
    count++;
}

public boolean isEmpty() {
    return root == null;
}

public int size() {
    return count;
}

public T find(T targetElement) throws ElementNotFoundException {
    BSTreeNode<T> current = findNode(targetElement, root);

    if (current == null)
        throw new ElementNotFoundException("BSTree");

    return (current.getElement());
}

private BSTreeNode<T> findNode(T targetElement, BSTreeNode<T> next) {
    if (next == null)
        return null;

    if (next.getElement().equals(targetElement))
        return next;

    BSTreeNode<T> temp = findNode(targetElement, next.getLeft());

    if (temp == null)
        temp = findNode(targetElement, next.getRight());

    return temp;
}

public T removeElement(T targetElement) throws ElementNotFoundException {
    T result = null;

    if (isEmpty())
        throw new ElementNotFoundException("BSTree");
    else {
        BSTreeNode<T> parent = null;
        if (((Comparable<T>) targetElement).equals(root.getElement())) {
            result = root.getElement();
            BSTreeNode<T> temp = replacement(root);
            if (temp == null)
                root = null;
            else {
                root.setElement(temp.getElement());
                root.setRight(temp.getRight());
                root.setLeft(temp.getLeft());
            }
        } else {
            parent = root;
            if (((Comparable) targetElement).compareTo(root.getElement()) < 0)
                result = removeElement(targetElement, root.getLeft(), parent);
            else
                result = removeElement(targetElement, root.getRight(), parent);
        }
    }
    count--;
    return result;
}

private T removeElement(T targetElement, BSTreeNode<T> node,
        BSTreeNode<T> parent) throws ElementNotFoundException {
    T result = null;

    if (node == null)
        throw new ElementNotFoundException("BSTree");
    else {
        if (((Comparable<T>) targetElement).equals(node.getElement())) {
            result = node.getElement();
            BSTreeNode<T> temp = replacement(node);
            if (parent.getRight() == node)
                parent.setRight(temp);
            else
                parent.setLeft(temp);
        } else {
            parent = node;
            if (((Comparable) targetElement).compareTo(node.getElement()) < 0)
                result = removeElement(targetElement, node.getLeft(),
                        parent);
            else
                result = removeElement(targetElement, node.getRight(),
                        parent);
        }
    }

    return result;
}

private BSTreeNode<T> replacement(BSTreeNode<T> node) {
    BSTreeNode<T> result = null;

    if ((node.getLeft() == null) && (node.getRight() == null))
        result = null;

    else if ((node.getLeft() != null) && (node.getRight() == null))
        result = node.getLeft();

    else if ((node.getLeft() == null) && (node.getRight() != null))
        result = node.getRight();

    else {
        BSTreeNode<T> current = node.getRight();
        BSTreeNode<T> parent = node;

        while (current.getLeft() != null) {
            parent = current;
            current = current.getLeft();
        }

        current.setLeft(node.getLeft());
        if (node.getRight() != current) {
            parent.setLeft(current.getRight());
            current.setRight(node.getRight());
        }

        result = current;
    }

    return result;
}

public String toString() 
{
    ArrayList<T> temp = new ArrayList<T>();
    inOrder(root, temp);
    return "Inorder traversal: " + temp.toString();
}

public Iterator<T> iterator()
{
    return iteratorInOrder();
}

public Iterator<T> iteratorInOrder()
{
    ArrayList<T> tempList = new ArrayList<T>();
    inOrder(root, tempList);

    return tempList.iterator();
}

public T findMax(){
    T result = null;
    if (isEmpty())
        throw new ElementNotFoundException ("binary tree");
    else {
        BSTreeNode<T> current = root;

        while (current.getRight() != null)
            current = current.getRight();

        result = current.getElement();
    }

return result;
}

public T removeMax(){
    T result = null;

    if (isEmpty())
         throw new ElementNotFoundException("binary tree");
    else 
    {
       if (root.getRight() == null) 
       {
          result =  root.getElement();
          root = root.getLeft();
       }
       else 
       {
            BSTreeNode<T> parent = root;
            BSTreeNode<T> current = root.getRight();

            while (current.getRight() != null) 
            {
               parent = current;
               current = current.getRight();
            }

            result =  current.getElement();
            parent.setRight(current.getLeft());
         }

       count--;
    }

    return result;
}

protected void inOrder(BSTreeNode<T> node, ArrayList<T> tempList) {
    if (node != null) {
        inOrder(node.getLeft(), tempList);
        tempList.add(node.getElement());
        inOrder(node.getRight(), tempList);
    }
}

}

Answer 1

你可以编写一个函数来计算左右子树的高度

int height(Node node) 
{
    if (node == null)
        return 0;

    return 1 + Math.max(height(node.left), height(node.right));
}

然后，您可以编写另一个方法来检查树是否平衡

boolean isBalanced(Node node) 
{
    int lh;
    int rh;

    if (node == null)
        return true;

    lh = height(node.left);
    rh = height(node.right);

    if (Math.abs(lh - rh) <= 1
            && isBalanced(node.left)
            && isBalanced(node.right)) {
        return true;
    }
    return false;
}

然后，您可以编写一个 JUnit 测试用例来测试您的 isBalanced()。

希望这会有所帮助!