二叉樹的序列化與反序列化
請設計一個演算法來實作二叉樹的序列化與反序列化。這里不限定你的序列 / 反序列化演算法執行邏輯，你只需要保證一個二叉樹可以被序列化為一個字串并且將這個字串反序列化為原始的樹結構。
示例:
你可以將以下二叉樹：
1
/ \
2 3
/ \
4 5
序列化為 "1 2 ##3 4 ##5 ##"
現在報錯超時。不知道我下面的字串傳遞是不是可以這樣用，還是說是其他的問題？
void dfs(struct TreeNode *root, char *s);
char* serialize(struct TreeNode* root) {
if(root == NULL)
return NULL;
char *re = (char*)malloc(sizeof(char) * 5000);
dfs(root, re);
return re;
}
void dfs(struct TreeNode *root, char *s)
{
if(root == NULL)
{
strcat(s, "#");//如果是NULL，在字串后添加“#”；
return;
}
int temp = root->val;
int index = strlen(s);
while(temp)
{
s[index++] =(char)(temp % 10 + '0');//直接將數值，添加在字串后面，最后加一個空格，區別，數值哪里截至。
temp /= 10;
}
s[index++] = ' ';
s[index] = '\0';
dfs(root->left, s);
dfs(root->right, s);
}
/** Decodes your encoded data to tree. */
struct TreeNode* deserialize(char* data) {
if(data[0] == '\0')
return NULL;
if(data[0] == '#')
{
data = data + 1;//如果傳遞過來的字串第一個是"#", 則將字串地址轉換為下一個索引的位置。
return NULL;
}
struct TreeNode * root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->val = 0;
int i = 0;
for(i = 0; data[i] >= '0' && data[i] <= '9'; i++)
{
root->val *= 10;
root->val += (int)(data[i] - '0');
}
data = data + i + 1; //當前的數值，取出后，將字串的地址改為該數值以及其后空格，之后的一個地址。這里不知道這種操作是否可行？？？？？？？？？？
root->left = deserialize(data);
root->right = deserialize(data);
return root;
}
// Your functions will be called as such:
// char* data = serialize(root);
// deserialize(data);
uj5u.com熱心網友回復：
換了一種方式寫。終于過了，雖然耗時和耗記憶體比較大。/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/** Encodes a tree to a single string. */
void dfs(struct TreeNode *root, char *s);
struct TreeNode* de(char* data, int *index, int len);
char* serialize(struct TreeNode* root) {
if(root == NULL)
return NULL;
char *re = (char*)malloc(sizeof(char) * 5000);
re[0] = '\0';
dfs(root, re);
return re;
}
void dfs(struct TreeNode *root, char *s)
{
if(root == NULL)
{
strcat(s, "#");
return;
}
char *str = (char*)malloc(sizeof(char) *12);
sprintf(str, "%d ", root->val);
//itoa(root->val, str, 10); itoa函式與ANSI標準是不兼容的；
strcat(s, str);
//strcat(s, " ");
free(str);
dfs(root->left, s);
dfs(root->right, s);
}
/** Decodes your encoded data to tree. */
struct TreeNode* deserialize(char* data) {
if(data == NULL)
return NULL;
int index = 0;
int len = strlen(data);
return de(data, &index, len);
}
struct TreeNode* de(char* data, int *index, int len)
{
//int len = strlen(data);
if((*index) >= len)
return NULL;
if((*index) < len && data[*index] == '#')
{
(*index)++;
return NULL;
}
int flag = 1;
if(data[*index] == '-')
{
flag = -1;
(*index)++;
}
else if(data[*index] == '+')
{
(*index)++;
}
struct TreeNode * root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->val = 0;
while((*index) <= len && data[*index] >= '0' && data[*index] <= '9')
{
root->val *= 10;
root->val += (int)(data[(*index)] - '0');
(*index)++;
}
root->val *= flag;
(*index)++;
root->left = de(data, index, len);
root->right = de(data, index, len);
return root;
}
// Your functions will be called as such:
// char* data = serialize(root);
// deserialize(data);
uj5u.com熱心網友回復：
"你只需要保證一個二叉樹可以被序列化為一個字串并且將這個字串反序列化為原始的樹結構。"這里所說的字串，并不一定是文字字串，也可以是二進制的吧。所以你可以省略，文字到數字的轉換程序。
另外
char *str = (char*)malloc(sizeof(char) *12); // char str [12]就行了，二叉樹不會太深
uj5u.com熱心網友回復：
這就是一個二叉樹的中序遍歷程序，再遍歷的程序當中，輸出或者讀取界節點內容// 輸出
void ioOutput（TreeNode* pTree， FILE* fp ){
輸出 pTree->data;
if ( pTree -> left ) ioOutput( pTree->left， fp) ; else 輸出 #；
if （pTree->right) ioOutput(pTree->right， fp); else 輸出#
}
// 讀入
TreeNode * ioInput（FILE * fp) {
ElementType data = 讀入資料
if ( data == '#' ) return NULL;
TreeNode * pTree = (TreeNode*) malloc(TreeNode);
pTree->data = data;
pTree->left = ioInput(fp);
pTree->right = ioInput(fp);
return pTree;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/131833.html
標籤：C語言
上一篇：命令列引數