我们如何操作二叉搜索树

• 更新TWO--

balancer 的BST方法根据需要固定和运行 . 问题是arraylist没有被正确传递以创建一个新的“ balancer ”树 . 这是我的代码，让其他人受益 . 欢呼大家帮忙！

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

• 更新一件 -

我已经创建了一个 balancer BST方法，但是，我无法调试为什么没有创建新的BST，特别是考虑到我使用的是insert方法（想法是迭代树，填充数组然后创建一个新的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);
    }

我是一名初学数据结构的学生参加在线课程（基本上是自学），并且有许多与OOP，BST有关的问题 .

我有一个BST类，可以在Liang，Java简介，综合版书籍中找到 . 但是，我正在努力通过添加许多方法来增强它（treeHeight，在给定级别没有节点， balancer 二叉搜索树以及更多） .

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

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

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

（3）如何将二叉树的内容推送到数组中（使用inorder方法排序），特别是给定迭代器内部类，如下所示，或者我不使用该内部类？我正在尝试创建一个方法，通过将树的内容推出到数组中来 balancer 树，然后迭代数组，将其（递归地）分成两半并创建 balancer 的BST . 由于数组已排序且BST的左子树的元素小于根，右子树的元素大于根，因此可以从数组的中间开始，选择root，然后递归地通过构建 balancer 的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;
    }
}