Java中带有级别顺序的完整二进制搜索树 [英] A complete Binary Search Tree with level order insert in Java
问题描述
我们得到了一个需要编写代码的作业:
We got an assignment where we need to code:
- 二进制搜索树
- 树必须是完整，而不是完美(这意味着所有不在最低级别或第二最低级别的节点都应有两个孩子，而最低级别的节点应尽可能远)
- 我们需要按级别顺序 插入树中
-
因此，如果我有一个元素为
{0, 1, 2, 3, 4, 5, 6, 7}的数组，则root应该为4，左侧为2, 1, 3, 0，右侧为6, 5, 7.
- A Binary Search Tree
- The Tree has to be complete, not perfect (which means all nodes which are not on the lowest level or second lowest level should have 2 children, while the nodes on the lowest level should be as far left as possible)
- We need to insert to the tree in level order
So if I have an Array with elements
{0, 1, 2, 3, 4, 5, 6, 7}therootshould be4, with2, 1, 3, 0on the left side, and6, 5, 7on the right side.
级别顺序插入为:4, 2, 6, 1, 3, 5, 7, 0
仅将Array的中间部分放在根目录下是行不通的.如果有1到9个元素的数组，则将有4个作为根(java中的int值，double为4.5)，并且在右侧将有5个元素，在左侧将有4个元素.这不是一棵完整的树.甚至都不是一棵完美的树.
Just taking the middle of the Array and put it as root doesn't work. If you got an array of 1 to 9 elements, you would have 4 as root (int value in java, double would be 4.5), and you would have 5 elements on the right side, and 4 on the left side. This is not a complete tree. Not even a perfect tree.
我的代码只能向左或向右插入，这取决于它是否大于根，或者不插入级别顺序. Anytype x参数是要插入的值，而BinaryNode t是我们在树中的当前节点(如果需要在左侧或右侧插入新值，这就是我们进行比较的方式)
My code is only able to insert at either left or right depending if it's greater og smaller than the root, no level order insertion. The Anytype x parameter is the value to be inserted, while the BinaryNode t is the current node we are at in the tree (that's how we compare if we need to insert the new value to the left or right)
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;
}
如何按级别顺序插入并仍然维护二进制搜索树?我应该使用某种形式的递归吗?
How can I insert in level order and still maintain a binary search tree? Should I use some form of recursion?
我的整个程序
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();
}
}
推荐答案
完整的BST部分花了一些时间来弄清实际上是什么.您的要求还要求插入订单级别.我不能说这确实可以插入"，但是它可以按顺序构建BST.
The complete BST part took a bit of time to sort out what that actually is. Your requirement also calls for order level insert. I can't say this does "inserts", but it builds the BST in order level.
必须首先对输入列表进行排序.
The input List must be sorted first.
按顺序构建是通过以下步骤完成的:取根并将其添加到BST中，然后将剩余的内容分为左右列表，将它们添加到列表列表中，然后处理列表列表.每轮拆分和添加到列表列表都是一个插入级别.
The building in order level is accomplished by taking the root and adding it to the BST, then splitting what is left into left and right lists, adding them into a list of lists, then processing the list of lists. Each round of splitting and adding to a list of lists is a level of insertion.
正如所注意到的，整个部分更加困难.处理该问题的方法是与普通的平衡树不同地计算列表的根.在正常的平衡树中，根索引为length/2.为了使BST完整，必须偏移根索引，以便通常会出现在根右侧的节点出现在根左侧.只要计算适用于任何长度列表，那么每个拆分子列表都将正确构建.
The complete part is more difficult, as was noticed. The way to handle that is to compute the root for the list differently than a normal balanced tree. In a normal balanced tree the root index is at length/2. For the BST to be complete the root index has to be offset so that nodes that would normally appear on the right side of the root instead appear on the left side of the root. As long as the computation works for any length list then each split sublist is built properly.
据我所知，通过增加长度上每个附加元素的偏移量直到达到水平宽度的1/2来计算偏移量.因此，高度为4的BST在最低级别具有8个元素.大小为8、9、10，…15的列表创建高度为4的BST.对于那些列表，列表的根索引为4、5、6、7、7、7、7、7.
From what I can tell computing the offset done by incrementing the offset for each additional element in length until you get to 1/2 of the width of a level. So, a BST with height of 4 has 8 elements in the lowest level. Lists of size 8, 9, 10, … 15 create BST with height of 4. For those lists the root index into the list is then 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);
}
}
请参见如何打印二叉树图?打印二叉树的代码.
See How to print binary tree diagram? for code on printing a binary tree.
PS>我敢肯定，通过清除和复制列表而不是每次都创建新列表，可以使它变得更好.
PS> I'm sure you can make it a bit better by clearing and copying Lists instead of making new ones each time.
您是否去过上面提到的printNode代码?
Did you go and get the printNode code referenced above?
1
2
/
1
2
/ \
1 3
3
/ \
/ \
2 4
/
1
依此类推...
这篇关于Java中带有级别顺序的完整二进制搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
