搜索未排序树的特定节点

Question

大意是通过递归回溯遍历一棵树（BinaryNode，数据为Character），找到一个特定的char。该方法将输出从根到数据为指定字符的节点的路径。向左移动表示路径为 0，向右移动表示路径为 1。例如，到最上层根节点的路径为空字符串，向左 child 的路径为 0 （右侧为 1 child）。

到目前为止，我有一个递归 void 方法，其基本情况是如果找到匹配项，则该方法结束。否则，如果有左 child 我再次调用该方法，然后检查 and/or 是否也调用右 child。最后一节是当前根是叶节点，我会修改存储的路径以消除最近添加的 0 或 1，然后 return 到之前的递归调用。这是我目前所拥有的

//method head
if(c==root.getData()) return;

if(root.hasLeftChild()) //call method with left child as root, and a 0 added to path

//same for right child, only add a 1 instead of a 0

//if leaf node aka neither left or right child, path will now be a substring from 0 to path.length()-1

感谢任何帮助！

Answer 1

注意：由于没有提供 BinaryNode 的实现，我只是使用它应该提供的一些基本方法。

public String getPath(char c , BinaryNode<Character> node){
     if(node.getData() == c)//matching node found
          return "";

     if(node.right() != null){//check if right child is parent of match
          String tmp = getPath(c , node);
          if(tmp != null)//match found -> complete path from this node
               return "1" + tmp;
     }
     if(node.left() != null){//check if left child is parent of match
          String tmp = getPath(c , node);
          if(tmp != null)
               return "0" + tmp;
     }

     //c is no content of the tree with node as root -> return null
     return null;
}

这段代码合二为一。当它深入到树中时，它会搜索匹配的节点，当算法返回到树的根部时，会向后生成路径（结果顺序正确）。

Answer 2

recurAndFind(String str, Node x, char c){
if(x== null);
if(x.getChar() == c)
   return str;
else if(x.hasLeft())
    recurAndFind("0"+str,x.left,c);
else if(x.hasright())
     recurAndFind("1"+str,x.right,c);
}

这将执行您想要执行的操作，但您必须在收到字符串后检查内容是什么，并做出相应的决定。您需要向它发送一个空字符串。

搜索未排序树的特定节点

Searching for a specific node of an unsorted tree

java

tree

recursion

backtracking