Drawing trees without any constraint on degrees
algorithm, draw, tree
Solution
Quoting from the article "Drawing Presentable Trees" by Bill Mill, the core steps of an m-ary tree drawing algorithm are the following:
- Do a post-order traversal of the tree
- If the node is a leaf, give it an x coordinate of 0
- Otherwise, for each of its children, place the child as close to its left sibling as possible
- Place the parent node halfway between its leftmost and rightmost children
The above steps have one problem though, the sub-trees to the left cause the rest of the tree to be pushed to the right and leads to imbalance. The article implements the following principle to solve the problem:
Principle 6: The child nodes of a parent node should be evenly spaced.
There's a link to a Python implementation of these steps given in the article.
Problem
I'm working on visualization of my distributed algorithm which solves problems on trees. I have to draw a rooted tree which is given as an input. Currently, I know how to handle the case if every node has at most 2 children. In this situation, for every node `v`, I draw `v` as a circle with coordinates `(x(v), x(y))`, where: ``` x(v) := index of v in the inorder traversal y(v) := distance from v to the root ``` That works fine (of course the width of the tree is quite big, but that doesn't bother me much) but only for at most binary trees. Please, suggest what algorithm I should use for general trees. The only requirement that I have is that the drawing has to be planar. EDIT: ``` the simpler algorithm is to implement, the better ```