2

大家好，我正在使用二叉搜索树进行课程项目。我在尝试查找二叉搜索树的第 n 个节点时遇到了麻烦。我理解使用顺序遍历和使用计数器的概念，但我无法将其放入代码中。如果有人可以提供帮助，将不胜感激。抱歉，代码太长了。有问题的方法就是nthElement(int n, BinaryNode<AnyType> t)方法。我不知道如何增加计数器。

package proj2;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// boolean contains( x )  --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate

/**
 * 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<? super AnyType>>
{
/** The tree root. */
private BinaryNode<AnyType> root;

/** The tree size. */
private int treeSize;

/**
 * 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 );
}

/**
 * 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 UnderflowException( );
    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 UnderflowException( );
    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 );
}

/**
 * Count the number of nodes in the tree.
 * @return the tree size.
 */
public int treeSize(){

    treeSize = treeSize(root);
    return treeSize;

}

/**
 * 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 );
}

public BinaryNode<AnyType> nthElement(int n){

    return nthElement(n, 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<AnyType>( 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;
}

/**
 * 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 for traversing the tree in-order.
 * @param t the node that roots the subtree.
 * @return 
 */
  private void nthElement(int n, BinaryNode<AnyType> t){

    int i = t.treeSize;
    if(t.left.treeSize == n){
        System.out.println(t.element);
    }else if(t.left.treeSize > n){
        nthElement(n, t.left);
    }else if(t.left.treeSize < n){
        int k = i - t.left.treeSize;
        nthElement(k, t.right);
    }
}

/** 
 * Internal method for finding tree size.
 * @param t the node that roots the subtree.
 * @return the number of nodes.
 */
private int treeSize(BinaryNode<AnyType> t){

    int size = 1;                                      
    if(t.right != null){
        size = size + treeSize(t.right);        
    }
    if(t.left != null){
        size = size + treeSize(t.left);          
    }
    return t.treeSize = size;
} 

/**
 * 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 ) );    
}

// 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
}

    // Test program
public static void main( String [ ] args )
{
    BinarySearchTree<Integer> t = new BinarySearchTree<Integer>( );
    final int NUMS = 10;
    final int GAP  = 1;

    System.out.println( "Checking... (no more output means success)" );

    t.insert(55);
    t.insert(40);
    t.insert(35);
    t.insert(60);
    t.insert(70);
    t.insert(80);

    System.out.println("this is tree size: " + t.treeSize());
    int n = t.root.left.treeSize;
    System.out.println(n);
    t.nthElement(3);

}
}

编辑：我已经修改了nthElement(int n, BinaryNode<AnyType> t)andtreeSize(BinaryNode<AnyType t>方法。NullPointerException现在的问题是，除了 2 和 3 之外，我输入的任何数字都会得到 a 。

4

4 回答 4

3

问题是您需要从递归函数（或多个函数）返回计数和节点。如果你把它交给我，我会以一种会给你带来麻烦的方式来做:)

对象 nthElement(int n, BinaryNode t)
{
    // 我们在正确的节点上，返回它。
    if(n == 1) // 我会以 1 为基础，所以传入 1 会返回第一个元素。
         返回 t;

    // 检查树的左侧。
    如果（t.left！= null）{
        对象 o=nthElement(n-1, t.left);
        // 我们找到了正确的节点。
        if(o instanceof BinaryNode)
            返回 o;
        // 我们没有找到它，但让我们数一下我们找到的那些。（这就是“诀​​窍”）
        n=(整数)o;
    }
    // 我们没有更多的孩子，让我们返回我们当前的计数。
    如果（t.right == null）
        返回 n;

    // 右递归
    返回（nthElement（n-1，t.right）；
}

这是未经测试的手工编码，我经常在快速未经测试的代码上犯下巨大的逻辑错误，但这个概念是合理的。任何称职的老师都可能无法回答这个问题，因为返回值有两种完全不同的不相关类型，我正在修改一个参数，但我想给你留下一些乐趣！

用法必须检查返回值，如果它是 BinaryNode 的实例，如果不是树没有足够的节点，那就太好了。

也只是为了好玩，我认为 -(int)nthElement(0, t) 计算树中的节点数。

“真实”递归解决方案将返回一个带有 BinaryNode 和计数的新可变对象。当它被传递时，您将修改计数，为访问的每个节点减去 1，当您点击 0 时，您返回对象并将其提取为“BinaryNode”

于 2013-04-01T02:23:47.660 回答
1

您最简单（但效率最低）的方法类似于：

// Ignoring the possibility that there may not be n elements in the tree.
int leftSize = treeSize(t.left);
// If the size of the left tree is greater than n then the nth element must be up the left branch.
if ( leftSize >= n ) {
  return nthElement(n-1, t.left);
} else {
  // Otherwise it must be up the right branch.
  return nthElement(n-leftSize, t.right);
}

但是，最好执行一次Iterator，然后逐步执行 n 次。

于 2013-03-31T23:32:47.243 回答
0

这对我来说没问题。在保持计数的同时按顺序遍历树。

    int c = 0;
    public void findNth(int n, IntTree t) {

    if(!IntTree.isEmpty(t)) {
        findNth(n, t.left);
        c++;
        if(c==n)
            System.out.println("The element on position "+n+" is " + IntTree.value(t));
        findNth(n, t.right);

    }
于 2014-03-15T08:16:43.087 回答
0

我被震惊了两天解决了这个问题。我能够打印第 n 个到最后一个元素。但是退货有困难。终于可以使用下面的代码解决了：

    public class BinarySearchTree {

    Node root;

    public Node findNth(int n){
        if(root == null)
            return null;

        NodeCounter myNode = new NodeCounter();

        findNth(root,n, myNode);
        return myNode.node;
    }


    private void findNth(Node head, int n, NodeCounter nodeObj){

        if(head == null)
            return;

        findNth(head.left, n ,nodeObj);
        nodeObj.counter = nodeObj.counter + 1;
        if(n == nodeObj.counter){
            nodeObj.node = head;
            return;
        }
        if(n > nodeObj.counter)
            findNth(head.right,n,nodeObj);

    }

}

private class NodeCounter{
        Node node;
        int counter = 0;
}
class Node{
    Node left;
    Node right;
    int data;

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

}
于 2014-09-29T01:23:37.967 回答