CODEWITHSUNDEEP
algorithmtreedraw
pkacprzak
pkacprzak

Reputation: 5629

Drawing trees without any constraint on degrees

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

Upvotes: 4

Views: 247

Answers (2)

rrufai
rrufai

Reputation: 1495

Quoting from the article "Drawing Presentable Trees" by Bill Mill, the core steps of an m-ary tree drawing algorithm are the following:

  1. Do a post-order traversal of the tree
  2. If the node is a leaf, give it an x coordinate of 0
  3. Otherwise, for each of its children, place the child as close to its left sibling as possible
  4. 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.

Upvotes: 3

andrew cooke
andrew cooke

Reputation: 46882

This is a fairly well-known paper (as in, I managed to remember it) on drawing trees of any degree.

Much simpler, an old blog post of mine that prints a tree in ASCII. You could adapt that approach if you want something quick and dirty.

Upvotes: 3

Related Questions