java - 序列化 BST 树

Question

我正在尝试序列化 BST，以便其他程序可以读取它。输出包含节点，后跟其所有子节点及其子节点的子节点等。如果没有其他子节点，则后跟右括号。

我的方法输出

(4 (2 (1 ) ) ( 3 ) ) (6  (5 )) (7 ))




public String serializePrefix(){
        StringBuilder str = new StringBuilder();
        serializePrefix (root, str, " ");
        return str.toString();
    }


    private void serializePrefix (Node t, StringBuilder str, String sep){
        int ID = 1;
        if (t == null)
            str.append(")");
        else{


                str.append("(" + t.data.toString() );
                str.append(sep);
                serializePrefix (t.left, str, sep);
                serializePrefix (t.right, str, sep);

        }

        ID++;

    }

我需要输出

(4 (2 (1 ) (3 ) ) (6 (5 ) (7 ) ) ))

这将创建树

         4
       /  \
      2    6
    /  \  / \
   1   3  5  7 

Answer 1

您的第一个问题情况是当您找到叶子时:所有右括号 ()) 都被加倍，因为您尝试向左和右链接前进，但发现 null，这会触发代码中的结束括号。

private void serializePrefix (Node t, StringBuilder str, String sep){
    int ID = 1;
    if (t == null)
        //ERROR: if empty node found, apply close bracket
        str.append(")");
    else{
        str.append("(" + t.data.toString() );
        str.append(sep);

        //this is the problem part, for example for node number 1:
        serializePrefix (t.left, str, sep); //this writes ")" first time
        serializePrefix (t.right, str, sep); //this writes ")" second time

    }

    ID++;

}

第二个问题是，在最后一个分支上，您的括号将无法正确关闭，因为当您的算法“后退”到根时，它不会在逐个后退时关闭打开的括号...

修复建议:

private void serializePrefix (Node t, StringBuilder str, String sep){
    int ID = 1;
    if (t == null)
        // do nothing!
        // str.append(")");
    else{
        str.append("(" + t.data.toString() );
        str.append(sep);

        //this is the problem part, for example for node number 1:
        serializePrefix (t.left, str, sep); //this writes ")" first time
        serializePrefix (t.right, str, sep); //this writes ")" second time

        //close opened bracket
        str.append(")");
    }

    ID++;

}

(顺便说一句，一般建议是尝试在距离打开位置可见的距离内关闭打开的内容...这对于控制数据库连接等资源周围的泄漏有很大帮助。)