How to create a binary tree from a common tree?

Question

I need to solve the following constructor for the BinaryTree class in java:

BinaryTree(GeneralTree<T> aTree) 

This method should create a BinaryTree (bt) from a shared tree (gt) as follows:

Each vertex from gt will be represented as a leaf in bt .

• If gt is a leaf, then bt will be a leaf with the same value as gt
• If gt is not a leaf, then bt will be built as an empty root, left subTree (lt) and right subTree (lr). Lt is a string binary tree created from the oldest gt subtree (the leftmost subtree), and lr is a string binary tree created from gt without its left subtree.

The frist part is pretty trivial, but the second gives me some problem. I got this far:

 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); } } 

Is it correct? If not, can you come up with a better way to solve this problem? This solution, for example, gives me a bunch of nodes without any data whatsoever, I don’t know if this is the problem of the problem itself or mine.

Thanks!

Answer 1

The problem is that most trees cannot be reduced to a binary tree. Reading your comment, you are fully aware of this. Take, for example, a tree with a root node with 3 children. There is no direct way to make a binary tree out of this without sacrificing connectivity. Where these empty nodes come from. The structure of the common tree is preserved with them. You can restore it, delete the empty nodes and reassemble the tree from two subtrees.

I did not debug your code. If this does what you said, it will be a good decision. Empty nodes sort the connectivity information of the shared tree. They are allowed to be there.

Answer 2

There is another, well-known way to create a binary tree from a shared tree without “connection nodes”. This method is best understood as follows:

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

Basically, this is a list of children of a common tree in the form of a linked list with the addition of each node that has a link to a linked list of its children. As you can see, this is structurally equivalent to a binary tree.

So, in pseudo-code (with extreme cases omitted for simplicity)

 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; } 

Of course, if you need a structure that you described, it would be useless, but overall this is a pretty good way to create a binary tree from a shared tree.