470,636 Members | 1,555 Online

# How do you guys print out a binary tree?

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
Apr 18 '06 #1
4 3863 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

Apr 18 '06 #2
A half-empty matrix will of course have (n+1)* n * 1/2 elements.

Apr 18 '06 #3
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.

Apr 19 '06 #4
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,

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.
Apr 19 '06 #5

### This discussion thread is closed

Replies have been disabled for this discussion.