一种用Java实现的具有层序插入的完全二叉树
一种用Java实现的具有层序插入的完全二叉树
提问于 2018-10-09 23:49:51
我们有一个任务，我们需要编写代码：
- A Binary Search Tree
- The Tree to be complete，not perfect (这意味着所有不在最低级别或次最低级别的节点都应该有两个子节点，而最低级别的节点应该尽可能地靠左)
- 如果我有一个元素为
{0, 1, 2, 3, 4, 5, 6, 7}的数组，root应该是4，2, 1, 3, 0在左侧，6, 5, 7在右侧，我们需要在级别order - So中插入树。插入的级别顺序是：
4, 2, 6, 1, 3, 5, 7, 0 - Just取数组的中间位置，并将其作为根，
- 不起作用。如果您得到一个由1到9个元素组成的数组，则根元素为4(在java中，int值为双精度为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();
}
}回答 2
Stack Overflow用户
回答已采纳
发布于 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如…等
Stack Overflow用户
发布于 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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52724898
复制相关文章
相似问题
腾讯云开发者
