Print a binary tree, python, in inorder

Question

Me and my friend are doing some school work with programming in Python 3.1 and are VERY stuck. We're programming a binary tree and it's working fine except when we want to print all the nodes in inorder in a way that would create a sentence (all the words in inorder just after one another in a row). We have been looking all over the internet for clues as to how to procede and we've been working with this little thing for like two hours. Any advice/help would be awesome.

Our program/Binary tree:

class Treenode:  
    def __init__(self, it = None, le = None, ri = None):  
        self.item = it  
        self.left = le  
        self.right = ri  

class Bintree:  
    def __init__(self):  
        self.item = None  
        self.left = None  
        self.right = None  

    def put(self, it = None):
        key = Treenode(it)
        if self.item == None:
            self.item = key
            return
        p = self.item
        while True:
            if key.item < p.item:
                if p.left == None:
                    p.left = key
                    return
                else:
                    p = p.left
            elif key.item > p.item:
                if p.right == None:
                    p.right = key
                    return
                else:
                    p = p.right
            else:
                return

    def exists(self, it):
        key = it
        p = self.item
        if p == key:
            return True
        while True:
            if key < p.item:
                if p.left == None:
                    return False
                else:
                    p = p.left
            elif key > p.item:
                if p.right == None:
                    return False
                else:
                    p = p.right
            else:
                return

    def isEmpty(self):
        if self.item == None:
            return True
        else:
            return False

def printtree (Treenode):
    if Treenode.left != None:
        printtree (Treenode.left)
    print (Treenode.item)
    if Treenode.right != None:
        printtree (Treenode.right)

We get a sort of print when we run the program which looks like this: "bintree.Treenode object at 0x02774CB0", which is not what we want.

We use the tree by running this:

import bintree

tree = bintree.Bintree()
print(tree.isEmpty())    # should give True
tree.put("solen")
print(tree.isEmpty())    # should give False
tree.put("gott")
tree.put("sin")
tree.put("hela")
tree.put("ban")
tree.put("upp")
tree.put("himlarunden")
tree.put("manen")
tree.put("seglar")
tree.put("som")
tree.put("en")
tree.put("svan")
tree.put("uti")
tree.put("midnattsstuden")

print(tree.exists("visa"))     # should give False
print(tree.exists("ban"))      # should give True
tree.printtree()               # print sorted

Also, the second last row gives us "None" instead of "True", which is wierd.

Solution 1

print(tree.exists("visa")) returns None, because in the last line of exists() there's return statement without any value (which defaults to None).

Also you shouldn't name a printtree argument Treenode since it's a name of an existing class and that might lead to confusion. It should look more like:

def printtree(tree_node):
    if tree_node.left is not None:
        printtree(tree_node.left)
    print(tree_node.item)
    if tree_node.right is not None:
        printtree(tree_node.right)

Another thing is calling printtree - it's a function, not Bintree method, so I suppose you should call it printtree(tree).

Solution 2

To print a binary tree, if you are printing a leaf you just print the value; otherwise, you print the left child then the right child.

def print_tree(tree):
    if tree:
        print tree.value
        print_tree(tree.left)
        print_tree(tree.right)

Comments

[Duncan]

I think you are getting confused between when you have an instance of a Treenode and when you have an instance of a Bintree. For example some things in your program have an attribute item which is a string and some have an item which is a Treenode. Try changing the name item in Bintree to something else like node and then you might start getting meaningful errors when you try to print the item attribute on what you think is a Treenode but is actually a Bintree.

[stribika]

Well, the None instead of True seems like an easy fix. The last line of exists() should be "return True".

[Duncan]

I think it may be a method but the indentation was messed up when the code was pasted. If true that means the misleadingly named parameter Treenode or as you put it tree_node ought really to be called self and is really a Bintree!