一个完整的二进制搜索树，在Java中插入了级别顺序

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

• 二进制搜索树
• 树必须是完整的 ，而不是完美的 （这意味着所有不在最低级别或第二低级别的节点应该有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

• 只需占用数组的中间并将其作为root用户不起作用。 如果你得到一个1到9个元素的数组，你将有4个作为root（java中的int值，double将是4.5），右边有5个元素，左边有4个元素。 这不是一棵完整的树。 甚至不是一棵完美的树。

我的代码只能向左或向右插入，这取决于它是否比根更小，没有水平顺序插入。 Anytype x参数是要插入的值，而BinaryNode t是我们在树中的当前节点（如果我们需要向左或向右插入新值，我们的比较方式）

 private BinaryNode insert( AnyType x, BinaryNode t ) { if( t == null ) return new BinaryNode( x, null, null ); int compareResult = x.compareTo( t.element ); if( compareResult  0 ) t.right = insert( x, t.right ); else ; // Duplicate; do nothing return t; } 

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

我的整个计划

 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> { /** * 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 insert( AnyType x, BinaryNode t ) { if( t == null ) return new BinaryNode( x, null, null ); int compareResult = x.compareTo( t.element ); 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 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 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 { // Constructors BinaryNode( AnyType theElement ) { this( theElement, null, null ); } BinaryNode( AnyType theElement, BinaryNode lt, BinaryNode rt ) { element = theElement; left = lt; right = rt; } AnyType element; // The data in the node BinaryNode left; // Left child BinaryNode right; // Right child } /** The tree root. */ private BinaryNode root; // Test program public static void main( String [ ] args ) { BinarySearchTree t = new BinarySearchTree( ); t.insert(2); t.insert(1); t.insert(3); t.printTree(); } } 

Answer 1

完整的BST部分花了一些时间来理清它实际上是什么。 您的要求还要求订单级别插入。 我不能说这会“插入”，但它会按顺序构建BST。

必须首先对输入列表进行排序。

通过获取根并将其添加到BST，然后将左侧和右侧列表中的内容拆分，将它们添加到列表列表中，然后处理列表列表来完成订单级别的构建。 每轮拆分并添加到列表列表是一个插入级别。

正如所注意到的那样，完整的部分更加困难。 处理它的方法是以不同于普通平衡树的方式计算列表的根。 在正常平衡树中，根索引的长度为/ 2。 要使BST完成，必须偏移根索引，以便通常出现在根的右侧的节点改为显示在根的左侧。 只要计算适用于任何长度列表，就可以正确构建每个拆分子列表。

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

似乎工作。

 public class Node> { protected Node left; protected Node right; protected T data; } public class BTree> { private Node root = new Node<>(); public void addData(T data) { Node 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 intList = IntStream.range(1, i).boxed().collect(Collectors.toList()); BTree bTree = new BTree<>(); List> splitLists = new ArrayList<>(); splitLists.add(intList); while (splitLists.size() > 0 ) { List> tSplitLists = new ArrayList<>(); for ( List 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提到的printNode代码吗？

 1 2 / 1 2 / \ 1 3 3 / \ / \ 2 4 / 1 

等等 …

Answer 2

我认为你应该这样做（代码在C＃中，但不应该很难将其转换为Java）：

 //list should be sorted public void myFunc(List list){ Queue> queue = new Queue>(); queue.Enqueue(list); while(queue.Any()){ List l = queue.Dequeue(); int rindex = findRoot(l); //print r or store it somewhere Console.WriteLine(l.ElementAt(rindex)); List leftlist = l.GetRange(0, rindex); List 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 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; }