java - 搜索未排序树的特定节点

Question

总体思路是使用递归回溯(BinaryNode，数据是Character)来遍历一棵树，找到特定的char。该方法将输出从根到数据为指定字符的节点的路径。向左移动意味着路径将有 0，向右移动意味着路径将有 1。因此，例如，到最上面的根节点的路径是一个空字符串，到左子节点的路径是 0(对于正确的 child )。

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

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

此代码将所有功能合而为一。当它深入到树中时，它会搜索匹配的节点，当算法返回到树的根部时，会向后生成路径(结果按正确的顺序)。