如何编写查找某个节点的代码。具体地说,我怎么说一个节点在我检查之后被访问了呢?
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/
发布于 2018-07-28 05:41:40
将图节点标记为已访问的唯一目的是确保您不会陷入无限循环,因为图可以包含循环。
二叉树是一种特殊的图,它不包含循环,因此在进行遍历时不需要将节点标记为已访问。
此外,通常二叉树的排序方式是:当前节点包含值X,其左子树具有小于X的节点,其右子树具有大于X的节点。这使得搜索需要对数时间,在您演示的代码中,您似乎没有利用这一点。
因此,我认为您对二叉树的工作原理没有很好的理解,在实现此功能之前,您应该进行更多的研究。
https://stackoverflow.com/questions/51565755
复制相似问题