首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何使用递归找到二叉树的某个节点?

如何使用递归找到二叉树的某个节点?
EN

Stack Overflow用户
提问于 2018-07-28 05:23:19
回答 1查看 43关注 0票数 -2

如何编写查找某个节点的代码。具体地说,我怎么说一个节点在我检查之后被访问了呢?

public Iterator<T> pathToRoot(T targetElement, BinaryTreeNode<T> current)
        throws ElementNotFoundException
    {
        Stack<BinaryTreeNode<T>> myStack = new Stack<>();
        if (current == null)
            return null;

        if (current.element.equals(targetElement)) //found it
        {
            myStack.push(current); //adds the current element to the stack 
        }
            // mark as visited
            //mark node also as found
            // return the found element

        if (current.hasLeftChild() || current.hasRightChild()) //if the current node has a left or right child
        {
            // mark node as visited
        }
        if (current.hasLeftChild())//if the current node has a left child node
            pathToRoot(targetElement, current.getLeft()); // check the left child node

        if (current.hasRightChild())//same thing as above but for the right
            pathToRoot(targetElement, current.getRight());

        if(current != targetElement && /*node has been visited*/)
            myStack.pop(); // pop node from the stack

        return myStack.toString(); //return string of path to root
    }

/using a dfs search to find a node/

EN

回答 1

Stack Overflow用户

发布于 2018-07-28 05:41:40

将图节点标记为已访问的唯一目的是确保您不会陷入无限循环,因为图可以包含循环。

二叉树是一种特殊的图,它不包含循环,因此在进行遍历时不需要将节点标记为已访问。

此外,通常二叉树的排序方式是:当前节点包含值X,其左子树具有小于X的节点,其右子树具有大于X的节点。这使得搜索需要对数时间,在您演示的代码中,您似乎没有利用这一点。

因此,我认为您对二叉树的工作原理没有很好的理解,在实现此功能之前,您应该进行更多的研究。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/51565755

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档