1

我正在实现对二叉树进行多次插入的功能。对我首先得到的元素向量进行排序，然后在循环中为单个元素调用普通树插入函数是正确的？还是有更有效的策略？谢谢！

@Override
public void insert(Vector<V> vec) {
    insert(root,vec);
}

private void insert(Node<V> node, Vector<V> vec){
    Collections.sort(vec);
    for(int i = 0; i < vec.size(); i++){
        insert(root, vec.get(i));
    }       
}

@Override
public void insert(V obj) {
    root = insert(root, obj);
}

private Node<V> insert(Node<V> node,V data){
    if(node == null){
        return node = new Node<V>(data,null,null);          
    }
    else{
        if(data.compareTo(node.data) < 0){
            node.left = insert(node.left,data);         
        }
        else{
            node.right = insert(node.right,data);                            
        }
        return node;
    }
}
4

2 回答 2

0

您必须在插入后平衡树。

这是我的实现：

public class Tree< T extends Comparable< T >>
{
   public static< T extends Comparable< T >> int getDepth( Tree< T > node )
   {
      return
         ( node == null )
            ? 0
            : ( 1 + Math.max( getDepth( node._left  ),
                              getDepth( node._right )));
   }// int getDepth()



   public Tree( T t )
   {
      _data  = t;
      _left  = null;
      _right = null;
      _count = 1;
   }// Tree( T t )



   public Tree< T > add( Tree< T > child )
   {
      Tree< T > root = this;
      int cmp = _data.compareTo( child._data );
      if( cmp > 0 )
      {
         if( _left == null )
         {
            _left = child;
         }
         else
         {
            _left = _left.add( child );
         }// if
         _count += child._count;
         if( _left._count > (( _right == null ) ? 0 : _right._count ) + 1 )
         {
            root = _left;
            _count -= root._count;
            _left = null;
            if( root._right == null )
            {
                root._right = this;
            }
            else
            {
               root._right = root._right.add( this );
            }// if
            root.updateCount();
         }// if
      }
      else if( cmp < 0 )
      {
         if( _right == null )
         {
            _right = child;
         }
         else
         {
            _right = _right.add( child );
         }// if
         _count += child._count;
         if( _right._count > (( _left == null ) ? 0 : _left._count ) + 1 )
         {
            root = _right;
            _count -= root._count;
            _right = null;
            if( root._left == null )
            {
               root._left  = this;
            }
            else
            {
               root._left = root._left.add( this );
            }// if
            root.updateCount();
         }// if
      }// if
      return root;
   }// Tree< T > add( Tree< T > child )



   public int getCount()
   {
      return _count;
   }// int getCount()



   @Override
   public String toString()
   {
      return _data.toString();
   }// String toString()



   private void updateCount()
   {
      _count =
         1 +
         (( _left  == null ) ? 0 : _left._count  ) +
         (( _right == null ) ? 0 : _right._count );
   }// void updateCount()



   public final T         _data;
   public /* */ Tree< T > _left;
   public /* */ Tree< T > _right;
   public /* */ int       _count;

}// class Tree
于 2012-11-06T13:35:38.233 回答
0

考虑

  • 在树中插入一个列表：当排序时，它会创建一个只有左或右节点被填充的列表。
  • 插入可以重新平衡树，就像在二叉 AVL 树中一样。缺点是树枝上有洞。K(F(A, -), P(-, T(R -)))：元素 6，深度 4。最佳深度为 3。

对于将列表变成深度最小的二叉树的情况：对列表进行排序，并在列表上根据索引创建树。

伪代码中的树构造：

convertListToTree(list)
    list.sort();
    return subtreeOf(list, 0, list.size())

subtreeOf(list, from, to) {
    if (to - from <= 0)
        return null;
    int mid = (from + to) / 2;
    return new Node(list.get(mid),
                    subTreeOf(list, from, mid),
                    subTreeOf(list, mid + 1, to));
}
于 2018-02-02T11:32:13.097 回答