Как создать двоичное дерево из общего дерева?

Question

я должен решить следующий конструктор для класса BinaryTree в Java:

BinaryTree(GeneralTree<T> aTree) 

Этот метод должен создать BinaryTree (Bt) из General дерева (Гт) следующим образом:

Каждая вершина от gt будет представлена ​​в виде листа в bt.

• Если GT является листом, то Ь будет лист с тем же значением, GT
• Если GT не лист, а затем BT будет построен как пустой корень, левый поддерева (л) и правого подтипа (lr). Lt - это строковое двоичное дерево, созданное из самого старого поддерева gt (самое левое поддерево), а lr - это строковое двоичное дерево, созданное из gt без его левого поддерева.

Фристовая часть достаточно тривиальная, но вторая дает мне некоторые проблемы. Я получил это далеко:

public BinaryTree(GeneralTree<T> aTree){ 
     if (aTree.isLeaf()){ 
      root= new BinaryNode<T>(aTree.getRootData()); 
     }else{ 
      root= new BinaryNode<T>(null); // empty root 
      LinkedList<GeneralTree<T>> childs = aTree.getChilds(); // Childs of the GT are implemented as a LinkedList of SubTrees 
      child.begin(); //start iteration trough list 
      BinaryTree<T> lt = new BinaryTree<T>(childs.element(0)); // first element = left-most child 
      this.addLeftChild(lt); 
      aTree.DeleteChild(hijos.elemento(0)); 
      BinaryTree<T> lr = new BinaryTree<T>(aTree); 
      this.addRightChild(lr); 
     } 
    } 

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

Спасибо!

Answer 1

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

Я не отлаживал ваш код. Если это сделает то, что вы сказали, это будет хорошим решением. Пустые узлы сортируют информацию о связности общего дерева. Им разрешено находиться там.

Answer 2

Существует еще один широко известный способ создания двоичного дерева из общего дерева без «узлов подключения». Этот метод можно лучше понять, как это:

Node{    Node{ 
data;    data; 
first_child; => left; 
next_sibling;  right; 
}     } 

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

Так, в псевдокоде (с крайними случаями опущенными для простоты)

BinaryTree(gtree){ 
    root=BinaryNode(gtree.data,BinaryNode(gtree.children),null); 
} 

BinaryNode(List<gnode> sibs){ 
    BinaryNode(sibs.first.data,BinaryNode(sibs.first.children),BinaryTree(sibs.rest)); 
} 

BinaryNode(data,left,right){ 
    data=data; 
    left=left; 
    right=right; 
} 

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