《剑指offer》第三十七题（序列化二叉树）

// 面试题37：序列化二叉树

// 题目：请实现两个函数，分别用来序列化和反序列化二叉树。

#include "BinaryTree.h"

#include <iostream>

#include <fstream>

using namespace std;

void Serialize(const BinaryTreeNode* pRoot, ostream& stream)//序列化二叉树，ostream写文件流

{

    if (pRoot == nullptr)

    {

        stream << "$,";//用<<写文件

        return;

    }

    stream << pRoot->m_nValue << ',';

    Serialize(pRoot->m_pLeft, stream);

    Serialize(pRoot->m_pRight, stream);

}

bool ReadStream(istream& stream, int* number)//istream读文件流

{

    if (stream.eof())//检测stream是否读到头了

        return false;

    char buffer[];

    buffer[] = '\0';

    char ch;

    stream >> ch;//读取一个字符

    int i = ;

    while (!stream.eof() && ch != ',')

    {

        buffer[i++] = ch;//将字符串中的非'，'全读入buffer

        stream >> ch;//读的意思

    }

    bool isNumeric = false;

    if (i >  && buffer[] != '$')

    {

        *number = atoi(buffer);//将不为'$'转换为整型

        isNumeric = true;

    }

    return isNumeric;

}

void Deserialize(BinaryTreeNode** pRoot, istream& stream)//反序列化二叉树，istream读文件流

{

    int number;

    if (ReadStream(stream, &number))//里面函数完成两个功能：true说明不为$且是整型可读；操作number

    {

        *pRoot = new BinaryTreeNode();

        (*pRoot)->m_nValue = number;

        (*pRoot)->m_pLeft = nullptr;

        (*pRoot)->m_pRight = nullptr;

        Deserialize(&((*pRoot)->m_pLeft), stream);

        Deserialize(&((*pRoot)->m_pRight), stream);

    }

}

// ==================== Test Code ====================

bool isSameTree(const BinaryTreeNode* pRoot1, const BinaryTreeNode* pRoot2)

{

    if (pRoot1 == nullptr && pRoot2 == nullptr)

        return true;

    if (pRoot1 == nullptr || pRoot2 == nullptr)

        return false;

    if (pRoot1->m_nValue != pRoot2->m_nValue)

        return false;

    return isSameTree(pRoot1->m_pLeft, pRoot2->m_pLeft) &&

        isSameTree(pRoot1->m_pRight, pRoot2->m_pRight);

}

void Test(const char* testName, const BinaryTreeNode* pRoot)

{

    if (testName != nullptr)

        printf("%s begins: \n", testName);

    PrintTree(pRoot);

    const 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())

    {

        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();

    BinaryTreeNode* pNode6 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode10 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode9 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode11 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode8, pNode6, pNode10);

    ConnectTreeNodes(pNode6, pNode5, pNode7);

    ConnectTreeNodes(pNode10, pNode9, pNode11);

    Test("Test1", pNode8);

    DestroyTree(pNode8);

}

//            5

//          4

//        3

//

void Test2()

{

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    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();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode5, nullptr, pNode4);

    ConnectTreeNodes(pNode4, nullptr, pNode3);

    ConnectTreeNodes(pNode3, nullptr, pNode2);

    Test("Test3", pNode5);

    DestroyTree(pNode5);

}

void Test4()

{

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    Test("Test4", pNode5);

    DestroyTree(pNode5);

}

void Test5()

{

    Test("Test5", nullptr);

}

//        5

//         5

//          5

//         5

//        5

//       5 5

//      5   5

void Test6()

{

    BinaryTreeNode* pNode1 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode61 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode62 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode71 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode72 = CreateBinaryTreeNode();

    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, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    system("pause");

    return ;

}