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

Question

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

BinaryTree(GeneralTree<T> aTree)

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

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

• Если gt является листом, то bt будет листом с тем же значением, что и gt
• Если gt не является листом, то bt будет создан как пустой корень,левое поддерево (lt) и правое поддерево (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;
}

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