问题：
如何在Java中让一个二叉查找树变成一个完整的二叉查找树？
云宾鸿
接受的答案可以做一棵完美的树（这也是一棵完整的树）。虽然它不能在没有完美的情况下做成一棵完整的树。不过，这是我的要求最接近的答案。为了在不完美的情况下进行竞争，你可以去掉树最右边的叶子。
1.问题:
试图将< code >二叉查找树变成< code >完整的二叉查找树。我可以找到很多< code >完全二叉树的代码示例，但是没有< code >完全二叉查找树。这个插件的工作就像二叉查找树应该做的那样。但是这种插入方式并不是一棵完整的树。如果我加上一堆随机数，就不是一棵完整的树了。我怎样才能把代码插入到树中，同时又是一个完整的二叉查找树呢？
我非常喜欢一个代码示例。我发现在理论上很难理解它，但在代码中实现它非常困难。
2.我尝试了什么:
-
< li >以层级顺序方式添加节点。 < li>While循环“插入，只要高度不是6，并且所有节点都是除叶子之外的完整节点”。 < li >“如果值大于父级，并且左子级不为空，则仅添加到右子级”。 要添加的< li>
数组和< code >链接列表。
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;
}
“任意类型”是要插入的值，“二进制节点”是当前节点。
4.该程序能够做什么:
-
null
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个答案
商昆琦
解决方案是使用递归，我做了一个新的帖子，我得到了一个答案：
https://stackoverflow.com/a/52749727/9899617
糜征
如果你稍微思考一下，你会看到使用通常的插入函数，元素的顺序决定了树的形状。
-
< li >如果您输入2，1，3或2，3，1，您将得到2级完整二叉树。 < li >如果您输入4，2，6，1，3，5，7，您将得到3级完整二叉树。 < li >如果您输入8，4，12，2，6，11，13，1，3，5，7，9，10，14，15，您将得到4级完整二叉树。
这里是递归提供元素的伪代码，初始调用必须是
getMedium( v，0，v . length)
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)
类似资料：
-
我需要制作一。如果我有一个看起来像这样的方法： 例如，我用数字9作为< code>i的值，我该怎么做才能找到一个根来生成一棵完整的树呢？ 如果我使用9作为值，则数字将为。对于完整的二叉搜索树，根必须为 6，如下所示： 我怎样才能制作一个知道这一点的方法？它应该适用于任何类型的数字，所以如果我想使用数字14，它应该能够。 到目前为止，我唯一拥有的代码是一个插入方法，它只是检查要插入的数字是大于（向右
-
我正在努力实现二叉搜索树。完成实现所需的功能之一是重新平衡功能。 根据规范，该功能的工作方式如下: rebalance（） 方法应创建一个平衡树，从而将偏度降低为零。平衡树是指在整个树中，左子树和右子树的大小相差不超过1（即，每个子树也是平衡的）。 为了平衡树，rebalance（） 方法应反复将根值移动到较小的子树，并将最小/最大值从较大的子树移动到根，直到树平衡。然后，它应该以递归方式平衡两个
-
主要内容：什么是二叉排序树？,使用二叉排序树查找关键字,二叉排序树中插入关键字,二叉排序树中删除关键字,总结前几节介绍的都是有关静态 查找表的相关知识，从本节开始介绍另外一种查找表—— 动态查找表。 动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。 动态查找表的表示方式有多种，本节介绍一种使用树结构表示动态查找表的实现方法—— 二叉排序树（又称为 “二叉查找树”）。 什么是二叉排序树？ 二叉排序树要么是空 二叉树，要么具有如下特点：
-
在包含 main 函数的类中，定义一个函数调用 createTree（String strKey）。给出一个整数字符串（用空格字符分隔），此函数将创建一个 BST 树，其中整数键跟在输入字符串之后。示例：给定一个字符串 s = “30 20 40”。调用函数 createTree（s） 来创建二叉搜索树：root = 30，root.left = 20，root.right = 40。以下是我的代
-
我试图制作一个二叉搜索树（非递归），然后稍后访问并执行预序遍历，但是当我打印根目录时，我只得到 1 个元素。我认为所有的插入都有效，但是 root 只是第一次插入，它的左右不引用任何东西，我认为这就是为什么我只得到 1 个元素。如何将根引用到节点树的顶部？这是节点类顺便说一句
-
我们已经看到了两种不同的方法来获取集合中的键值对。回想一下，这些集合实现了 map 抽象数据类型。我们讨论的 map ADT 的两个实现是在列表和哈希表上的二分搜索。在本节中，我们将研究二叉查找树作为从键映射到值的另一种方法。 在这种情况下，我们对树中项的确切位置不感兴趣，但我们有兴趣使用二叉树结构来提供高效的搜索。