Java 递归函数行为
Java Recursive function behavoir
我在 Java 中完成了一个 BinaryTree class 的开发，它构建了一个 Huffman 风格的二进制 tree/map 到 "encode" 一个短语到一个二进制值。
一些方法使用递归到 populate/traverse 树的节点。我有一个编码字符串的方法，比如 test 到 01111110001。为了对其进行编码，我有一个函数可以将树的路径映射到具有该字符的节点。我还有一个搜索节点以找到该字符的叶节点的功能。
一切正常：树已构建，我可以搜索和定位节点，并且映射有效。当我为 searchNode 方法输出节点参数时，看起来代码可以很好地遍历树......但它在找到节点后并没有退出。它多次找到它。我对方法做了一些不同的变体，我无法让它退出遍历整个树，或者一旦它找到 第一次 [=] 的节点就停止39=].
我想知道为什么代码在第一次找到节点后不会停止，并寻找有关如何优化它的任何建议。
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 使用 "this is a test" 作为树并搜索 '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 次。然而，当它编码 string/characters 时，它可以很好地转换为 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) 找到该节点（并且 return 是一个非 null 结果），那么您立即重新搜索 return 该值。从根开始，它将（最终）向右搜索，到第 8 个节点，然后是第 5 个节点，然后从第 3 个节点向左搜索。然后它会再次从 3 节点向左搜索，returning 到非空的 5 节点。 5节点重复查找（因为得到了一个非空值），所以你再次查找3节点，找到值，再次查找（得到return值），即return ed，然后 returned 再次到 8 节点。 8节点得到一个非空值，所以再次搜索到return值（所以我们访问5, and 3, and 3, and 5, and 3 and 3）和return到根，再次搜索 8 (5 & 3 & 3 and 5 & 3 & 3) 和 returns.
您想保存找到的值，所以可以return它！
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;
我在 Java 中完成了一个 BinaryTree class 的开发，它构建了一个 Huffman 风格的二进制 tree/map 到 "encode" 一个短语到一个二进制值。
一些方法使用递归到 populate/traverse 树的节点。我有一个编码字符串的方法，比如 test 到 01111110001。为了对其进行编码，我有一个函数可以将树的路径映射到具有该字符的节点。我还有一个搜索节点以找到该字符的叶节点的功能。
一切正常：树已构建，我可以搜索和定位节点，并且映射有效。当我为 searchNode 方法输出节点参数时，看起来代码可以很好地遍历树......但它在找到节点后并没有退出。它多次找到它。我对方法做了一些不同的变体，我无法让它退出遍历整个树，或者一旦它找到 第一次 [=] 的节点就停止39=].
我想知道为什么代码在第一次找到节点后不会停止，并寻找有关如何优化它的任何建议。
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 使用 "this is a test" 作为树并搜索 '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 次。然而，当它编码 string/characters 时，它可以很好地转换为 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) 找到该节点（并且 return 是一个非 null 结果），那么您立即重新搜索 return 该值。从根开始，它将（最终）向右搜索，到第 8 个节点，然后是第 5 个节点，然后从第 3 个节点向左搜索。然后它会再次从 3 节点向左搜索，returning 到非空的 5 节点。 5节点重复查找（因为得到了一个非空值），所以你再次查找3节点，找到值，再次查找（得到return值），即return ed，然后 returned 再次到 8 节点。 8节点得到一个非空值，所以再次搜索到return值（所以我们访问5, and 3, and 3, and 5, and 3 and 3）和return到根，再次搜索 8 (5 & 3 & 3 and 5 & 3 & 3) 和 returns.
您想保存找到的值，所以可以return它！
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;