接受的答案可以构成一棵完美树(这也是一棵完整树)。虽然它不能在不完美的情况下形成完整的树。不过，这是对我的要求最接近的回答。为了在不完美的情况下进行竞争，您可以移除树最右边的叶子。
<强>1。问题:
试图将一个二叉搜索树变成一个完整的二叉搜索树。我可以找到很多关于Complete Binary Tree 的代码示例，但找不到Complete Binary Search Tree。插入作为二叉搜索树应该工作。但是这种插入方式并不是Complete Tree。如果我加上一堆随机数，它就不是一棵完全树了。如何让代码插入到树中但同时成为一棵完整的二叉搜索树？
如果有代码示例，我将不胜感激。我不觉得理论上很难理解它，但很难用代码实现它。
<强>2。我尝试了什么:
- 以层次顺序的方式添加节点。
- While循环“只要高度不为6就插入，除叶子外所有节点都是全节点”。
- “如果值大于父级且左子级不为空，则只添加到右子级”。
Arrays和LinkedLists添加。
<强>3。我如何插入:
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;
}
AnyType是要插入的值，BinaryNode是 当前节点。
<强>4。该程序能够做什么:
- 插入和删除。
- 查找高度、最小值、最大值或特定节点。
- Preorder、Postorder、Levelorder 和 Inorder 搜索。
- 获取全节点数、所有节点数、叶子数。
<强>5。完整程序:
import java.nio.BufferUnderflowException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class ExerciseBinarySearchTree03<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public ExerciseBinarySearchTree03( )
{
root = null;
}
public void preOrder(){
System.out.println("\nPre Order ");
preOrder(root);
}
public void postOrder(){
System.out.println("\nPost Order ");
postOrder(root);
}
public void inOrder(){
System.out.println("\nIn Order ");
inOrder(root);
}
public void levelOrder(){
System.out.println("\nLevel Order ");
levelOrder(root);
}
public int numberOfNodes(){
return numberOfNodes(root);
}
public int numberOfFullNodes(){
return numberOfFullNodes(root);
}
public int numberOfLeaves(){
return numberOfLeaves(root);
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
if( isEmpty( ) )
throw new BufferUnderflowException( );
return findMin( root ).element;
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( )
{
if( isEmpty( ) )
throw new BufferUnderflowException( );
return findMax( root ).element;
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}
/**
* 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;
}
/* Given a binary tree, return true if the tree is complete
else false */
static boolean isCompleteBT(BinaryNode root)
{
// Base Case: An empty tree is complete Binary Tree
if(root == null)
return true;
// Create an empty queue
Queue<BinaryNode> queue =new LinkedList<>();
// Create a flag variable which will be set true
// when a non full node is seen
boolean flag = false;
// Do level order traversal using queue.
queue.add(root);
while(!queue.isEmpty())
{
BinaryNode temp_node = queue.remove();
/* Check if left child is present*/
if(temp_node.left != null)
{
// If we have seen a non full node, and we see a node
// with non-empty left child, then the given tree is not
// a complete Binary Tree
if(flag == true)
return false;
// Enqueue Left Child
queue.add(temp_node.left);
}
// If this a non-full node, set the flag as true
else
flag = true;
/* Check if right child is present*/
if(temp_node.right != null)
{
// If we have seen a non full node, and we see a node
// with non-empty right child, then the given tree is not
// a complete Binary Tree
if(flag == true)
return false;
// Enqueue Right Child
queue.add(temp_node.right);
}
// If this a non-full node, set the flag as true
else
flag = true;
}
// If we reach here, then the tree is complete Bianry Tree
return true;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return t; // Item not found; do nothing
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = remove( x, t.left );
else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the smallest item.
*/
private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
if( t != null )
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the subtree.
* @return node containing the matched item.
*/
private boolean contains( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return false;
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
return contains( x, t.left );
else if( compareResult > 0 )
return contains( x, t.right );
else
return true; // Match
}
/**
* 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 ) );
}
public int height(){
return height(root);
}
private void preOrder(BinaryNode t )
{
if (t == null) {
return;
}
System.out.println(t.element + " ");
preOrder(t.left);
preOrder(t.right);
}
private void postOrder(BinaryNode t){
if (t == null) {
return;
}
postOrder(t.left);
postOrder(t.right);
System.out.println(t.element + " ");
}
private void inOrder(BinaryNode t)
{
if (t == null) {
return;
}
inOrder(t.left);
System.out.println(t.element + " ");
inOrder(t.right);
}
private void levelOrder(BinaryNode root) {
if (root == null) {
return;
}
Queue<BinaryNode> q = new LinkedList<>();
// Pushing root node into the queue.
q.add(root);
// Executing loop till queue becomes
// empty
while (!q.isEmpty()) {
BinaryNode curr = q.poll();
System.out.print(curr.element + " ");
// Pushing left child current node
if (curr.left != null) {
q.add(curr.left);
}
// Pushing right child current node
if (curr.right != null) {
q.add(curr.right);
}
}
}
//O(n) for the below three methods.
private int numberOfNodes(BinaryNode<AnyType> root){
if ( root == null ) {
return 0;
}
return 1 + numberOfNodes( root.left ) + numberOfNodes( root.right );
}
private int numberOfLeaves(BinaryNode<AnyType> t){
if( t == null ) {
return 0;
}
if( t.left == null && t.right == null ) {
return 1;
}
return numberOfLeaves(t.left) + numberOfLeaves(t.right);
}
private int numberOfFullNodes(BinaryNode<AnyType> root){
if(root==null) {
return 0;
}
if(root.left!=null && root.right!=null) {
return 1 + numberOfFullNodes(root.left) + numberOfFullNodes(root.right);
}
return numberOfFullNodes(root.left) + numberOfFullNodes(root.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;
AnyType[] arr = (AnyType[]) new Integer[7];
// Test program
public static void main( String [ ] args ) {
ExerciseBinarySearchTree03<Integer> bst = new ExerciseBinarySearchTree03<>( );
final int NUMS = 20;
final int GAP = 37;
System.out.println( "Checking... (no more output means success)" );
bst.insert(10);
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) {
if(i != 10) {
bst.insert(i);
}
}
for( int i = 1; i < NUMS; i+= 2 )
bst.remove( i );
if( NUMS <= 40 )
bst.printTree( );
if( bst.findMin( ) != 2 || bst.findMax( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );
for( int i = 2; i < NUMS; i+=2 )
if( !bst.contains( i ) )
System.out.println( "Find error1!" );
for( int i = 1; i < NUMS; i+=2 )
{
if( bst.contains( i ) )
System.out.println( "Find error2!" );
}
bst.inOrder();
}
}
最佳答案
如果您稍加思考，就会发现使用通常的插入函数，元素的顺序决定了树的形状。
- 如果您输入 2,1,3 或 2,3,1 您将得到第 2 级完全二叉树。
- 如果输入 4,2,6,1,3,5,7 将得到第 3 级完全二叉树。
- 如果输入 8,4,12,2,6,11,13,1,3,5,7,9,10,14,15 将得到 4 级完全二叉树。
这里是递归提供元素的伪代码，初始调用必须是
getMedium( v , 0 , v.lenght)
getMedium( array v , start , finish)
if start == finish
insert(v[start])
return
insert( v[(finish - start)/2]
getMedium( array v , start , (finish - start)/2 -1)
getMedium( array v , (finish - start)/2+1 , finish)
关于java - 如何在 Java 中使二叉搜索树成为完整的二叉搜索树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52632698/