32

今日、二分木のシリアライズを依頼された面接に行きました。ノード i の子 (レベル順トラバーサルの番号付け) が左の子の 2*i インデックスと右の子の 2*i + 1 にある配列ベースのアプローチを実装しました。インタビュアーは多かれ少なかれ満足しているように見えましたが、シリアライズとは正確には何を意味するのでしょうか? ディスクに書き込むためにツリーをフラット化することに特に関連していますか、それともツリーをシリアル化することには、ツリーをリンクされたリストに変換することも含まれますか。また、ツリーを (二重に) リンクされたリストにフラット化し、それを再構築するにはどうすればよいでしょうか? リンクされたリストからツリーの正確な構造を再現できますか?

4

11 に答える 11

13

これらの記事はすべて、主にシリアライゼーションの部分について語っています。デシリアライゼーションの部分は、1 回のパスで実行するのが少し難しいです。

逆シリアル化のための効率的なソリューションも実装しました。

問題: 正の数を含む二分木をシリアライズおよびデシリアライズします。

シリアル化部分:

  1. null を表すには 0 を使用します。
  2. preorder トラバーサルを使用して整数のリストにシリアル化します。

逆シリアル化部分:

  1. 整数のリストを受け取り、逆シリアル化に再帰ヘルパー メソッドを使用します。
  2. 再帰的デシリアライザーはペア (BTNode ノード、int nextIndexToRead) を返します。ここで、node はこれまでに構築されたツリー ノードであり、nextIndexToRead はシリアル化された数値のリストで次に読み取られる数値の位置です。

以下は Java のコードです。

public final class BinaryTreeSerializer
{
    public static List<Integer> Serialize(BTNode root)
    {
        List<Integer> serializedNums = new ArrayList<Integer>();

        SerializeRecursively(root, serializedNums);

        return serializedNums;
    }

    private static void SerializeRecursively(BTNode node, List<Integer> nums)
    {
        if (node == null)
        {
            nums.add(0);
            return;
        }

        nums.add(node.data);
        SerializeRecursively(node.left, nums);
        SerializeRecursively(node.right, nums);
    }

    public static BTNode Deserialize(List<Integer> serializedNums)
    {
        Pair pair = DeserializeRecursively(serializedNums, 0);

        return pair.node;
    }

    private static Pair DeserializeRecursively(List<Integer> serializedNums, int start)
    {        
        int num = serializedNums.get(start);

        if (num == 0)
        {
            return new Pair(null, start + 1);
        }

        BTNode node = new BTNode(num);

        Pair p1 = DeserializeRecursively(serializedNums, start + 1);
        node.left = p1.node;

        Pair p2 = DeserializeRecursively(serializedNums, p1.startIndex);
        node.right = p2.node;

        return new Pair(node, p2.startIndex);
    }

    private static final class Pair
    {
        BTNode node;
        int startIndex;

        private Pair(BTNode node, int index)
        {
            this.node = node;
            this.startIndex = index;
        }
    }
}

public class BTNode 
{
    public int data;
    public BTNode left;
    public BTNode right;

    public BTNode(int data)
    {
        this.data = data;
    }
}
于 2013-08-24T20:28:43.597 に答える
9

pre order traversal を使用して、バイナリ ツリーをシリアル化します。ツリーを逆シリアル化するために、同じ事前注文トラバーサルを使用します。エッジケースに注意してください。ここでヌルノードは「#」で表されます 

public static String serialize(TreeNode root){
            StringBuilder sb = new StringBuilder();
            serialize(root, sb);
            return sb.toString();
        }

    private static void serialize(TreeNode node, StringBuilder sb){
        if (node == null) {
            sb.append("# ");
        } else {
            sb.append(node.val + " ");
            serialize(node.left, sb);
            serialize(node.right, sb);
        }
    }

    public static TreeNode deserialize(String s){
        if (s == null || s.length() == 0) return null;
        StringTokenizer st = new StringTokenizer(s, " ");
        return deserialize(st);
    }

    private static TreeNode deserialize(StringTokenizer st){
        if (!st.hasMoreTokens())
            return null;
        String val = st.nextToken();
        if (val.equals("#"))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = deserialize(st);
        root.right = deserialize(st);
        return root;
    }
于 2016-01-18T17:56:33.533 に答える
7

アプローチ 1: Inorder トラバーサルと Preorder トラバーサルの両方を実行して、ツリー データをシリアル化します。デシリアライゼーションでは、プリオーダーを使用し、インオーダーで BST を実行して、ツリーを適切に形成します。

構造が異なる場合でも、A -> B -> C は予約注文として表すことができるため、両方が必要です。

アプローチ 2: 左または右の子が null の場合は常に # をセンチネルとして使用します.....

于 2013-02-23T19:49:53.920 に答える
0

最善の方法は、特別な文字 (前のコメントで述べた # など) をセンチネルとして使用することです。空間の複雑さと時間の複雑さの両方の点で、インオーダートラバーサル配列とプリオーダー/ポストオーダートラバーサル配列を構築するよりも優れています。また、実装もはるかに簡単です。

リンクされたリストは、ツリーを再構築するために const 要素のアクセス時間が必要なため、ここでは適していません。

于 2014-03-19T22:07:29.500 に答える
0

順序通りのトラバーサルを実行し、ルート キーとすべてのノード キーを std::list またはツリーを平坦化する選択した他のコンテナーに配置するのはどうですか。次に、boost ライブラリを使用して、選択した std::list またはコンテナーを単純にシリアル化します。

逆は単純で、バイナリ ツリーへの標準的な挿入を使用してツリーを再構築します。これは非常に大きなツリーでは完全に効率的ではないかもしれませんが、ツリーを std::list に変換するランタイムは最大で O(n) であり、ツリーを再構築するのは最大で O(log n) です。

データベースを Java から C++ に変換するときに、C++ でコーディングしたばかりのツリーをシリアル化するためにこれを実行しようとしています。

于 2013-03-12T17:59:28.297 に答える