Интервью на бинарных деревьях

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

Честно говоря, определение "эффективный" было бы хорошим первым шагом. Что считается важным? Пропускная способность сети? Вычисления на стороне сервера участвуют? Вычисления на стороне клиента?

В том же духе, что это за данные?

Например, если данные являются целыми числами и важна пропускная способность сети, вы можете создать массив деревьев из дерева, передать его с минимальными издержками, а затем преобразовать его обратно в двоичное дерево на стороне пользователя.

Если загрузка на стороне сервера является наиболее важной вещью, вы пошли бы другим путем. Если загрузка на стороне клиента, возможно, еще одна.

Стоит отметить, что, поскольку это вопрос интервью, обсуждение с интервьюером того, что они считают важным для эффективности и как это влияет на решение, может быть столь же важным, как и фактическое решение, которое вы придумали.

Answer 2

Достаточно показать, как преобразовать данное двоичное дерево T в последовательность значений S таким образом, чтобы мы могли восстановить T из S на стороне клиента.Один из возможных способов - использовать общеизвестный факт:

Мы можем построить двоичное дерево уникально из его обходов по порядку и по порядку.

Таким образом, мы можем позволить S бытьобход по предварительному заказу с последующим обходом по предварительному заказу.Проверьте ответ на этот вопрос .

Answer 3

Мне кажется, проблема не столько в самой передаче, сколько в том, как можно упаковать данные для передачи. Важно отметить, что поскольку вы передаете байты, в отличие от объектов C ++, вы не сможете так легко сохранить структуру дерева во время передачи.

Поэтому я бы посоветовал вам сериализовать дерево, а затем отправить его по сети. Очевидно, вам потребуется заранее определенная схема сериализации, о которой клиент знает, чтобы клиент мог воссоздать дерево из полученных им байтов.