How do you guys print out a binary tree?

Discussion in 'Python' started by Anthony Liu, Apr 18, 2006.

  1. Anthony Liu

    Anthony Liu Guest

    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
     
    Anthony Liu, Apr 18, 2006
    #1
    1. Advertisements

  2. Anthony Liu

    bayerj Guest

    Hi,
    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, Apr 18, 2006
    #2
    1. Advertisements

  3. Anthony Liu

    bayerj Guest

    A half-empty matrix will of course have (n+1)* n * 1/2 elements.
     
    bayerj, Apr 18, 2006
    #3
  4. Anthony Liu

    Dave Hansen Guest

    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
     
    Dave Hansen, Apr 18, 2006
    #4
  5. Anthony Liu

    bayerj Guest

    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.
     
    bayerj, Apr 19, 2006
    #5
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.