java - 如何在 Java 中使二叉搜索树成为完整的二叉搜索树？

Question

接受的答案可以构成一棵完美树(这也是一棵完整树)。虽然它不能在不完美的情况下形成完整的树。不过，这是对我的要求最接近的回答。为了在不完美的情况下进行竞争，您可以移除树最右边的叶子。

<强>1。问题:

试图将一个二叉搜索树变成一个完整的二叉搜索树。我可以找到很多关于Complete Binary Tree 的代码示例，但找不到Complete Binary Search Tree。插入作为二叉搜索树应该工作。但是这种插入方式并不是Complete Tree。如果我加上一堆随机数，它就不是一棵完全树了。如何让代码插入到树中但同时成为一棵完整的二叉搜索树？

如果有代码示例，我将不胜感激。我不觉得理论上很难理解它，但很难用代码实现它。

<强>2。我尝试了什么:

• 以层次顺序的方式添加节点。
• While循环“只要高度不为6就插入，除叶子外所有节点都是全节点”。
• “如果值大于父级且左子级不为空，则只添加到右子级”。
• Arrays 和 LinkedLists 添加。

<强>3。我如何插入:

private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
    if( t == null )
        return new BinaryNode<>( x, null, null);

    int compareResult = x.compareTo( t.element );

        if (compareResult < 0)
            t.left = insert(x, t.left);
        else if (compareResult > 0)
            t.right = insert(x, t.right);
        else
            ;  // Duplicate; do nothing

    return t;
}

• AnyType是要插入的值，BinaryNode是当前节点。

<强>4。该程序能够做什么:

• 插入和删除。
• 查找高度、最小值、最大值或特定节点。
• Preorder、Postorder、Levelorder 和 Inorder 搜索。
• 获取全节点数、所有节点数、叶子数。

<强>5。完整程序:

import java.nio.BufferUnderflowException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

/**
 * Implements an unbalanced binary search tree.
 * Note that all "matching" is based on the compareTo method.
 * @author Mark Allen Weiss
 */
public class ExerciseBinarySearchTree03<AnyType extends Comparable<? super AnyType>>
{
    /**
     * Construct the tree.
     */
    public ExerciseBinarySearchTree03( )
    {
        root = null;
    }

    public void preOrder(){
        System.out.println("\nPre Order ");
        preOrder(root);
    }
    public void postOrder(){

        System.out.println("\nPost Order ");
        postOrder(root);
    }
    public void inOrder(){

        System.out.println("\nIn Order ");
        inOrder(root);
    }
    public void levelOrder(){
        System.out.println("\nLevel Order ");
        levelOrder(root);
    }


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

    public int numberOfFullNodes(){
        return numberOfFullNodes(root);
    }
    public int numberOfLeaves(){
        return numberOfLeaves(root);
    }

    /**
     * Insert into the tree; duplicates are ignored.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {
        root = insert( x, root );
    }

    /**
     * Remove from the tree. Nothing is done if x is not found.
     * @param x the item to remove.
     */
    public void remove( AnyType x )
    {
        root = remove( x, root );
    }

    /**
     * Find the smallest item in the tree.
     * @return smallest item or null if empty.
     */
    public AnyType findMin( )
    {
        if( isEmpty( ) )
            throw new BufferUnderflowException( );
        return findMin( root ).element;
    }

    /**
     * Find the largest item in the tree.
     * @return the largest item of null if empty.
     */
    public AnyType findMax( )
    {
        if( isEmpty( ) )
            throw new BufferUnderflowException( );
        return findMax( root ).element;
    }

    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return true if not found.
     */
    public boolean contains( AnyType x )
    {
        return contains( x, root );
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty( )
    {
        root = null;
    }

    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( )
    {
        return root == null;
    }

    /**
     * Print the tree contents in sorted order.
     */
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }

    /**
     * Internal method to insert into a subtree.
     * @param x the item to insert.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
    {
        if( t == null )
            return new BinaryNode<>( x, null, null);

        int compareResult = x.compareTo( t.element );

            if (compareResult < 0)
                t.left = insert(x, t.left);
            else if (compareResult > 0)
                t.right = insert(x, t.right);
            else
                ;  // Duplicate; do nothing

        return t;
    }

    /* Given a binary tree, return true if the tree is complete
       else false */
    static boolean isCompleteBT(BinaryNode root)
    {
        // Base Case: An empty tree is complete Binary Tree
        if(root == null)
            return true;

        // Create an empty queue
        Queue<BinaryNode> queue =new LinkedList<>();

        // Create a flag variable which will be set true
        // when a non full node is seen
        boolean flag = false;

        // Do level order traversal using queue.
        queue.add(root);
        while(!queue.isEmpty())
        {
            BinaryNode temp_node = queue.remove();

            /* Check if left child is present*/
            if(temp_node.left != null)
            {
                // If we have seen a non full node, and we see a node
                // with non-empty left child, then the given tree is not
                // a complete Binary Tree
                if(flag == true)
                    return false;

                // Enqueue Left Child
                queue.add(temp_node.left);
            }
            // If this a non-full node, set the flag as true
            else
                flag = true;

            /* Check if right child is present*/
            if(temp_node.right != null)
            {
                // If we have seen a non full node, and we see a node
                // with non-empty right child, then the given tree is not
                // a complete Binary Tree
                if(flag == true)
                    return false;

                // Enqueue Right Child
                queue.add(temp_node.right);

            }
            // If this a non-full node, set the flag as true
            else
                flag = true;
        }
        // If we reach here, then the tree is complete Bianry Tree
        return true;
    }












    /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the subtree.
     * @return the new root of the subtree.
     */
    private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
    {
        if( t == null )
            return t;   // Item not found; do nothing

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 )
            t.left = remove( x, t.left );
        else if( compareResult > 0 )
            t.right = remove( x, t.right );
        else if( t.left != null && t.right != null ) // Two children
        {
            t.element = findMin( t.right ).element;
            t.right = remove( t.element, t.right );
        }
        else
            t = ( t.left != null ) ? t.left : t.right;
        return t;
    }

    /**
     * Internal method to find the smallest item in a subtree.
     * @param t the node that roots the subtree.
     * @return node containing the smallest item.
     */
    private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
    {
        if( t == null )
            return null;
        else if( t.left == null )
            return t;
        return findMin( t.left );
    }

    /**
     * Internal method to find the largest item in a subtree.
     * @param t the node that roots the subtree.
     * @return node containing the largest item.
     */
    private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
    {
        if( t != null )
            while( t.right != null )
                t = t.right;

        return t;
    }

    /**
     * Internal method to find an item in a subtree.
     * @param x is item to search for.
     * @param t the node that roots the subtree.
     * @return node containing the matched item.
     */
    private boolean contains( AnyType x, BinaryNode<AnyType> t )
    {
        if( t == null )
            return false;

        int compareResult = x.compareTo( t.element );

        if( compareResult < 0 )
            return contains( x, t.left );
        else if( compareResult > 0 )
            return contains( x, t.right );
        else
            return true;    // Match
    }

    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the subtree.
     */
    private void printTree( BinaryNode<AnyType> t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }

    /**
     * Internal method to compute height of a subtree.
     * @param t the node that roots the subtree.
     */
    private int height( BinaryNode<AnyType> t )
    {
        if( t == null )
            return -1;
        else
            return 1 + Math.max( height( t.left ), height( t.right ) );
    }


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

    private void preOrder(BinaryNode t )
    {
        if (t == null) {
            return;
        }
            System.out.println(t.element + " ");
            preOrder(t.left);
            preOrder(t.right);

    }

    private void postOrder(BinaryNode t){
        if (t == null) {
            return;
        }
            postOrder(t.left);
            postOrder(t.right);
            System.out.println(t.element + " ");

    }

    private void inOrder(BinaryNode t)
    {
        if (t == null) {
            return;
        }
            inOrder(t.left);
            System.out.println(t.element + " ");
            inOrder(t.right);
    }

    private void levelOrder(BinaryNode root) {
        if (root == null) {
            return;
        }

        Queue<BinaryNode> q = new LinkedList<>();

        // Pushing root node into the queue.
        q.add(root);

        // Executing loop till queue becomes
        // empty
        while (!q.isEmpty()) {

            BinaryNode curr = q.poll();
            System.out.print(curr.element + " ");

            // Pushing left child current node
                if (curr.left != null) {
                    q.add(curr.left);
                }

                // Pushing right child current node
                if (curr.right != null) {
                    q.add(curr.right);
                }
            }
    }

    //O(n) for the below three methods.
    private int numberOfNodes(BinaryNode<AnyType> root){
        if ( root == null ) {
            return 0;
        }
        return 1 + numberOfNodes( root.left ) + numberOfNodes( root.right );
    }


    private int numberOfLeaves(BinaryNode<AnyType> t){
        if( t == null ) {
            return 0;
        }
        if( t.left == null && t.right == null ) {

            return 1;
        }
            return numberOfLeaves(t.left) + numberOfLeaves(t.right);
    }

    private int numberOfFullNodes(BinaryNode<AnyType> root){
        if(root==null) {
            return 0;
        }
        if(root.left!=null && root.right!=null) {
            return 1 + numberOfFullNodes(root.left) + numberOfFullNodes(root.right);
        }
        return numberOfFullNodes(root.left) + numberOfFullNodes(root.right);
    }


    // Basic node stored in unbalanced binary search trees
    private static class BinaryNode<AnyType>
    {
            // Constructors
        BinaryNode( AnyType theElement )
        {
            this( theElement, null, null );
        }

        BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
        {
            element  = theElement;
            left     = lt;
            right    = rt;
        }

        AnyType element;            // The data in the node
        BinaryNode<AnyType> left;   // Left child
        BinaryNode<AnyType> right;  // Right child
    }

      /** The tree root. */
    private BinaryNode<AnyType> root;


    AnyType[] arr = (AnyType[]) new Integer[7];


    // Test program
    public static void main( String [ ] args ) {
        ExerciseBinarySearchTree03<Integer> bst = new ExerciseBinarySearchTree03<>( );
        final int NUMS = 20;
        final int GAP  =   37;

        System.out.println( "Checking... (no more output means success)" );

        bst.insert(10);

        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) {
            if(i != 10) {
                bst.insert(i);
            }
        }

        for( int i = 1; i < NUMS; i+= 2 )
            bst.remove( i );

        if( NUMS <= 40 )
            bst.printTree( );
        if( bst.findMin( ) != 2 || bst.findMax( ) != NUMS - 2 )
            System.out.println( "FindMin or FindMax error!" );

        for( int i = 2; i < NUMS; i+=2 )
            if( !bst.contains( i ) )
                System.out.println( "Find error1!" );

        for( int i = 1; i < NUMS; i+=2 )
        {
            if( bst.contains( i ) )
                System.out.println( "Find error2!" );
        }

        bst.inOrder();
    }


}

Answer 1

如果您稍加思考，就会发现使用通常的插入函数，元素的顺序决定了树的形状。

• 如果您输入 2,1,3 或 2,3,1 您将得到第 2 级完全二叉树。
• 如果输入 4,2,6,1,3,5,7 将得到第 3 级完全二叉树。
• 如果输入 8,4,12,2,6,11,13,1,3,5,7,9,10,14,15 将得到 4 级完全二叉树。

这里是递归提供元素的伪代码，初始调用必须是

getMedium( v , 0 , v.lenght)

getMedium( array v , start , finish)

     if start == finish
         insert(v[start])
         return 

     insert( v[(finish - start)/2]
     getMedium( array v , start , (finish - start)/2 -1)
     getMedium( array v , (finish - start)/2+1 , finish)