二叉搜索树

二叉搜索树（没有重复元素）的特征是：对于树中的每一个节点，它的左子树中的节点的值都小于该节点的值，而它的右子树中节点的值都大于该节点的值。

表示二叉搜索树

二叉搜索树（Binary Search Tree, BST）可以用一个链式节点的集合来表示二叉树。 每个节点都包含一个数值和两个称为left和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;
    }
}   

TreeNode<Integer> root = new TreeNode<>(60);

变量root指向根节点。如果树为空，root的值为null。

树的遍历

二叉树分为根节点、左子树和右子树，分别表示为 +、1、2。
二叉树本身是递归定义的，相应的遍历很自然就成为一种递归问题。

递归遍历操作的关键点是递归体和递归出口：

• 递归出口是二叉树的空子树或叶节点，此时为空操作，递归不继续进行，只能回退；
• 递归体是对二叉树根节点或左、右子树进行相应处理。

基于递归的遍历算法易于编写，操作简单，但可读性差，系统需要维护相应的工作栈，效率不是很高。递归转化为非递归的基本思想是如何实现原本是系统完成的递归工作栈，为此，可以仿照递归执行过程中工作栈状态变化而得到。

对二叉树进行前序、中序和后序遍历时都开始于根节点或结束于根节点，经由路线也相同。彼此差别在于对节点访问时机的选择不同。三种遍历方式都是沿着左子树不断深入下去，当到达二叉树左下节点而无法往下深入时，就向上逐一返回，行进到最近深入时曾遇到节点的右子树，然后进行同样的深入和返回，直到最终从根节点的右子树返回到根节点。
这样，遍历时返回顺序与深入节点顺序恰好相反，因此可以在实现二叉树遍历过程中，使用一个工作栈来保存当前深入到的节点信息，以供后面返回需要时使用。

中序遍历(inorder traversal)

遍历顺序为： 1+2 可以递增顺序显示BST中所有节点。
中序遍历的黄金口诀：当前节点为空，从栈中弹出一个元素，当前节点向右移动；当前节点不为空，压栈，当前节点向左移动

• 中序遍历访问左子二叉树
• 访问根节点
• 中序遍历访问右子二叉树

inorder递归遍历

public void inorder() {
    inorder(root);      
}

protected void inorder(TreeNode<E> root) {
    if (root == null)
        return;
    inorder(root.left);  // 递归遍历左子树
    System.out.print(root.element + " ");  // 递归遍历根节点
    inorder(root.right);  // 递归遍历右子树 1+2
}

中序非递归遍历

public void inorder() {
    inorder(root);
}

protected void inorder(TreeNode<E> root) {
    if (root == null) 
        return;
    java.util.Stack<TreeNode<E>> stack = new java.util.Stack<>();
    TreeNode<E> current = root;
    while (!stack.empty() || current != null) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {            
            TreeNode<E> node = stack.pop();
            System.out.print(node.element + " ");
            current = node.right;
        }
    }
}

前序遍历(preorder traversal)

+12 深度优先遍历法(depth-first traversal)与前序遍历法相同。

• 访问根节点
• 前序遍历访问左子二叉树
• 前序遍历访问右子二叉树

preorder递归遍历

public void preorder() {
    preorder(root);
}
protected void preorder(TreeNode<E> root) {
    if (root == null)
        return;
    System.out.println(root.element + " ");  // 递归遍历根节点
    preorder(root.left);  // 递归遍历左子树
    preorder(root.right);  // 递归遍历右子树 +12
}

前序非递归遍历

public void preorder() {
    preorder(root);
}    
protected void preorder(TreeNode<E> root) {
    if (root == null) 
        return;
    Stack<TreeNode<E>> stack = new Stack<>();
    stack.push(root);

    while (!stack.empty()) {
        TreeNode<E> node = stack.pop();
        System.out.print(node.element + " ");

        // Push the right child onto the stack 
        // first so the left is processed first
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

后序遍历(postorder traversal)

12+

• 后序遍历访问左子二叉树
• 后序遍历访问右子二叉树
• 访问根节点

postorder递归遍历

public void postorder() {
    postorder(root);
}
protected void postorder(TreeNode<E> root) {
    if (root == null)
        return;
    postorder(root.left);  // 递归遍历左子树
    postorder(root.right);  // 递归遍历右子树
    System.out.println(root.element + " ");  // 递归遍历根节点 12+
}

后序非递归遍历

public void postorder() {
    postorder(root);
}

protected void postorder(TreeNode<E> root) {
    if (root == null) return;

    // Create two stacks
    Stack<TreeNode<E>> stack1 = new Stack<>();
    Stack<TreeNode<E>> stack2 = new Stack<>();

    // push root to stack1
    stack1.push(root);
    while (!stack1.empty()) {
        // Pop node from stack1 and push onto stack2
        TreeNode<E> node = stack1.pop();
        stack2.push(node);

        if (node.left != null)
            stack1.push(node.left);
        if (node.right != null)
            stack1.push(node.right);
    }

    // Display elements in stack2
    while (!stack2.empty()) {
        System.out.print(stack2.pop().element + " ");
    }
}

广度优先遍历(breadth-first traversal)

广度优先遍历

public void breadthFirstTraversal() {
    if (root == null)
        return;

    // Queue Deque Linkedlist
    java.util.Queue<TreeNode<E>> queue = new java.util.LinkedList<>();  

    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode<E> current = queue.element();
        if (current.left != null) {
            queue.add(current.left);
        }
        if (current.right != null) {
            queue.add(current.right);
        }
        System.out.println(queue.remove().element + " ");
    }
}

搜索一个元素

二叉搜索树中搜索一个元素，可以从根节点向下扫描，知道找到匹配元素，或者达到一棵空子树为止。

在BST中搜索一个元素

public boolean search(E e) {
    TreeNode<E> current = root; // 当前指针指向根节点
    while (current != null) {
        if (e.compareTo(current.element) < 0) {
            current = current.left;  // 比当前指针的元素小，则往左
        } else if (e.compareTo(current.element) > 0) {
            current = current.right; // 比当前指针的元素大，则往右
        } else {  // 元素匹配
            return true;  // 找到元素 return true
        }
    }
    return false;
}

插入一个元素

BST中插入一个元素，需要确定在书中插入的位置，关键思路是确定新节点的父节点所在的位置。

• 如果树是空的，使用新元素创建一个根节点；
• 否则，寻找新节点的父节点的位置
• 为该元素创建一个新节点，如果新元素的值小于父元素的值，左子节点；如果新元素的值大于父元素的值，右子节点；BST没有重复元素，重复则不插入

在BST中插入一个元素

public boolean insert(E e) {
    if (root == null) {
        root = createNewNode(e);  // 创建一个节点，树为空该节点成为根节点
    } else {
        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; // 元素已经在树中，return false
            }
        }
        // 为元素e创建一个节点
        if (e.compareTo(parent.element) < 0) {
            parent.left = createNewNode(e);
        } else {
            parent.right = createNewNode(e);
        }
    }
    size++;
    return true;
}
public TreeNode<E> createNewNode(E e) {
    return new TreeNode<>(e);
}

删除BST中的一个元素

为了从一棵二叉搜索树中删除一个元素，首先需要定位该元素位置，然后再删除该元素以及重新连接树前，考虑两种情况–该节点有或者没有左子节点。
情况1：当前节点没有左子结点。只需将该节点的父节点和该节点的右子节点相连。如果当前节点是叶子节点，属于情况1；

情况2：当前节点有左子结点。假设rightMost指向包含current节点的左子树中的最大元素的节点，而parentOfRightMost指向rightMost节点的父节点。使用rightMost节点中的元素替代current节点中的元素值，将parentOfRightMost节点和rightMost节点的左子节点相连，然后删除rightMost节点。 rightMost作为最大值不能有右节点，但是可能会有左子节点！

从BST中删除一个元素

public boolean delete(E e) {
    // 如果current为root,那么parent为null
    TreeNode<E> parent = null;  // 指向current节点的父节点
    TreeNode<E> current = root; // 指向二叉搜索树中包含该元素的节点
    
    while (current != null) { // 递归寻找current节点
        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; // 找到包含e的current节点
        }
    }
    
    if (current == null) {
        return false; // 元素不在树内
    }
    
    // 情况1：当前节点没有左子节点
    if (current.left == null) {
        //只需将该节点的父节点和该节点的右子节点相连
        if (parent == null) {
            root = current.right;
        } else {
            if (e.compareTo(parent.element) < 0) {
                parent.left = current.right;  // e是父节点的左子结点
            } else {
                parent.right = current.right; // e是父节点的右子结点
            }
        }
    } else { 
        // 情况2：当前节点有左子节点
        TreeNode<E> parentOfRightMost = current;  // rightMost节点的父节点
        TreeNode<E> rightMost = current.left;   // 当前节点的左子树最右端的节点
        
        while (rightMost.right != null) {
            parentOfRightMost = rightMost;
            rightMost = rightMost.right;  // 向右不断递归
        }
        // 用rightMost节点的内容替换current中的内容
        current.element = rightMost.element;
        // rightMost的父节点和rightMost的左子节点相连
        if (parentOfRightMost.right == rightMost) {
            // rightMost是右子节点
            parentOfRightMost.right = rightMost.left;
        } else {
            // rightMost是左子节点
            parentOfRightMost.left = rightMost.left;
        }
    }
    size--;
    return true;
}

找出叶子节点和非叶子结点

找出叶子节点的个数

public int getNumberOfLeaves() {
    return getNumberOfLeaves(root);
}

protected int getNumberOfLeaves(TreeNode<E> root) {
    if (root ==null)
        return 0;
    // If node has no children return 1 
    // else return the sum of all the leaves
    return root.left == null && root.right == null ? 
            1 : getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right);
}

找出非叶子节点的个数

public int getNumberOfNonLeaves() {
    return getNumberOfNonLeaves(root);
} 

protected int getNumberOfNonLeaves(TreeNode<E> root) {
    if (root == null) return 0;
    
    // If node has children return 0
    // else return 1 plus the sum of the nonleaves
    return (root.left == null && root.right == null) ? 0 : 
        1 + getNumberOfNonLeaves(root.left) + 
        getNumberOfNonLeaves(root.right) ;
}

实现equals和clone方法

树的equals方法

public boolean equals(BST<E> tree) {
    if (tree.size != size) return false;
    return equals(root, tree.root);
}

/** Equals helper */
protected boolean equals(TreeNode<E> root1, TreeNode<E> root2) {
    if (root1 == root2) return true;
    if (root1 == null || root2 == null) return false;
    return root1.element.equals(root2.element) &&
    equals(root1.left, root2.left) &&
    equals(root1.right, root2.right);
}

树的clone方法

public BST<E> clone() throws CloneNotSupportedException {
    BST<E> cloneBST = new BST<>();
    clone(cloneBST, root);
    return cloneBST;
}

/** Clone helper */
protected void clone(BST<E> clone, TreeNode<E> root) {
    if (root == null) return;
    clone.insert(root.element);
    clone(clone, root.left);
    clone(clone, root.right);
}

BST类

使用一个Tree的接口来定义树的所有常用操作，提供AbstractTree的抽象类部分实现了Tree，最后实现了BST类。

Tree接口

Tree.java 接口定义树的常用操作

public interface Tree<E> extends Iterable<E>{
    /** Return true 如果搜索成功 */
    boolean search(E e);
    
    /** 向二叉搜索树插入元素  Return true 如果成功添加 */   
    boolean insert(E e);
    
    /** Return true 如果成功从树中删除元素 */  
    boolean delete(E e);
    
    /** 中序遍历打印节点 1+2 */ 
    void inorder();
    
    /** 后序遍历打印节点 12+ */ 
    void postorder();
    
    /** 前序遍历打印节点 +12 */ 
    void preorder();
    
    /** 广度优先遍历打印节点 */   
    void breadthFirstTraversal();
    
    /** 返回树中节点数 */  
    int getSize();
    
    /** Return true 如果树为空 */
    boolean isEmpty();  
}

AbstractTree抽象类

AbstractTree.java 抽象类部分地实现了Tree

public abstract class AbstractTree<E> implements Tree<E> {
    @Override /** 中序遍历打印节点 1+2 */   
    public void inorder() {
    }

    @Override /** 后序遍历打印节点 12+ */   
    public void postorder() {
    }

    @Override /** 前序遍历打印节点 +12 */
    public void preorder() {
    }

    @Override /** Return true 如果树为空 */
    public boolean isEmpty() {
        return getSize() == 0;
    }
}

具体的BST

BST.java 具体定义了BST

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

/* 因为每个节点只遍历一次，遍历的时间复杂度都是O(n)
 * 搜索、插入和删除的时间复杂度是树的高度。
 * 最差的情况下，树的高度为O(n)
 * 如果树是平衡的，高度将是O（logn) 
 */

public class BST<E extends Comparable<E>> extends AbstractTree<E> {
    protected TreeNode<E> root; //根节点
    protected int size = 0;  //节点数目
    
    /** 默认构造方法 */
    public BST() {      
    }
    /** 泛型数组构造二叉搜索树 */
    public BST(E[] objects) {
        for (int i = 0; i < objects.length; i++)
            insert(objects[i]);
    }   

    @Override 
    public boolean search(E e) {
        TreeNode<E> current = root; // 当前指针指向根节点
        while (current != null) {
            if (e.compareTo(current.element) < 0) {
                current = current.left;  // 比当前指针的元素小，则往左
            } else if (e.compareTo(current.element) > 0) {
                current = current.right; // 比当前指针的元素大，则往右
            } else {  // 元素匹配
                return true;  // 找到元素 return true
            }
        }
        return false;
    }

    @Override 
    public boolean insert(E e) {
        if (root == null) {
            root = createNewNode(e);  // 创建一个节点，树为空该节点成为根节点
        } else {
            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; // 元素已经在树中，return false
                }
            }
            // 为元素e创建一个节点
            if (e.compareTo(parent.element) < 0) {
                parent.left = createNewNode(e);
            } else {
                parent.right = createNewNode(e);
            }
        }
        size++;
        return true;
    }
    
    public TreeNode<E> createNewNode(E e) {
        return new TreeNode<>(e);
    }
    
    /** 为了从一棵二叉搜索树中删除一个元素，首先需要定位该元素位置，
     * 然后在删除该元素以及重新连接树之前，考虑两种情况：
     * 1）该节点有左子节点
     * 2）该节点没有左子节点 
     */
    @Override
    public boolean delete(E e) {
        // 如果current为root,那么parent为null
        TreeNode<E> parent = null;  // 指向current节点的父节点
        TreeNode<E> current = root; // 指向二叉搜索树中包含该元素的节点
        
        while (current != null) { // 递归寻找current节点
            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; // 找到包含e的current节点
            }
        }
        
        if (current == null) {
            return false; // 元素不在树内
        }
        
        // 情况1：当前节点没有左子节点
        if (current.left == null) {
            //只需将该节点的父节点和该节点的右子节点相连
            if (parent == null) {
                root = current.right;
            } else {
                if (e.compareTo(parent.element) < 0) {
                    parent.left = current.right;  // e是父节点的左子结点
                } else {
                    parent.right = current.right; // e是父节点的右子结点
                }
            }
        } else { 
            // 情况2：当前节点有左子节点
            TreeNode<E> parentOfRightMost = current;  // rightMost节点的父节点
            TreeNode<E> rightMost = current.left;   // 当前节点的左子树最右端的节点
            
            while (rightMost.right != null) {
                parentOfRightMost = rightMost;
                rightMost = rightMost.right;  // 向右不断递归
            }
            // 用rightMost节点的内容替换current中的内容
            current.element = rightMost.element;
            // rightMost的父节点和rightMost的左子节点相连
            if (parentOfRightMost.right == rightMost) {
                // rightMost是右子节点
                parentOfRightMost.right = rightMost.left;
            } else {
                // rightMost是左子节点
                parentOfRightMost.left = rightMost.left;
            }
        }
        size--;
        return true;
    }

    @Override
    public void inorder() {
        inorder(root);      
    }
    
    protected void inorder(TreeNode<E> root) {
        if (root == null)
            return;
        inorder(root.left);  // 递归遍历左子树
        System.out.print(root.element + " ");  // 递归遍历根节点
        inorder(root.right);  // 递归遍历右子树 1+2
    }

    @Override
    public void postorder() {
        postorder(root);
    }
    protected void postorder(TreeNode<E> root) {
        if (root == null)
            return;
        postorder(root.left);  // 递归遍历左子树
        postorder(root.right);  // 递归遍历右子树
        System.out.println(root.element + " ");  // 递归遍历根节点 12+
    }

    @Override
    public void preorder() {
        preorder(root);
    }
    protected void preorder(TreeNode<E> root) {
        if (root == null)
            return;
        System.out.println(root.element + " ");  // 递归遍历根节点
        preorder(root.left);  // 递归遍历左子树
        preorder(root.right);  // 递归遍历右子树 +12
    }

    @Override
    public void breadthFirstTraversal() {
        if (root == null)
            return;
        Queue<TreeNode<E>> queue = new LinkedList<>();  // Queue Deque Linkedlist
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode<E> current = queue.element();
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
            System.out.println(queue.remove().element + " ");
        }
    }
    
    /**以数组线性表返回节点的路径：
     * 从根节点开始到该元素所在的节点
     * 元素可能不在树中
     */
    public ArrayList<TreeNode<E>> path(E e) {
        ArrayList<TreeNode<E>> list = new ArrayList<>();
        TreeNode<E> current = root;
        while (current != null) {
            list.add(current);
            if (e.compareTo(current.element) < 0) {
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                current = current.right;
            } else {
                break;
            }
        }
        return list;
    }
    
    public int height() {
        return height(root);
    }
    public int height(TreeNode<E> root) {
        if (root == null)
            return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    @Override
    public int getSize() {
        return size;
    }

    public TreeNode<E> getRoot() {
        return root;
    }
    
    public void clear() {
        root = null;
        size = 0;
    }
    /** 测试完全二叉树，完全二叉树的节点格式为 2^depth - 1 */
    public boolean isFullBST() {
        return size == Math.pow(2, height()) - 1 ? true : false;
    }
    /** 找出叶子节点的个数 */
    public int getNumberOfLeaves() {
        return getNumberOfLeaves(root);
    }
    
    protected int getNumberOfLeaves(TreeNode<E> root) {
        if (root ==null)
            return 0;
        // If node has no children return 1 
        // else return the sum of all the leaves
        return root.left == null && root.right == null ? 
                1 : getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right);
    }
    
    public int getNumberOfNonLeaves() {
        return getNumberOfNonLeaves(root);
    } 

    protected int getNumberOfNonLeaves(TreeNode<E> root) {
        if (root == null) return 0;
        
        // If node has children return 0
        // else return 1 plus the sum of the nonleaves
        return (root.left == null && root.right == null) ? 0 : 
            1 + getNumberOfNonLeaves(root.left) + 
            getNumberOfNonLeaves(root.right) ;
    }    
    
    /** Returns true if two trees are equal. 
     Otherwise returns false (recursive) */
    public boolean equals(BST<E> tree) {
        if (tree.size != size) return false;
        return equals(root, tree.root);
    }

    /** Equals helper */
    protected boolean equals(TreeNode<E> root1, TreeNode<E> root2) {
        if (root1 == root2) return true;
        if (root1 == null || root2 == null) return false;
        return root1.element.equals(root2.element) &&
        equals(root1.left, root2.left) &&
        equals(root1.right, root2.right);
    }
    
    @Override /** Override the protected clone method  
    defined in the Object class, and deep copy BST */
    public BST<E> clone() throws CloneNotSupportedException {
        BST<E> cloneBST = new BST<>();
        clone(cloneBST, root);
        return cloneBST;
    }
    
    /** Clone helper */
    protected void clone(BST<E> clone, TreeNode<E> root) {
        if (root == null) return;
        clone.insert(root.element);
        clone(clone, root.left);
        clone(clone, root.right);
    }
    
    @Override
    public Iterator<E> iterator() {
        return new InorderIterator();
    }
    
    private class InorderIterator implements Iterator<E> {
        private ArrayList<E> list = new ArrayList<>();
        private int current = 0;  // 指向线性表中的第一个元素
        
        public InorderIterator() {
            inorder();
        }
        
        private void inorder() {
            inorder(root);
        }
        private void inorder(TreeNode<E> root) {
            if (root == null)
                return;
            inorder(root.left);
            list.add(root.element);
            inorder(root.right);
        }
        
        @Override
        public boolean hasNext() {
            if (current < list.size())  // 检查current是否在list范围内
                return true;
            return false;
        }
        @Override
        public E next() {
            return list.get(current++); // 返回当前元素 然后current+1
        }
        @Override
        public void remove() {
            delete(list.get(current));  // 删除当前元素
            list.clear();  // 清空线性表
            inorder();  // 创建一个新的线性表，每次通过迭代器删除一个元素都要重新构造整个线性表
        }
        
        /*  在使得remove方法不被迭代器支持后，
          * 无须为树中的元素维护一个线性表使得迭代器更加高效。
          * 可以使用栈来存储节点
          * 
         public void remove() {
            throw new UnsupportedOparetionException("removing 
            an element from the iterator is not supported");
         }                
         */
    }
        
    /** Returns an iterator for traversing the elements in preorder */
    public java.util.Iterator<E> preorderIterator() {
        return new PreorderIterator();
    }

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

        public PreorderIterator() {
            preorder(); // Traverse binary tree and store elements in list
        }

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

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

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

            return false;
        }

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

        @Override /** Remove the current element */
        public void remove() {
            delete(list.get(current)); // Delete the current element
            list.clear(); // Clear the list
            preorder(); // Rebuild the list
        }
    }
    
    /** 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;
        }
    }   
}

BST的测试用例

BST测试用例

import java.util.Iterator;

public class TestBST {
    public static void main(String[] args) throws Exception {
        // 广度优先遍历和树的高度
        BST<String> strTree = new BST<>();
        strTree.insert("George");
        strTree.insert("Micheal");
        strTree.insert("Tom");
        strTree.insert("Adam");
        strTree.insert("Jones");
        strTree.insert("Peter");
        strTree.insert("Daniel");
        
        System.out.print("\nBreadth-first: ");
        strTree.breadthFirstTraversal();        
        System.out.print("\nHeight of tree: "); 
        System.out.println(strTree.height());

        
        // 测试完全二叉树
        Integer[] numbers1 = {2, 4, 3, 1, 8, 5, 6, 7};
        Integer[] numbers2 = {4, 2, 1, 3, 8, 5, 9};
        Integer[] numbers3 = {10, 4, 2, 1, 3, 8, 5, 9, 15, 12, 11, 13, 21, 19, 25};
        BST<Integer> intTree1 = new BST<>(numbers1);
        BST<Integer> intTree2 = new BST<>(numbers2);
        BST<Integer> intTree3 = new BST<>(numbers3);
        
        System.out.print("\nIs tree #1 a full binary tree? ");
        System.out.println(intTree1.isFullBST());
        System.out.print("\nIs tree #2 a full binary tree? ");
        System.out.println(intTree2.isFullBST());
        System.out.print("\nIs tree #3 a full binary tree? ");
        System.out.println(intTree3.isFullBST());
        
        
        // 找出叶子节点和非叶子节点
        Integer[] numbers = {60, 55, 45, 47, 59, 100, 76, 107, 101};        
        BST<Integer> intTree = new BST<>(numbers);
        
        System.out.println("Number of leaf nodes: " + 
            intTree.getNumberOfLeaves());       
        System.out.println("Number of nonleaf nodes: " + 
            intTree.getNumberOfNonLeaves());    
        
        
        // 前序遍历
        Integer[] numbers4 = {60, 55, 45, 48, 59, 100, 76, 107, 101};   
        BST<Integer> intTree4 = new BST<>(numbers4);
        
        System.out.print("intTree: ");
        intTree4.preorder();
        

        // 测试clone方法
        BST<Integer> intTreeCopy = intTree.clone();

        // 测试equals方法
        System.out.println("\nIs intTree equal to intTree2? " + 
            intTree.equals(intTree2));
        System.out.println("Is intTree equal to intTreeCopy? " + 
            intTree.equals(intTreeCopy));

        // 前序遍历
        System.out.print("intTreeCopy: ");
        intTreeCopy.preorder();
        System.out.println();       
        
        // 测试前序迭代器
        BST<String> tree0 = new BST<>();
        tree0.insert("George");
        tree0.insert("Michael");
        tree0.insert("Tom");
        tree0.insert("Adam");
        tree0.insert("Jones");
        tree0.insert("Peter");
        tree0.insert("Daniel");

        Iterator<String> iterator = tree0.preorderIterator();
        while (iterator.hasNext())
            System.out.print(iterator.next().toUpperCase() + " ");
        System.out.println();
    }
}

---