How do you guys print out a binary tree?

[Anthony Liu]

There are many ways to represent a binary tree on an
ascii screen.

1
/ \
2 3
/ \ / \
4 5 6 7

or

4---2-----------1
| |
5 6----- 3
|
7

Suppose I have a function that takes a matrix like
this one:

1 2 3 4 5
0 7 8 9 10
0 0 13 14 15
0 0 0 19 20
0 0 0 0 25

Look at the triangle represented by the non-zero
integers. This triangle is a binary tree if we take 5
as the root and walk down on both sides.

How do I print out this triangle on an ascii console
and visually present it as a binary tree.

Any suggestions?

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

[bayerj]

Hi,

1 2 3 4 5
0 7 8 9 10
0 0 13 14 15
0 0 0 19 20
0 0 0 0 25
Look at the triangle represented by the non-zero
integers. This triangle is a binary tree if we take 5
as the root and walk down on both sides.

Are you sure? Is 9 a child of 4 or 10? A binary tree can have up to
2^n - 1 nodes. A matrix can have up to n^2 values, in your case of a
half-empty matrix about (n-1)^2.

[bayerj]

A half-empty matrix will of course have (n+1)* n * 1/2 elements.

[bayerj]

The problem is that you cannot represent a matrix as a tree, due to the
fact that there are more than one tree for a matrix.

First you have to decide, how you will turn the matrix into a tree.

[Dave Hansen]

On Tue, 18 Apr 2006 08:17:22 -0700 (PDT) in comp.lang.python, Anthony
Liu <an***********@yahoo.com> wrote:

--- bayerj <ba****@in.tum.de> wrote:

Hi,

> 1 2 3 4 5
> 0 7 8 9 10
> 0 0 13 14 15
> 0 0 0 19 20
> 0 0 0 0 25
> Look at the triangle represented by the non-zero
> integers. This triangle is a binary tree if we

take 5

> as the root and walk down on both sides.

Are you sure? Is 9 a child of 4 or 10? A binary
tree can have up to
2^n - 1 nodes. A matrix can have up to n^2 values,
in your case of a
half-empty matrix about (n-1)^2.

Thanks. I am not concerned about the shape of binary
tree. So, let's forget about binary tree.

Given a triangle like that, it does not matter which
is whose children. How do we nicely present it as
tree in an ascii console?

Something like the following might work. Quick 2-minute script.
Probably needs tweaking to be generally useful

import sys
def print_tri(t):
n = len(t)
cell = 0
for line in t:
tw = max(map(lambda x:len(str(x)), line))
if tw > cell:
cell = tw
for p in range(n,0,-1):
sys.stdout.write("%*s"%(((cell+1)/2)*(2*p),""))
x = 0
y = p-1
while y<n:
s = str(t[x][y])
b = (cell-len(s))/2
sys.stdout.write("%*s%*s"%(b,s,cell-b,""))
x += 1
y += 1
sys.stdout.write("\n")

Regards,
-=Dave

--
Change is inevitable, progress is not.