在文件中表示二進制樹

什麼是參與在一個文件中表示二進制樹不同的策略，使樹形結構可以很容易地重現？我使用C.在文件中表示二進制樹

來源

2012-01-10 PaulDaviesC

我覺得你的問題太含糊。在Java中，我猜你可以使用'Serializable'。 – insumity 2012-01-10 10:41:36

問題很模糊，你能更精確嗎！ – Pratik 2012-01-10 10:42:04

我將使用c程序創建一個二叉樹，並且我需要將樹結構存儲到一個文件中，以便通過從文件中讀取，我可以再次重新創建樹。 – PaulDaviesC 2012-01-10 10:45:58

存儲在文件中的樹的序和序遍歷。任何二叉樹都可以按照順序和前序遍歷來重構[1]。

[1] http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

來源

2013-01-14 16:49:18 user1054825

-1

做一箇中序遍歷，並將節點的值寫入用新行定界的文件。如果節點是葉子，則在葉子值之後存儲特殊字符（例如＃）。

當您讀取文件時，直到您沒有'＃'插入值，然後下降到左邊。如果你得到'＃'，直到右邊沒有元素，然後下降到右邊。這是遞歸的。

來源

2012-01-10 11:04:18 WebMonster

對不起，它不會保留你的原始樹。它將只保留具有相同數字的正確二進制搜索樹。 – WebMonster 2012-01-10 11:10:19

下降到左邊你的意思是，將一個孩子附在左邊，對嗎？那麼你提升的意思是什麼？ – PaulDaviesC 2012-01-10 11:19:53

如果一個節點沒有合適的孩子，這是行不通的。你需要爲這種情況加額外的＃。 – 2012-01-10 15:22:36

這裏有一個簡單的方式，假設你有這樣的：

struct bst { 
    int val; 
    struct bst *left; // NULL when no node 
    struct bst *right; 
}

讓另一個結構如下所示：

struct bst_serial { 
    int val; 
    int left; // NULL when no node 
    int right; 
}

然後的malloc bst_serial秒的數組，它是爲你的樹一樣大：

struct bst_serial *serial_bst = malloc(sizeof(struct bst_serial) * tree_size);

現在，做樹的遍歷像這樣（未經）：

int current_pos = 0; 

int convert_node(bst *root) { 
    int this_pos = current_pos; 
    current_pos++;   

    serial_bst[this_pos].val = root->val; 
    if(root->left != NULL) { 
     serial_bst[this_pos].left = convert_node(root->left); 
    } else { 
     serial_bst[this_pos].left = -1; 
    } 

    if(root->right != NULL) {  
     serial_bst[this_pos].right = convert_node(root->right); 
    } else { 
     serial_bst[this_pos].right = -1; 
    } 
    return this_pos; 
}

您現在可以將write()數組輸出到磁盤。如果你編寫函數遍歷bst_serial類型的樹，那麼你甚至不需要反序列化它 - 你可以只用mmap()它。對於額外的點，首先不要使用指針樹 - 在創建二叉樹時創建並增長bst_serial數組。然後，您的代碼不需要關心它是從磁盤還是剛剛創建的樹處理樹。

來源

2012-01-10 11:31:02

爲了能夠構建精確的樹，您將需要至少2遍樹的遍歷。因爲在給定的遍歷中可能有多個唯一的樹。

例如，您可以將二叉樹的inorder和preorder遍歷存儲到您的文本文件中，並在重新創建樹時從下面的鏈接開始執行。

http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

來源

2013-01-08 11:46:35 C0deBr8kr

在文件中表示二進制樹

回答

相關問題