树的存储问题
1.如何把一棵树存储到磁盘上？此时树的数据结构该如何定义？
2.如何读取问题1中存储到磁盘上的文件并再次生成一棵树？
菜鸟刚会爬，还望高手不吝赐教。
给代码的话，就用C语言吧。 树 存储 磁盘
[解决办法]
1、用相同的顺序写或者读，用中序容易实现
2、处理好空节点或者NULL指针的设置。
[解决办法]
参考C语言版数据结构这本书吧
[解决办法]
偶像元首……
[解决办法]
序列化，持久化。。
[解决办法]
序列化成XML试试。
[解决办法]
c不是很熟，用c++写了个简单的demo，二进制读取文件。代码不是很复杂，注释没详细写。
凑活着看看，可以参考，自己改成c的
#include <iostream>
#include <fstream>
struct TreeNode
{
int data;
TreeNode* parent;
TreeNode* left;
TreeNode* right;
};
void addnode(TreeNode*& node, int data, int flag);
void addroot(TreeNode*& node, int data);
void addleft(TreeNode*& node, int data) {addnode(node, data, 1);}
void addright(TreeNode*& node, int data) {addnode(node, data, 2);}
void erasetree(TreeNode*& node);
void inordertrave(TreeNode* node);
void preordertrave(TreeNode* node);
void postordertrave(TreeNode* node);
std::ofstream& writetreetofile(std::ofstream& fout, TreeNode* node);
std::ifstream& readtreefromfile(std::ifstream& fin, TreeNode*& node, int flag =0);
int main()
{
TreeNode* root = NULL;
addroot(root, 0);
addleft(root, 1);
addright(root, 2);
TreeNode* p = root->left;
addleft(p, 3);
addright(p, 4);
p = root->right;
addleft(p, 5);
inordertrave(root);
std::cout << std::endl;
preordertrave(root);
std::cout << std::endl;
postordertrave(root);
std::cout << std::endl;
std::ofstream fout;
fout.open("tree.dat", std::ios_base::out
[解决办法]
std::ios_base::binary);
if (!fout.is_open())
{
std::cerr << "open file error.\n";
erasetree(root);
exit(EXIT_FAILURE);
}
writetreetofile(fout, root);
fout.close();
erasetree(root);
std::ifstream fin;
fin.open("tree.dat", std::ios_base::in
[解决办法]
std::ios_base::binary);
if (!fin.is_open())
{
std::cerr << "open file error.\n";
erasetree(root);
exit(EXIT_FAILURE);
}
readtreefromfile(fin, root);
fin.close();
inordertrave(root);
std::cout << std::endl;
erasetree(root);
return 0;
}
void addnode(TreeNode*& node, int data, int flag)
{
TreeNode* p = new TreeNode;
p->data = data;
p->parent = node;
p->left = p->right = NULL;
switch (flag)
{
case 1:
node->left = p;
break;
case 2:
node->right = p;
break;
}
}
void addroot(TreeNode*& node, int data) //插入根节点，如果已经存在，直接返回
{
if (node == NULL)
{
node = new TreeNode;
node->data = data;
node->parent = node->left = node->right = NULL;
}
}
void erasetree(TreeNode*& node) //删除树
{
if (node == NULL)
return;
erasetree(node->left);
erasetree(node->right);
TreeNode* p = node->parent;
if (p != NULL)
{
if (p->left == node)
p->left = NULL;
else
p->right = NULL;
}
delete node;
node = NULL;
}
void inordertrave(TreeNode* node) //中序
{
if (node == NULL)
return;
std::cout << node->data << ' ';
inordertrave(node->left);
inordertrave(node->right);
}
void preordertrave(TreeNode* node) //前序
{
if (node == NULL)
return;
preordertrave(node->left);
std::cout << node->data << ' ';
preordertrave(node->right);
}
void postordertrave(TreeNode* node) //后序
{
if (node == NULL)
return;
postordertrave(node->left);
postordertrave(node->right);
std::cout << node->data << ' ';
}
std::ofstream& writetreetofile(std::ofstream& fout, TreeNode* node) //二进制写文件
{
char ch;
int data;
if (node == NULL)
{
ch = 0; // 0xFF 空节点标志
fout.write(&ch, sizeof(char));
}
else
{
ch = 1; // 0x01 非空节点标志
fout.write(&ch, sizeof(char));
data = node->data;
fout.write((char*)&data, sizeof(int));
writetreetofile(fout, node->left);
writetreetofile(fout, node->right);
}
return fout;
}
std::ifstream& readtreefromfile(std::ifstream& fin, TreeNode*& node, int flag) //二进制读文件
{
char ch;
int data;
TreeNode* p;
fin.read(&ch, sizeof(char)); //先读标志
if (!fin.good()
[解决办法]
ch == 0x00) //文件损坏or到了文件尾or空节点
return fin;
fin.read((char*)&data, sizeof(int));
if (!fin.good())
return fin;
switch(flag)
{
case 0: //根节点
addroot(node, data);
p = node;
break;
case 1: //左子树
addleft(node, data);
p = node->left;
break;
case 2: //右子树
addright(node, data);
p = node->right;
break;
}
readtreefromfile(fin, p, 1);
readtreefromfile(fin, p, 2);
return fin;
}
