Tree को Serialize और Deserialize करना

किसी tree को serialize करना इसे notes की एक flat list के रूप में लिखने जैसा है, और deserialize करना उन notes का उपयोग tree को बिल्कुल जैसा था वैसा rebuild करने के लिए करना है।

In this page:

Serialization Idea
Null Markers
Deserialization
Round Trip
Practice

Syntax

markup

def serialize(node):
    if node is None:
        return ['#']
    return [str(node.value)] + serialize(node.left) + serialize(node.right)

def deserialize(values):
    v = next(values)
    if v == '#':
        return None
    node = TreeNode(int(v))
    node.left = deserialize(values)
    node.right = deserialize(values)
    return node

Serialization Idea

Serialization एक tree structure को एक flat, storable sequence (जैसे एक string या array) में convert करता है ताकि इसे एक file में save किया जा सके, network पर भेजा जा सके, या cache किया जा सके — trees को पहले flatten किए बिना इन linear formats में सीधे store नहीं किया जा सकता।

उदाहरण: Serialization Idea

#include <iostream>
#include <string>
using namespace std;
struct Node { int val; Node *left, *right; };
void serialize(Node* n, string& out) {
    if (!n) { out += "# "; return; }
    out += to_string(n->val) + " ";
    serialize(n->left, out);
    serialize(n->right, out);
}
int main() {
    Node l={2,nullptr,nullptr}, r={3,nullptr,nullptr};
    Node root={1,&l,&r};
    string out;
    serialize(&root, out);
    cout << "Serialized: " << out << endl;
    return 0;
}

public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static void serialize(Node n, StringBuilder out) {
        if (n == null) { out.append("# "); return; }
        out.append(n.val).append(" ");
        serialize(n.left, out);
        serialize(n.right, out);
    }
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2); root.right = new Node(3);
        StringBuilder out = new StringBuilder();
        serialize(root, out);
        System.out.println("Serialized: " + out);
    }
}

class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def serialize(n, out):
    if n is None:
        out.append("#")
        return
    out.append(str(n.val))
    serialize(n.left, out)
    serialize(n.right, out)

root = Node(1)
root.left = Node(2); root.right = Node(3)
out = []
serialize(root, out)
print("Serialized:", " ".join(out))

#include <stdio.h>
#include <stddef.h>
struct Node { int val; struct Node *left, *right; };
void serialize(struct Node* n) {
    if (!n) { printf("# "); return; }
    printf("%d ", n->val);
    serialize(n->left);
    serialize(n->right);
}
int main() {
    struct Node l={2,NULL,NULL}, r={3,NULL,NULL};
    struct Node root={1,&l,&r};
    printf("Serialized: ");
    serialize(&root);
    printf("\n");
    return 0;
}

Null Markers

चूंकि trees के arbitrary positions पर missing children हो सकते हैं, serialization को output sequence में explicit null markers चाहिए बिल्कुल record करने के लिए कि कहां एक child absent है — उनके बिना, original tree की shape इसे rebuild करते समय ambiguous होगी।

उदाहरण: Null Markers

#include <iostream>
using namespace std;
int main() {
    cout << "Without a '#' marker for missing children, the flat sequence '1 2 3' is ambiguous -- multiple trees could produce it" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Without a '#' marker for missing children, the flat sequence '1 2 3' is ambiguous -- multiple trees could produce it");
    }
}

print("Without a '#' marker for missing children, the flat sequence '1 2 3' is ambiguous -- multiple trees could produce it")

#include <stdio.h>
int main() {
    printf("Without a '#' marker for missing children, the flat sequence '1 2 3' is ambiguous -- multiple trees could produce it\n");
    return 0;
}

Deserialization

Deserialization process को reverse करता है, flat sequence वापस पढ़कर और original tree को node by node reconstruct करते हुए, वही traversal order और null markers उपयोग करते हुए जो serialization के दौरान उपयोग हुए यह जानने के लिए कि हर node बिल्कुल कहां belong करता है।

उदाहरण: Deserialization

#include <iostream>
#include <sstream>
#include <string>
using namespace std;
struct Node { int val; Node *left, *right; };
Node* deserialize(istringstream& in) {
    string token; in >> token;
    if (token == "#") return nullptr;
    Node* n = new Node{stoi(token), nullptr, nullptr};
    n->left = deserialize(in);
    n->right = deserialize(in);
    return n;
}
int main() {
    istringstream in("1 2 # # 3 # #");
    Node* root = deserialize(in);
    cout << "Rebuilt root value: " << root->val << endl;
    return 0;
}

import java.util.*;
public class Main {
    static class Node { int val; Node left, right; Node(int v){val=v;} }
    static Scanner sc;
    static Node deserialize() {
        String token = sc.next();
        if (token.equals("#")) return null;
        Node n = new Node(Integer.parseInt(token));
        n.left = deserialize();
        n.right = deserialize();
        return n;
    }
    public static void main(String[] args) {
        sc = new Scanner("1 2 # # 3 # #");
        Node root = deserialize();
        System.out.println("Rebuilt root value: " + root.val);
    }
}

class Node:
    def __init__(self, val):
        self.val = val; self.left = None; self.right = None

def deserialize(tokens):
    token = next(tokens)
    if token == "#":
        return None
    n = Node(int(token))
    n.left = deserialize(tokens)
    n.right = deserialize(tokens)
    return n

data = "1 2 # # 3 # #"
root = deserialize(iter(data.split()))
print("Rebuilt root value:", root.val)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Node { int val; struct Node *left, *right; };
char* tokens[20]; int idx = 0;
struct Node* deserialize() {
    char* token = tokens[idx++];
    if (strcmp(token, "#") == 0) return NULL;
    struct Node* n = malloc(sizeof(struct Node));
    n->val = atoi(token); n->left = NULL; n->right = NULL;
    n->left = deserialize();
    n->right = deserialize();
    return n;
}
int main() {
    char data[] = "1 2 # # 3 # #";
    char* tok = strtok(data, " ");
    while (tok) { tokens[idx == 0 ? 0 : idx] = tok; tok = strtok(NULL, " "); }
    idx = 0;
    struct Node* root = deserialize();
    printf("Rebuilt root value: %d\n", root->val);
    return 0;
}

Round Trip

एक सही serialize/deserialize implementation को एक perfect round trip होना चाहिए: एक tree serialize करना और फिर उस output को deserialize करना एक tree reconstruct करना चाहिए जो structurally original जैसा identical हो, किसी भी missing children की exact positions सहित।

उदाहरण: Round Trip

#include <iostream>
using namespace std;
int main() {
    cout << "serialize(deserialize(serialize(tree))) must equal serialize(tree) -- structure and values both preserved" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("serialize(deserialize(serialize(tree))) must equal serialize(tree) -- structure and values both preserved");
    }
}

print("serialize(deserialize(serialize(tree))) must equal serialize(tree) -- structure and values both preserved")

#include <stdio.h>
int main() {
    printf("serialize(deserialize(serialize(tree))) must equal serialize(tree) -- structure and values both preserved\n");
    return 0;
}

Practice

यह pattern कहीं भी ज़रूरी है जहां tree-shaped data को memory छोड़कर बाद में वापस आना हो — application state save करना, network API पर tree structures transmit करना, या एक parsed document structure को disk पर persist करना।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
    cout << "Used for saving app state, sending trees over a network, or persisting them to a file" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Used for saving app state, sending trees over a network, or persisting them to a file");
    }
}

print("Used for saving app state, sending trees over a network, or persisting them to a file")

#include <stdio.h>
int main() {
    printf("Used for saving app state, sending trees over a network, or persisting them to a file\n");
    return 0;
}

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson Tree Views Left Right Top Bottom Next Lesson → Heap Introduction