我用Java完成了一个BinaryTree类的开发，它构建了一个霍夫曼风格的二叉树/映射，将一个短语"编码"成二进制值。
一些方法使用递归来填充/遍历树的节点。 我有一个对字符串进行编码的方法，比如test01111110001. 为了对其进行编码，我有一个函数，可以将树的路径映射到具有该字符的节点。 我还有一个搜索节点以查找该字符的叶节点的功能。
一切正常：树已构建，我可以搜索和定位节点，并且映射有效。 当我输出searchNode方法的节点参数时，看起来代码正在遍历树......但它在找到节点后不会退出。 它会多次找到它。我已经对方法进行了几种不同的变体，我无法让它退出遍历整个树，或者在第一次找到节点后停止。
我想知道为什么代码在第一次找到节点后不会停止，并寻找有关如何优化它的任何建议。
public class BinaryTree {
---snip ---
/*
* searchNode
* Searches nodes for a value
*
* @param n Node to start or focus at
* @param c char character to search for
* @return Node containing value
*/
public Node searchNode(Node n, char c) {
System.out.println(n);
if(n != null) {
if(n._char == c) { return n; }
if(this.searchNode(n._leftChild, c) != null) {
return this.searchNode(n._leftChild, c);
}
if(this.searchNode(n._rightChild, c) != null) {
return this.searchNode(n._rightChild, c);
}
}
return null;
}
/*
* mapPath
* Maps path with 1s or 0s from root node to
* node containing char
*
* @param n Node to map to
* @return StringBuilder string of map
*/
public StringBuilder mapPath(Node n) {
if(n == null) { return new StringBuilder(1); }
StringBuilder sb = new StringBuilder(256);
if(n == this._root || n._parent == null) {
sb.insert(0, "0");
return sb;
}
Node p = n._parent;
while(p != null) {
if(p._leftChild == n) {
sb.insert(0, "0");
} else {
if(p._rightChild == n) {
sb.insert(0, "1");
}
}
n = p;
p = p._parent;
}
return sb;
}
/*
* encodeString
* Encodes a string with appropriate binary value
*
* @param s String to encode
* @returns encoded String(Builder)
*/
public StringBuilder encodeString(String s) {
StringBuilder sb = new StringBuilder(s.length() * 10);
char[] st = s.toCharArray();
for(char stt : st) {
sb.append(this.mapPath(this.searchNode(this._root, stt)));
}
return sb;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
BinaryTree bt = new BinaryTree(args[0]);
bt.buildTree();
System.out.println(bt.searchNode(bt._root, args[1].toCharArray()[0]));
//System.out.println(bt.encodeString(args[1]));
}
}
第一个参数是要编码的短语或数据。 我要传递的第二个参数是要搜索的字符，因此java BinaryTree this is a test a树使用"这是一个测试"并搜索"a"。
这棵树看起来像
14
/
6 8
/ /
s t _ 5
/
i 3
/
a 2
/
h e
当我运行java BinaryTree this is a test i时，我得到以下输出：
_ - 14[parent=null *root*]
_ - 6[parent=_ - 14[parent=null *root*]]
s - 3[parent=_ - 6[parent=_ - 14[parent=null *root*]]]
null
null
t - 3[parent=_ - 6[parent=_ - 14[parent=null *root*]]]
null
null
_ - 8[parent=_ - 14[parent=null *root*]]
- 3[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
null
null
_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
_ - 8[parent=_ - 14[parent=null *root*]]
- 3[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
null
null
_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
i - 2[parent=_ - 5[parent=_ - 8[parent=_ - 14[parent=null *root*]]]]
输出包括节点的父节点，以帮助我在调试时可视化树。
你可以看到它找到了字符"i"9次。然而，当它对字符串/字符进行编码时，它可以很好地转换为 110。
它不会在你第一次找到节点时停止，因为你在找到它后会继续搜索。
if(this.searchNode(n._leftChild, c) != null) {
return this.searchNode(n._leftChild, c);
}
if(this.searchNode(n._rightChild, c) != null) {
return this.searchNode(n._rightChild, c);
}
如果this.searchNode(n._leftChild, c)找到节点(并返回非null结果)，则立即重做搜索以返回值。 从根目录开始，它将(最终)向右搜索，到 8 节点，然后搜索 5 节点，然后从 3 节点向左搜索。 然后它将再次从 3 节点向左搜索，以非空返回 5 节点。 5 节点重复搜索(因为它得到了一个非空值)，所以你再次搜索 3 节点，找到值，再次搜索(获取返回值)，返回该值，然后再次返回到 8 节点。 8 节点获得一个非空值，因此再次搜索以返回值(因此我们访问 5、3、3、5、3 和 3)并返回根目录，根目录再次搜索 8(5 & 3 和 5 & 3 和 5 & 3 &3)并返回。
您想保存找到的价值，以便可以将其退回！
Node result;
result = this.searchNode(n._leftChild, c);
if (result != null)
return result;
result = this.searchNode(n._rightChild, c);
if (result != null)
return result;
交互：
Node result = null;
if (n != null) {
...
result = this.searchNode(n._leftChild, c);
if (result == null)
result = this.searchNode(n._rightChild, c);
}
return result;