查找树中的节点 N

发布于 2024-10-23 23:31:00 字数 268 浏览 3 评论 0原文

我在用 Java 编写以下方法时遇到问题

int findNodeN(节点节点，int n)

例如，如果二叉搜索树构造如下：

<前><代码> 20 10 30 1 14 25 35

那么如果 n=0，则返回节点 1，如果 n = 1，则返回节点 10，依此类推（即 inOrder 遍历）

感谢任何帮助

原文

I am having trouble coding in Java the following method

int findNodeN(Node node, int n)

For example if the binary search tree is constructed as following:

        20
   10       30    
 1   14   25   35

Then node 1 would be returned if n=0, node 10 would be returned if n = 1 and so on (i.e inOrder traversal)

Appreciate any help

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

等待圉鍢 2024-10-30 23:31:00

最简单的实现是将计数器变量设置为零。按照通常的顺序走树。当您转到右孩子时 - 增加计数器，当您转到父母并且您在左孩子中时 - 增加计数器。当计数器变得等于N时返回当前顶点。

回复收藏 0 原文

七月上 2024-10-30 23:31:00

这是我的一个版本，它与您需要的有点不同，但它是可以使用的：

public E findElement(E element)
{
    TreeNode<E> current = root;

    while (current != null)
    {
        if ( element.compareTo(current.getElement() ) == 0)   //If found
        {
            return current.getElement();
        } 
        else if( element.compareTo(current.getElement() ) < 0)    //If element is less
        {
            current = current.getLeftChild();               //Try the left child
        } 
        else                                                //If element is greater
        {
            current = current.getRightChild();             //Try the right child
        }
    }

//not found
return null;

}

很确定您可以使用递归来获得一些更简洁的代码，但这可以完成工作。

编辑：好的，尝试这样的事情：

public int findNodeN(Node node, int n, int callNumber) //Call initially with findNodeN(tree.getRoot(), n, 0)
{
    if (node.hasLeft())
        findNodeN(node.getLeftChild(), n, callNumber);
    if (callNumber == n)                     
         return node.getElement();
    else
         callNumber++;
    if (node.hasRight())
        printTreeInOrder(node.getRightChild(), n, callNumber);

}

这没有经过测试。
卡勒姆

Here's a version I have, it's a bit different from what you need, but it's something to work from:

public E findElement(E element)
{
    TreeNode<E> current = root;

    while (current != null)
    {
        if ( element.compareTo(current.getElement() ) == 0)   //If found
        {
            return current.getElement();
        } 
        else if( element.compareTo(current.getElement() ) < 0)    //If element is less
        {
            current = current.getLeftChild();               //Try the left child
        } 
        else                                                //If element is greater
        {
            current = current.getRightChild();             //Try the right child
        }
    }

//not found
return null;

}

Pretty sure you can use recursion to get some more concise code, but this gets the job done.

EDIT: OK, try something like this:

public int findNodeN(Node node, int n, int callNumber) //Call initially with findNodeN(tree.getRoot(), n, 0)
{
    if (node.hasLeft())
        findNodeN(node.getLeftChild(), n, callNumber);
    if (callNumber == n)                     
         return node.getElement();
    else
         callNumber++;
    if (node.hasRight())
        printTreeInOrder(node.getRightChild(), n, callNumber);

}

This isn't tested.
Calum

回复收藏 0 原文

~没有更多了~