Принятый ответ может составить Совершенное дерево (которое также является Полным деревом).Хотя он не может создать Полное дерево, не будучи Совершенным.Это был самый близкий ответ на мою просьбу.Чтобы составить конкуренцию без совершенства, вы можете удалить самые правые листья дерева.
1.Проблема:
Попытка превратить Binary Search Tree в Complete Binary Search Tree.Я могу найти много примеров кода для Complete Binary Tree, но не Complete Binary Search Tree.Вставка работает так, как должно работать бинарное дерево поиска.Но этот способ вставки не является Полным Деревом.Если я добавлю несколько случайных чисел, это не будет полное дерево.Как я могу сделать вставку кода в дерево , но в то же время быть полным двоичным деревом поиска?
Я был бы очень признателен за пример кода.Мне вообще не трудно понять это теоретически, но очень трудно реализовать это в коде.
2.Что я пробовал:
- Чтобы добавить узлы в порядке порядка уровней.
- Хотя цикл "Вставить, если высота не равна 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.Что может сделать программа:
- Вставить и удалить.
- Найти высоту, минимум, максимум или определенный узел.
- Предварительный заказ, Postorder,Поиск по уровням и по порядку.
- Получите количество полных узлов, количество всех узлов и количество листьев.
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();
}
}