二叉樹採訪任務

Question

任務：將服務器端二叉樹轉移到客戶端。

我在面試中得到了這個任務。有沒有任何有效的方法來做到這一點？ 我自己不太瞭解這項任務。

這是我想出的，但不確定服務器到客戶端的傳輸。有任何想法嗎？

 void copyInOrder(TNode *orgTree, Tnode *& copyTree) 
    { 
     if(orgTree !=NULL){ 
      //left side 
      TNode newLeftNode = cloneNode(orgTree->left_link); 
      copyTree->left_link = newLeftNode; 
      copyInOrder(orgTree->left_link, copyTree->left_link); 

      //right side 
      TNode newRightNode = cloneNode(orgTree->right_link); 
      copyTree->right_link = newRightNode; 
      copyInOrder(orgTree->right_link, copyTree->right_link); 
     } 
    } 

Answer 1

老實說，定義「高效」將是一個好的第一步。什麼被認爲重要？網絡帶寬？涉及服務器端計算？客戶端計算涉及？

沿着同樣的路線，數據是什麼？例如，如果數據是整數並且網絡帶寬很重要，則可以從樹中構建一個int數組，並以最小開銷進行傳輸，然後將其轉換回用戶端的二叉樹。

如果服務器端負載是最重要的事情，你會走一條不同的路線。如果客戶端加載，可能又是另一個。

值得注意的是，由於這是一個面試問題，與面試官討論他們認爲重要的效率以及它如何影響解決方案可能與您提出的實際解決方案一樣重要。

Answer 2

對我來說，這個問題似乎不是關於傳輸本身，而是如何將數據打包傳輸。需要注意的重要一點是，由於您正在傳輸字節，而不是C++對象，因此在傳輸過程中無法輕鬆保留樹的結構。

因此，我建議你serialize樹，然後通過網絡發送它。您顯然需要預先確定的客戶端知道的序列化方案，以便客戶端可以從接收到的字節中重新創建樹。

Answer 3

只需展示如何將給定的二叉樹T轉換爲值的序列S就足以讓我們可以在客戶端從S重建T。一種可能的方式是使用衆所周知的事實：

我們可以從它的序獨特構造一個二叉樹和預購 遍歷。

因此，我們可以讓S是先序遍歷，然後是前序遍歷。檢查這question的答案。