Java递归函数行为

Question

我用 Java 开发了一个 BinaryTree 类，它构建了一个霍夫曼风格的二叉树/映射来将短语“编码”为二进制值。

一些方法使用递归来填充/遍历树的节点。我有一个编码字符串的方法，比如 test 到 01111110001。为了对其进行编码，我有一个函数可以将树的路径映射到具有该字符的节点。我还有一个搜索节点以找到该字符的叶节点的函数。

一切正常:树已构建，我可以搜索和定位节点，并且映射有效。当我为 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 对树使用“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 次。然而，当它对字符串/字符进行编码时，它可以很好地转换为 110。

Answer 1

它不会在你第一次找到节点时停止，因为找到它后你会继续搜索。

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 结果)，那么您立即重新搜索以返回值(value)。从根开始，它将(最终)向右搜索，到第 8 个节点，然后是第 5 个节点，然后从第 3 个节点向左搜索。然后再从3节点向左搜索，返回到非空的5节点。 5节点重复查找(因为得到了一个非空值)，所以你再次查找3节点，找到值，再次查找(得到返回值)，返回，再次返回给8节点. 8 节点获得一个非空值，因此再次搜索以返回该值(因此我们访问 5, and 3, and 3, and 5, and 3 and 3)并返回到根，再次搜索 8 (5 & 3 & 3 and 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;