剑指offer - 序列化二叉树

题目

请实现两个函数，分别序列化和反序列化二叉树。这里的序列化指的是将一棵二叉树保存到文件中，反序列化就是从文件中读取二叉树结点值重构原来的二叉树。

思路

使用前序遍历的顺序来序列化二叉树，因为前序遍历是从根结点开始的，在遍历二叉树碰到nullptr指针时，这些nullptr指针序列化为一个特殊的字符（'$'），另外，结点的数值之间使用特殊字符（如：‘,’）隔开。如下图二叉树

屏幕快照 2019-10-21 上午11.36.39.png

代码实现

#include <iostream>
#include <fstream>
using namespace std;

// 定义二叉树
struct BinaryTreeNode {
    int value;
    BinaryTreeNode *leftNode;
    BinaryTreeNode *rightNode;
    BinaryTreeNode *parent;
};

// ostream: 输出流
// 采用前序遍历实现序列化二叉树
void Serialize(const BinaryTreeNode *pRoot, ostream &stream) {
    if (pRoot == nullptr) { // 结点为空
        stream << "$,"; // 输出$,
        return;
    }

    stream << pRoot->value << ','; // 输出值
    Serialize(pRoot->leftNode, stream); // 递归左子树
    Serialize(pRoot->rightNode, stream); // 递归右子树
}

// 从流中读取数字
bool ReadStream(istream &stream, int *number) {
    if (stream.eof()) // 判断文件是否为空或者是否读到文件结尾了
        return false;

    char buffer[32];
    buffer[0] = '\0';

    char ch;
    stream >> ch; // 输入字符
    int i = 0;
    while (!stream.eof() && ch != ',') {
        buffer[i++] = ch;
        stream >> ch;
    }

    bool isNumeric = false;
    if (i > 0 && buffer[0] != '$') {
        *number = atoi(buffer); // atoi (表示 ascii to integer)是把字符串转换成整型数的一个函数
        isNumeric = true;
    }

    return isNumeric;
}

// 反序列化  istream: 输入流
void Deserialize(BinaryTreeNode **pRoot, istream &stream) {
    int number;
    if (ReadStream(stream, &number)) {
        *pRoot = new BinaryTreeNode(); // 创建结点
        (*pRoot)->value = number;
        (*pRoot)->leftNode = nullptr;
        (*pRoot)->rightNode = nullptr;

        // 递归创建左、右子树
        Deserialize(&(*pRoot)->leftNode, stream);
        Deserialize(&(*pRoot)->rightNode, stream);
    }
}

辅助测试代码

// 创建二叉树结点
BinaryTreeNode* CreateBinaryTreeNode(int value){
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->value = value;
    pNode->leftNode = nullptr;
    pNode->rightNode = nullptr;
    pNode->parent = nullptr;

    return pNode;
}

// 连接二叉树
void ConnectTreeNodes(BinaryTreeNode* pParent,
                      BinaryTreeNode* pLeft,
                      BinaryTreeNode* pRight){
    if(pParent != nullptr){
        pParent->leftNode = pLeft;
        pParent->rightNode = pRight;

        if(pLeft != nullptr)
            pLeft->parent = pParent;
        if(pRight != nullptr)
            pRight->parent = pParent;
    }
}

// 打印结点
void PrintTreeNode(BinaryTreeNode* pNode){
    if(pNode != nullptr) { // 结点存在
        printf("value of this node is: %d\n", pNode->value);

        if(pNode->leftNode != nullptr) // 左子树
            printf("value of its left child is: %d.\n", pNode->leftNode->value);
        else
            printf("left child is null.\n");

        if(pNode->rightNode != nullptr) // 右子树
            printf("value of its right child is: %d.\n", pNode->rightNode->value);
        else
            printf("right child is null.\n");
    } else {
        printf("this node is null.\n");
    }

    printf("\n");
}

// 打印二叉树
void PrintTree(BinaryTreeNode* pRoot) {
    PrintTreeNode(pRoot);

    if(pRoot != nullptr) {
        if(pRoot->leftNode != nullptr)
            PrintTree(pRoot->leftNode);

        if(pRoot->rightNode != nullptr)
            PrintTree(pRoot->rightNode);
    }
}

// 销毁二叉树
void DestroyTree(BinaryTreeNode* pRoot) {
    if(pRoot != nullptr) {
        BinaryTreeNode* pLeft = pRoot->leftNode;
        BinaryTreeNode* pRight = pRoot->rightNode;

        delete pRoot;
        pRoot = nullptr;

        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}

测试代码部分

// 是否是相同的树
bool isSameTree(const BinaryTreeNode* pRoot1, const BinaryTreeNode* pRoot2) {
    if(pRoot1 == nullptr && pRoot2 == nullptr)
        return true;

    if(pRoot1 == nullptr || pRoot2 == nullptr)
        return false;

    if(pRoot1->value != pRoot2->value)
        return false;

    return isSameTree(pRoot1->leftNode, pRoot2->leftNode) &&
    isSameTree(pRoot1->rightNode, pRoot2->rightNode);
}

void Test(const char* testName, BinaryTreeNode* pRoot) {
    if(testName != nullptr)
        printf("%s begins: \n", testName);

    // 打印二叉树
    PrintTree(pRoot);

    // 文件名
    char* fileName = "test.txt";
    ofstream fileOut;
    fileOut.open(fileName); // 打开文件

    // 序列化二叉树
    Serialize(pRoot, fileOut);
    fileOut.close(); // 文件读写操作完成之后，将文件关闭以使文件重新变为可访问的

    // print the serialized file
    ifstream fileIn1;
    char ch;
    fileIn1.open(fileName);
    while(!fileIn1.eof()) // 如果读文件到达文件末尾，返回true
    {
        fileIn1 >> ch;
        cout << ch;
    }
    fileIn1.close();
    cout << endl;

    // 反序列化
    ifstream fileIn2;
    fileIn2.open(fileName);
    BinaryTreeNode* pNewRoot = nullptr;
    Deserialize(&pNewRoot, fileIn2);
    fileIn2.close();

    // 打印新的二叉树
    PrintTree(pNewRoot);

    // 新老二叉树是否相同
    if(isSameTree(pRoot, pNewRoot))
        printf("The deserialized tree is same as the oritinal tree.\n\n");
    else
        printf("The deserialized tree is NOT same as the oritinal tree.\n\n");

    // 销毁二叉树
    DestroyTree(pNewRoot);
}

//            8
//        6      10
//       5 7    9  11
void Test1()
{
    BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
    BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9);
    BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11);

    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode9, pNode11);

    Test("Test1", pNode8);

    DestroyTree(pNode8);
}

//            5
//          4
//        3
//      2
void Test2()
{
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);

    ConnectTreeNodes(pNode5, pNode4, nullptr);
    ConnectTreeNodes(pNode4, pNode3, nullptr);
    ConnectTreeNodes(pNode3, pNode2, nullptr);

    Test("Test2", pNode5);

    DestroyTree(pNode5);
}

//        5
//         4
//          3
//           2
void Test3()
{
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);

    ConnectTreeNodes(pNode5, nullptr, pNode4);
    ConnectTreeNodes(pNode4, nullptr, pNode3);
    ConnectTreeNodes(pNode3, nullptr, pNode2);

    Test("Test3", pNode5);

    DestroyTree(pNode5);
}

void Test4()
{
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);

    Test("Test4", pNode5);

    DestroyTree(pNode5);
}

void Test5()
{
    Test("Test5", nullptr);
}

//        5
//         5
//          5
//         5
//        5
//       5 5
//      5   5
void Test6()
{
    BinaryTreeNode* pNode1 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode2 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode3 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode61 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode62 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode71 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode72 = CreateBinaryTreeNode(5);

    ConnectTreeNodes(pNode1, nullptr, pNode2);
    ConnectTreeNodes(pNode2, nullptr, pNode3);
    ConnectTreeNodes(pNode3, pNode4, nullptr);
    ConnectTreeNodes(pNode4, pNode5, nullptr);
    ConnectTreeNodes(pNode5, pNode61, pNode62);
    ConnectTreeNodes(pNode61, pNode71, nullptr);
    ConnectTreeNodes(pNode62, nullptr, pNode72);

    Test("Test6", pNode1);

    DestroyTree(pNode1);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";

    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
    return 0;
}

参考

《剑指offer》