Java中带有级别顺序的完整二进制搜索树

Question

我们得到了一个需要编写代码的作业：

• 二叉搜索树
• 树必须是完整的，而不是完美的（这意味着所有不在最低级别或第二低级别的节点都应有2个子节点，而最低级别的节点应尽可能远）
• 我们需要按级别顺序插入树中

• 因此，如果我有一个包含元素{0, 1, 2, 3, 4, 5, 6, 7}的数组，root应该是4，2, 1, 3, 0在左侧和6, 5, 7右侧。

• 级别订单插入为： 4, 2, 6, 1, 3, 5, 7, 0

• 仅将Array的中间部分放在根目录是行不通的。如果有1到9个元素的数组，则将有4个作为根（java中的int值，double为4.5），右侧将有5个元素，左侧有4个元素。这不是一棵完整的树。甚至不是完美的树。

我的代码只能向左或向右插入，具体取决于它是否
大于或小于根，而不插入级别顺序。该Anytype x
参数是要插入的价值，同时BinaryNode t为当前
节点，我们在树（这就是我们的比较，如果我们需要新的插入
值向左或向右）

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

如何按级别顺序插入并仍然维护二进制搜索树？
我应该使用某种形式的递归吗？

我的整个程序

import java.nio.BufferUnderflowException;
import java.util.*;

import static java.lang.Math.pow;

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

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

    /**
     * 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;
    }

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

    // 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;

        // Test program
    public static void main( String [ ] args )
    {
        BinarySearchTree<Integer> t = new BinarySearchTree<>( );

        t.insert(2);
        t.insert(1);
        t.insert(3);
        t.printTree();
    }
}

Answer 1

完整的BST部分花了一些时间来弄清实际内容。
您的要求还要求插入订单级别。我不能说这确实可以
“插入”，但是它可以按顺序构建BST。

输入列表必须首先排序。

通过建立根目录并将其添加
到BST，然后将左侧内容拆分为左右列表，将
它们添加到列表列表中，然后处理列表列表，可以完成顺序构建。每轮
拆分和添加到列表列表都是一个插入级别。

如所注意到的，完整部分更加困难。处理该问题的方法是
与普通的平衡树不同地计算列表的根。在
正常的平衡树中，根索引为length / 2。为了使BST完整
，必须偏移根索引，以便通常会出现在
根右侧的节点出现在根左侧。由于
只要计算适用于任何长度的名单，然后每个分割子列表中
正确建立。

据我所知，通过增加
长度上每个附加元素的偏移量直到达到
水平宽度的1/2来计算偏移量。因此，高度为4的BST在最低级别具有8个元素。的列表
大小8，9，10，… 15创建BST用的4高度对于这些列表的根
索引的列表然后4，5，6，7，7,7，7,7。

似乎可以工作。

public class Node<T extends Comparable<T>> {
    protected Node<T> left;
    protected Node<T> right;
    protected T data;   
}

public class BTree<T extends Comparable<T>> {
    private Node<T> root = new Node<>();
    public void addData(T data) {
        Node<T> parent = root;
        while (parent.data != null ) {
            if ( data.compareTo( parent.data ) > 0 ) {
                if ( parent.right == null ) 
                    parent.right = new Node<>();
                parent = parent.right;
            } else {
                if ( parent.left == null ) 
                    parent.left = new Node<>();
                parent = parent.left;
            }
        }
        parent.data = data;
    }
}

private void run() {
    for ( int i = 2; i < 65; ++i ) {
        List<Integer> intList = IntStream.range(1, i).boxed().collect(Collectors.toList());
        BTree<Integer> bTree = new BTree<>();
        List<List<Integer>> splitLists = new ArrayList<>();
        splitLists.add(intList);
        while (splitLists.size() > 0 ) {
            List<List<Integer>> tSplitLists = new ArrayList<>();
            for ( List<Integer> tIntList: splitLists) {
                int length = tIntList.size();
                // compute starting point
                int mid = calcMid(length);      // length/2 ; //+ calcOffset(length);
                bTree.addData(tIntList.get(mid));
                if ( mid - 0 > 0)
                    tSplitLists.add(tIntList.subList(0, mid));
                if ( length - (mid+1) > 0)
                    tSplitLists.add(tIntList.subList(mid+1, length));
            }
            splitLists = tSplitLists;
        }
        bTree.printNode();
    }
}
private int calcMid(int length) {
    if ( length <= 4 )
        return length / 2;
    int levelSize = 1;
    int total = 1;
    while ( total < length ) {
        levelSize *= 2;
        total += levelSize;
    }
    int excess = length - (total - levelSize);
    int minMid = (total - levelSize + 1) / 2;
    if ( excess <= levelSize / 2 ) {
        return minMid + (excess - 1); 
    } else {
        int midExcess = levelSize/2; 
        return minMid + (midExcess - 1);
    }

}

请参阅如何打印二叉树图？有关打印二叉树的代码。

PS>我相信您可以通过清除和复制列表而不是每次都创建新列表来使它更好。

编辑：你去获取printNode上面引用的代码吗？

1

 2   
/   
1

 2   
/ \ 
1 3

   3       
  / \   
 /   \  
 2   4   
/       
1

等等 …