我们有一个任务,我们需要编写代码:
{0, 1, 2, 3, 4, 5, 6, 7}
的数组,root
应该是4
,2, 1, 3, 0
在左侧,6, 5, 7
在右侧,我们需要在级别order4, 2, 6, 1, 3, 5, 7, 0
我的代码只能在左侧或右侧插入,这取决于它是否大于或小于根,没有级别顺序插入。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();
}
}
发布于 2018-10-11 06:38:44
完整的BST部分花了一些时间来理清它到底是什么。您的需求还需要订单级插入。我不能说这是“插入”,但它在订单级别构建了BST。
必须首先对输入列表进行排序。
顺序级别的构建是通过以下方式完成的:取根并将其添加到BST中,然后将剩下的内容拆分为左和右列表,将它们添加到列表列表中,然后处理列表列表。拆分和添加到列表列表的每一轮都是一个插入级别。
正如我们已经注意到的,完整的部分更难。处理这种情况的方法是以不同于普通平衡树的方式计算列表的根。在正常的平衡树中,根索引的长度为/2。为了使BST完整,必须对根索引进行偏移,以便通常出现在根的右侧的节点出现在根的左侧。只要计算对任何长度的列表都有效,那么每个拆分子列表都是正确构建的。
据我所知,计算偏移量是通过增加长度上每个额外元素的偏移量,直到你得到一个标高宽度的1/2。因此,高度为4的BST在最低层有8个元素。大小为8、9、10、…的列表15创建高度为4的BST。对于这些列表,列表中的根索引是4,5,6,7,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);
}
}
有关打印二叉树的代码,请参见How to print binary tree diagram?。
PS>我相信你可以通过清理和复制列表来使它变得更好,而不是每次都创建新的列表。
编辑:你有没有拿到上面提到的printNode
代码?
1
2
/
1
2
/ \
1 3
3
/ \
/ \
2 4
/
1
如…等
发布于 2018-10-10 08:59:57
我认为你应该这样做(代码是用C#写的,但是把它转换成Java应该不是很难):
//list should be sorted
public void myFunc(List<int> list){
Queue<List<int>> queue = new Queue<List<int>>();
queue.Enqueue(list);
while(queue.Any()){
List<int> l = queue.Dequeue();
int rindex = findRoot(l);
//print r or store it somewhere
Console.WriteLine(l.ElementAt(rindex));
List<int> leftlist = l.GetRange(0, rindex);
List<int> rightlist = l.GetRange(rindex + 1, l.Count-rindex-1);
//leftlist = list l from index 0 to r-1; rightlist = list l from index r+1 to end.
if (leftlist.Any())
{
queue.Enqueue(leftlist);
}
if (rightlist.Any())
{
queue.Enqueue(rightlist);
}
}
}
*编辑:*
要在每次具有大小为n的列表时查找根,请执行以下操作:
public int findRoot(List<int> list)
{
int n = list.Count;
double h = Math.Ceiling(Math.Log(n + 1, 2)) - 1;
double totNodesInCompleteBinaryTreeOfHeighthMinusOne = Math.Pow(2, h) - 1;
double nodesOnLastLevel = n - totNodesInCompleteBinaryTreeOfHeighthMinusOne;
double nodesOnLastLevelInRightSubtree = 0;
if (nodesOnLastLevel > Math.Pow(2, h - 1))
{
nodesOnLastLevelInRightSubtree = nodesOnLastLevel - Math.Pow(2, h - 1);
}
int rindex = (int)(n - nodesOnLastLevelInRightSubtree - 1 - ((totNodesInCompleteBinaryTreeOfHeighthMinusOne - 1) / 2));
return rindex;
}
https://stackoverflow.com/questions/52724898
复制相似问题