序列化二叉樹

02-26

序列化二叉樹

請實現2個函數，分別用來序列化和反序列化二叉樹。

思路：我們通過前序遍歷序列和中序遍歷序列構造一顆二叉樹，缺點是二叉樹中不能有數值重複的節點。序列化二叉樹，對於空指針需要標記出來。

參考代碼：

root@gt:/home/git/Code# ./a.out 1,2,4,$,$,$,3,5,$,$,6,$,$,root@gt:/home/git/Code# cat serialize.c #include <stdio.h>#include <stdlib.h>typedef struct BTreeNode{ int value; struct BTreeNode* pleft; struct BTreeNode* pright;}TreeNode;void serialize(TreeNode* proot){ if(!proot) { printf("$,"); return; } printf("%d,",proot->value); serialize(proot->pleft); serialize(proot->pright);}void deSerialize(TreeNode** pproot,int* arr,int* index){ if(arr[*index] != && arr[*index] != $) { *pproot = (TreeNode*)malloc(sizeof(TreeNode)); (*pproot) -> value = arr[*index]; (*pproot) -> pleft = NULL; (*pproot) -> pright = NULL; ++(*index); deSerialize(&(*pproot) -> pleft,arr,index); ++(*index); deSerialize(&(*pproot) -> pright,arr,index); }}int main(){ int arr[] = {1,2,4,$,$,$,3,5,$,$,6,$,$,}; TreeNode* proot = NULL; int index = 0; deSerialize(&proot,arr,&index); serialize(proot); printf(" "); return 0;}