百度Intern面試題之二叉樹的網絡傳輸及恢複--二叉樹的檔案存儲和讀取

這不是我的面試題，是一個同學在百度的面試題。

  要求将一顆二叉樹通過網絡傳輸到給另一個用戶端，并且在該用戶端恢複為原始二叉樹。

  這道題目可以了解為如何将一顆二叉樹存儲到檔案中，并且讀取後正确恢複。

  以這樣的一棵二叉樹為例：

  我想到了三種解決方法：

  1. 二叉樹補全法，将這課二叉樹補全，變成一顆完全二叉樹，再使用數組進行存儲，寫入檔案中。這樣做需要在節點中增加一個屬性，标記是否為補全的節點。

  這種方法不太合理，因為使用了補全操作，對于一顆很不規則的二叉樹，将會占用非常大的存儲空間，并且修改了二叉樹的屬性。

  2. 遊标實作法。定義一個新的結構體，其中的left和right指針修改為結構體在數組中的位置。

  就像下面這樣，數組的第一個位置表示NULL位置，剩餘的存放節點，left和right分别指向左右子節點所在數組索引。這是前序周遊遞歸調用得到的數組。

  3. 二叉樹位置描述實作。同2類似，不過這裡沒有左右子節點的指針，而是用一個整形來描述目前節點在一顆完全二叉樹中的位置。顯然，在上圖這樣的二叉樹中，節點1的位置為1,節點2的位置為2，節點3的位置為3，節點4的位置為4，節點5的位置為6，依次類推。。。

  依次，可以定義一個新的結構體描述節點資訊，用于存儲。

[cpp]  view plain copy

1. typedef struct BTreeNodeFile {  
2.     Element e; //節點值  
3.     Position p; //節點在完全二叉樹中的位置  
4. } BTreeNodeFile;  

  于是可以前序周遊遞歸調用，得到這樣的一個數組。

  恢複的時候，查找左右子節點，隻需要查找p值2倍于自身以及2倍+1于自身的節點。

  下面就是對與方法3的C++源碼。

1. /* 
2.  * tree.h 
3.  * 
4.  *  Created on: 2011-3-31 
5.  *      Author: boyce 
6.  */  
7. #ifndef TREE_H_  
8. #define TREE_H_  
9. typedef int Element;  
10. typedef struct BTreeNode{  
11.     Element e;  
12.     BTreeNode *left;  
13.     BTreeNode *right;  
14. }BTreeNode;  
15. typedef struct BTree{  
16.     BTreeNode *root;  
17.     unsigned int count;  
18. }BTree;  
19. typedef BTreeNode* BTreeNodePtr;  
20. typedef BTree* BTreePtr;  
21. #endif /* TREE_H_ */  

2.  * main.cpp 
7. #include <iostream>  
8. #include <map>  
9. #include <stdio.h>  
10. #include <string.h>  
11. #include "tree.h"  
12. using namespace std;  
13. typedef int Position;  
18. typedef map<int, BTreeNodePtr> NodeMap;  
19. const char fileName[] = "btree.dat";  
20. FILE *filePtr;  
21. void writeNode(const BTreeNodePtr btn, Position p) {  
22.     if (!btn) {  
23.         return;  
24.     }  
25.     BTreeNodeFile node;  
26.     node.e = btn->e;  
27.     node.p = p;  
28.     //寫入目前節點  
29.     fwrite(&node, sizeof(node), 1, filePtr);  
30.     //寫入左子樹  
31.     writeNode(btn->left, 2 * p);  
32.     //寫入右子樹  
33.     writeNode(btn->right, 2 * p + 1);  
34. }  
35. void writeBTree(const BTreePtr bt) {  
36.     filePtr = fopen(fileName, "w");  
37.     fwrite(&bt->count, sizeof(bt->count), (size_t) 1, filePtr); //寫入節點個數  
38.     writeNode(bt->root, 1); //寫入節點  
39.     fclose(filePtr);  
41. BTreePtr readBTree() {  
42.     BTreePtr bt = new BTree;  
43.     NodeMap mapNode;  
44.     BTreeNodeFile btnf;  
45.     BTreeNode *btn;  
46.     filePtr = fopen(fileName, "r");  
47.     fread(&(bt->count), sizeof(bt->count), 1, filePtr); //讀入結點個數  
48.     while (fread(&btnf, sizeof(btnf), (size_t) 1, filePtr) > 0) {  
49.         btn = new BTreeNode;  
50.         btn->e = btnf.e;  
51.         mapNode.insert(NodeMap::value_type(btnf.p, btn));  
53.     NodeMap::iterator iter;  
54.     NodeMap::iterator iter_t;  
55.     for (iter = mapNode.begin(); iter != mapNode.end(); iter++) {  
56.         iter_t = mapNode.find(2 * iter->first);  
57.         if (iter_t != mapNode.end()) { //找到左兒子  
58.             iter->second->left = iter_t->second;  
59.         } else {    //未找到左兒子  
60.             iter->second->left = NULL;  
61.         }  
62.         iter_t = mapNode.find(2 * iter->first + 1);  
63.         if (iter_t != mapNode.end()) { //找到右兒子  
64.             iter->second->right = iter_t->second;  
65.         } else {    //未找到右兒子  
66.             iter->second->right = NULL;  
69.     iter_t = mapNode.find(1); //找root節點  
70.     if (iter_t != mapNode.end()) {  
71.         bt->root = iter_t->second;  
74.     return bt;  
76. BTreePtr buildBTree() {  
78.     BTreeNodePtr btn = new BTreeNode[9];  
79.     for (int i = 0; i < 9; i++) {  
80.         memset(&btn[i], 0, sizeof(BTreeNode));  
81.         btn[i].e = i;  
83.     btn[0].left = &btn[1];  
84.     btn[1].left = &btn[3];  
85.     btn[2].left = &btn[4];  
86.     btn[5].left = &btn[7];  
87.     btn[0].right = &btn[2];  
88.     btn[2].right = &btn[5];  
89.     btn[4].right = &btn[6];  
90.     btn[5].right = &btn[8];  
91.     bt->root = &btn[0];  
92.     bt->count = 9;  
95. void printSubBTree(BTreeNodePtr btn, int lvl) {  
96.     int i;  
97.     if (!btn)  
99.     for (i = 0; i < lvl; i++)  
100.         printf("  ");  
101.     printf("%d/n", btn->e + 1);  
102.     printSubBTree(btn->left, lvl + 1);  
103.     printSubBTree(btn->right, lvl + 1);  
105. void printBTree(BTreePtr bt) {  
106.     printSubBTree(bt->root, 0);  
108. int main() {  
109.     BTreePtr bt = buildBTree();  
110.     printBTree(bt);  
111.     writeBTree(bt);  
112.     bt = readBTree();  
114.     return 0;