java - 我们如何操作二叉搜索树

Question

--更新二--

平衡 BST 方法已修复并按要求运行。问题在于数组列表没有正确传递以创建新的“平衡”树。这是我的代码，供其他人受益。为大家的帮助干杯!

public void balanceBST(TreeNode <E> node) {
    if (node == null)
        System.out.println("There is no tree to balance");

    java.util.ArrayList<E> bstToArray = new java.util.ArrayList<E>();

    Iterator<E> treeToArray = iterator();
    while(treeToArray.hasNext()){
        bstToArray.add(treeToArray.next());
    }
    int low = 0;
    int high = bstToArray.size();
    clear();
    balanceHelper(bstToArray, low, high);

}
/** Helper method for the balanceBST method*/
public void balanceHelper(java.util.ArrayList<E> b, int low, int high) {
    if(low == high)
        return;

    int midpoint = (low+high)/2;
    insert(b.get(midpoint));
    balanceHelper(b, midpoint+1, high);
    balanceHelper(b, low, midpoint);
}

--更新一个--

我已经创建了一个平衡 BST 方法，但是，我无法调试为什么没有创建新的 BST，特别是考虑到我正在使用插入方法(其想法是迭代树，填充数组，然后使用中点递归地使用已排序的数组创建一个新的 BST，以便对新树进行排序)。我将不胜感激任何调试此问题的帮助。这是我的方法:-

/** Balance BST */
    public void balanceBST(TreeNode <E> node) {
        if (node == null)
            System.out.println("There is no tree to balance");

        java.util.ArrayList<E> bstToArray = new java.util.ArrayList<E>();
        Iterator<E> treeToArray = iterator();
        while(treeToArray.hasNext()){
            bstToArray.add(treeToArray.next());
        }
        //System.out.println(bstToArray);
        int low = 0;
        int high = bstToArray.size();

        balanceHelper(bstToArray, low, high);
        //System.out.println(bstToArray);
    }

    public void balanceHelper(java.util.ArrayList<E> b, int low, int high) {
        if(low == high)
            return;

        int midpoint = (low+high)/2;
        insert(b.get(midpoint));

        balanceHelper(b, midpoint+1, high);
        balanceHelper(b, low, midpoint);
    }

我是一名数据结构初学者，正在学习在线类(class)(基本上是自学)，并且有一些与 OOP、BST 相关的问题。

我有一个如下所示的 BST 类，可以在《Liang》《Java 简介》综合版一书中找到。不过，我正在努力通过添加许多方法(treeHeight、给定级别的节点数、平衡二叉搜索树以及其他一些方法)来增强它。

所以我编写了这些方法，但我对不同的对象以及如何在驱动程序/测试程序中调用这些方法有点迷失。这是我的问题(请原谅，因为它们对某些人来说可能微不足道):-

(1) 为什么我们将节点而不是树传递给这些方法？

(2) 当我在驱动程序中创建一棵树并尝试调用 treeHeight 方法时，我收到一条错误消息，告诉我传递了错误的参数(树而不是节点)....我知道错误并理解为什么会出现它，但这里有点困惑，因为我在网上看到的大多数示例都将节点传递给 treeHeight 方法，并且通过在 BST 中插入元素，我们确实有节点，但我们如何调用这样的方法呢？这是我对 OOP 缺乏理解的地方。

(3) 如何将二叉树的内容插入数组(使用 inorder 方法排序)，特别是给定如下所示的迭代器内部类，或者我不使用该内部类？我正在尝试创建一种平衡树的方法，方法是将树的内容推出到数组中，然后迭代该数组，将其(递归地)分成两半并创建平衡的 BST。由于数组已排序，并且 BST 的左子树的元素小于根，右子树的元素大于根，所以我能够从数组的中间开始，选择根，然后递归地构建平衡 BST。

这是我的测试程序代码片段:

BST<Integer> b1 = new BST<Integer>();
b1.insert(1);
b1.insert(2);
b1.insert(3);
b1.insert(4);
// How do I call the treeHeight on BST?
// I tried b1.treeHeight() but....
// and I tried treeHeight(BST) but....
// am a bit lost

这是带有我的方法的 BST 类(请注意，某些方法可能不正确，我仍在研究它们......我确信一旦我掌握了基础知识，我就会弄清楚它们):

import java.lang.Math;

public class BST<E extends Comparable<E>> {

    protected TreeNode<E> root;
    protected int size = 0;

    /** Create a default binary tree */
    public BST() {
    }

    /** Create a binary tree from an array of objects */
    public BST(E[] objects) {
        for (int i = 0; i < objects.length; i++)
            insert(objects[i]);
    }

    /** Returns true if the element is in the tree */
    public boolean search(E e) {
        TreeNode<E> current = root; // Start from the root

        while (current != null) {
            if (e.compareTo(current.element) < 0) {
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                current = current.right;
            } else
                // element matches current.element
                return true; // Element is found
        }

        return false;
    }

    /**
     * Insert element o into the binary tree Return true if the element is
     * inserted successfully
     */
    public boolean insert(E e) {
        if (root == null)
            root = createNewNode(e); // Create a new root
        else {
            // Locate the parent node
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
            while (current != null)
                if (e.compareTo(current.element) < 0) {
                    parent = current;
                    current = current.left;
                } else if (e.compareTo(current.element) > 0) {
                    parent = current;
                    current = current.right;
                } else
                    return false; // Duplicate node not inserted

            // Create the new node and attach it to the parent node
            if (e.compareTo(parent.element) < 0)
                parent.left = createNewNode(e);
            else
                parent.right = createNewNode(e);
        }

        size++;
        return true; // Element inserted
    }

    protected TreeNode<E> createNewNode(E e) {
        return new TreeNode<E>(e);
    }

    /** Inorder traversal from the root */
    public void inorder() {
        inorder(root);
    }

    /** Inorder traversal from a subtree */
    protected void inorder(TreeNode<E> root) {
        if (root == null)
            return;
        inorder(root.left);
        System.out.print(root.element + " ");
        inorder(root.right);
    }

    /** Postorder traversal from the root */
    public void postorder() {
        postorder(root);
    }

    /** Postorder traversal from a subtree */
    protected void postorder(TreeNode<E> root) {
        if (root == null)
            return;
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.element + " ");
    }

    /** Preorder traversal from the root */
    public void preorder() {
        preorder(root);
    }

    /** Preorder traversal from a subtree */
    protected void preorder(TreeNode<E> root) {
        if (root == null)
            return;
        System.out.print(root.element + " ");
        preorder(root.left);
        preorder(root.right);
    }

    /**
     * This inner class is static, because it does not access any instance
     * members defined in its outer class
     */
    public static class TreeNode<E extends Comparable<E>> {
        protected E element;
        protected TreeNode<E> left;
        protected TreeNode<E> right;

        public TreeNode(E e) {
            element = e;
        }
    }

    /** Get the number of nodes in the tree */
    public int getSize() {
        return size;
    }

    /** Returns the root of the tree */
    public TreeNode<E> getRoot() {
        return root;
    }

    /** Return tree height - my own method */
    public int treeHeight(TreeNode <E> node) {
        // height of empty tree = ZERO
        if (node == null)
            return 0;

        int leftHeight = treeHeight(node.left);
        int rightHeight = treeHeight(node.right);

        if (leftHeight > rightHeight)
            return leftHeight;
        else
            return rightHeight;
    }

    /** Return the no of nodes at given level - my own method */
    public int numberOfNodesAtLevel(TreeNode <E> node, int level) {
        if (root == null)
            return 0;
        if (level == 0)
            return 1;
        return numberOfNodesAtLevel(node.left, level-1) + numberOfNodesAtLevel(node.right, level-1);
    }

    /** Return the no of nodes in binary tree - my own method  */
    public int numberOfNodes(TreeNode <E> node) {
        if (node == null)
            return 0;
        return 1 + numberOfNodes(node.left) + numberOfNodes(node.right);
    }

    /** Calculate ACE - my own method  */
    public double calculateACE(TreeNode <E> node) {
        int n = numberOfNodes(node);
        int treeHeight = treeHeight(node);
        int sum = 0;
        int level = 0;
        for (level=0, sum=0; level < treeHeight; level++ ) {
            sum += numberOfNodesAtLevel(node, level) * (level + 1);
        }
       double ACE = sum / n;
       return ACE;
    }

    /** Calculate MinACE - my own method */
    public double calculateMinACE(TreeNode <E> node) {
        int n = numberOfNodes(node);
        int treeHeight = (int) Math.floor((Math.log(n))+1);
        int sum = 0;
        int level = 0;
        for (level=0, sum=0; level < treeHeight; level++ ) {
            sum += numberOfNodesAtLevel(node, level) * (level + 1);
        }
       double ACE = sum / n;
       return ACE;
    }

    /** Calculate MaxACE - my own method */
    public double calculateMaxACE(TreeNode <E> node) {
        int n = numberOfNodes(node);
        int treeHeight = n;
        int sum = 0;
        int level = 0;
        for (level=0, sum=0; level < treeHeight; level++ ) {
            sum += numberOfNodesAtLevel(node, level) * (level + 1);
        }
       double ACE = sum / n;
       return ACE;
    }

    /** Needs Balancing - my own method */
    public boolean needsBalancing(TreeNode <E> node) {
        double k = 1.25;
        double AceValue = calculateACE(node);
        double MinAceValue = calculateMinACE(node);
        if(AceValue > (MinAceValue*k))
            return true;
        return false;

    }

    /** Balance BST  - my own method, not complete yet */
    public void balanceBST(TreeNode <E> node) {
        int size = numberOfNodes(node);

    }

    /** Returns a path from the root leading to the specified element */
    public java.util.ArrayList<TreeNode<E>> path(E e) {
        java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();
        TreeNode<E> current = root; // Start from the root

        while (current != null) {
            list.add(current); // Add the node to the list
            if (e.compareTo(current.element) < 0) {
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                current = current.right;
            } else
                break;
        }

        return list; // Return an array of nodes
    }

    /**
     * Delete an element from the binary tree. Return true if the element is
     * deleted successfully Return false if the element is not in the tree
     */
    public boolean delete(E e) {
        // Locate the node to be deleted and also locate its parent node
        TreeNode<E> parent = null;
        TreeNode<E> current = root;
        while (current != null) {
            if (e.compareTo(current.element) < 0) {
                parent = current;
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                parent = current;
                current = current.right;
            } else
                break; // Element is in the tree pointed at by current
        }

        if (current == null)
            return false; // Element is not in the tree

        // Case 1: current has no left children
        if (current.left == null) {
            // Connect the parent with the right child of the current node
            if (parent == null) {
                root = current.right;
            } else {
                if (e.compareTo(parent.element) < 0)
                    parent.left = current.right;
                else
                    parent.right = current.right;
            }
        } else {
            // Case 2: The current node has a left child
            // Locate the rightmost node in the left subtree of
            // the current node and also its parent
            TreeNode<E> parentOfRightMost = current;
            TreeNode<E> rightMost = current.left;

            while (rightMost.right != null) {
                parentOfRightMost = rightMost;
                rightMost = rightMost.right; // Keep going to the right
            }

            // Replace the element in current by the element in rightMost
            current.element = rightMost.element;

            // Eliminate rightmost node
            if (parentOfRightMost.right == rightMost)
                parentOfRightMost.right = rightMost.left;
            else
                // Special case: parentOfRightMost == current
                parentOfRightMost.left = rightMost.left;
        }

        size--;
        return true; // Element inserted
    }

    /** Obtain an iterator. Use inorder. */
    public java.util.Iterator<E> iterator() {
        return new InorderIterator();
    }

    // Inner class InorderIterator
    private class InorderIterator implements java.util.Iterator<E> {
        // Store the elements in a list
        private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
        private int current = 0; // Point to the current element in list

        public InorderIterator() {
            inorder(); // Traverse binary tree and store elements in list
        }

        /** Inorder traversal from the root */
        private void inorder() {
            inorder(root);
        }

        /** Inorder traversal from a subtree */
        private void inorder(TreeNode<E> root) {
            if (root == null)
                return;
            inorder(root.left);
            list.add(root.element);
            inorder(root.right);
        }

        /** More elements for traversing? */
        public boolean hasNext() {
            if (current < list.size())
                return true;

            return false;
        }

        /** Get the current element and move to the next */
        public E next() {
            return list.get(current++);
        }

        /** Remove the current element */
        public void remove() {
            delete(list.get(current)); // Delete the current element
            list.clear(); // Clear the list
            inorder(); // Rebuild the list
        }
    }

    /** Remove all elements from the tree */
    public void clear() {
        root = null;
        size = 0;
    }
}

Answer 1

(1) 为什么我们将节点而不是树传递给这些方法？

答案:
BST 由其根定义，您可以实现接受根或树的方法 - 这是一个任意决定。

(2) ...我在网上看到过将一个节点传递给treeHeight方法，并通过在BST中插入元素，我们确实有节点，但是我们如何调用这样的方法呢？这是我对 OOP 缺乏理解的表现。

答案:
在您给出的示例中，您应该这样调用它:

BST<Integer> b1 = new BST<Integer>();
b1.insert(1);
b1.insert(2);
b1.insert(3);
b1.insert(4);
int h = b1.treeHeight(b1.getRoot()); // get the height

(3) 如何将二叉树的内容插入数组。

答案:
我没有调试以下代码，但我确信它会让您很好地了解它是如何完成的:

int arraySize = b1.getSize();
Integer[] treeToArray = new Integer[arraySize];
iterator iter = b1.iterator();
int i=0;
while(iter.hasNext()) {
    treeToArray[i++] = (Integer)iter.next();
}

(4) 为什么 treeHeight() 不起作用(总是返回零)？

答案:
由于它有一个错误，因此修复方法如下:

/** Return tree height - my own method */
    public int treeHeight(TreeNode <E> node) {
        // height of empty tree = ZERO
        if (node == null)
            return 0;

        int leftHeight = treeHeight(node.left);
        int rightHeight = treeHeight(node.right);

        if (leftHeight > rightHeight)
            return leftHeight+1; // bug was here: you should return the height of the child + 1 (yourself)
        else
            return rightHeight+1; // and here
    }