// 面试题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 ;
}