Member Avatar for RehabReda

hi all
hope that all of u are fine : )
well i want to draw a tree not a binary tree but i can't find an efficient algorithm
to draw it
the big problem when the tree is unbalanced

Thanks ur help will be greatly appreciated : )

Edited by RehabReda because: n/a
  • 3 Contributors
  • 3 Replies
  • 194 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by swinefish

Dani AI

Generated

For drawing general (non-binary) trees — especially when they are highly unbalanced — a "tidy" layout is usually the most reliable choice. The tidy-family (Reingold–Tilford and Buchheim’s linear-time refinement) computes compact x positions by measuring subtree contours and resolving overlaps so parents stay centered over their children. Radial layouts or force-directed layouts are alternatives when horizontal overflow or extreme skew are a problem.

A compact two-pass approach (high level) that follows the tidy idea:

# first pass: post-order compute prelim and mods
function firstWalk(node):
    if node.children.empty():
        node.prelim = 0
    else:
        for child in node.children:
            firstWalk(child)
        node.prelim = (node.children.first.prelim + node.children.last.prelim) / 2
        apportion(node)   # push overlapping sibling subtrees apart, update node.mod

# second pass: finalize coordinates
function secondWalk(node, modSum=0, depth=0):
    node.x = node.prelim + modSum
    node.y = depth * levelHeight
    for child in node.children:
        secondWalk(child, modSum + node.mod, depth + 1)

Practical tips and pitfalls:

  • Compute subtree contours and enforce a configurable minimum horizontal separation to avoid overlaps.
  • For very deep chains use iterative traversal or tail-recursive techniques to avoid stack overflow.
  • If an unbalanced tree still produces extreme width, consider radial layout, compressing single-child chains, or interactive strategies (collapse/expand, level-of-detail, panning+zoom).
  • Debug by drawing left/right contours, printing prelim and mod values, or visualizing shifts applied during apportion.

This complements ’s simple traversal idea by adding automatic conflict resolution and scaling behavior, and aligns with ’s point that concrete examples/small test trees make bugs reproducible.

Recommended Answers

All 3 Replies

Member Avatar for griswolf

First, you should show some effort. The best form of effort to show is some of your own code, best if it actually works to do something (maybe not the right thing); or if you cannot get it to compile then show the code and the errors you get from the compiler/interpreter. Be sure to use the code button to place CODE tags around your code.

If you are really just talking about an algorithm that is not tied to a particular programming language, then please be more specific: "the big problem" is not a useful description of what goes wrong. Do you expect that recursion will fail? Does the graphic overflow the bounds of the screen? Are you unable to decide which direction to begin laying out subtrees? These specific details are needed to allow us to understand.

Edited by happygeek because: fixed formatting
Member Avatar for swinefish

A simple method for drawing binary trees can be generalised to non-binary trees. Okay, so for binary trees, do an inorder traversal of the tree, and draw each node as you visit it. Each node is placed at (x, y) as follows: how many nodes were visited before this one, and y is the depth (or height, you choose) of the node.
To generalise it to non binary trees, instead of visiting the left child, then the node, then the right child, split the children into 2 halves. Visit the first half of the children, then the node itself, then the second half.
I can't really give code at the moment, but I hope I've explained myself clearly enough.

Keep well
M

Member Avatar for swinefish

Glad to help :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.