Python implement a preorder method of a binary tree

Question

Why can't this python program run correctly. I would like to build a binary tree and then traverse it in pre-order. When I call the PreOrder method, it returns nothing.

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.left = left
        self.right = right
        self.data = data

class BTree:
    def __init__(self, root):
        self.root = root

    def CreateTree(self, root):
        self.root.data = raw_input("Enter data,'*' means empty: ")
        if self.root.data == '*':
            return
        self.root.left = Node()
        self.root.right = Node()
        self.CreateTree(self.root.left)
        self.CreateTree(self.root.right)

    def PreOrder(self, root):
        if self.root != None:
            if self.root.data != '*':
                print self.root.data,
                PreOrder(self, self.root.left)
                PreOrder(self, self.root.right)

if __name__ == '__main__':
    t = Node()
    bt = BTree(t)
    bt.CreateTree(t)
    bt.PreOrder(t)

Roshan Mathews · Accepted Answer · 2011-08-14 09:25:38Z

3

PreOrder is a method of the class BTree, you might want to change the recursive calls, like so:

def PreOrder(self):
    if self.root != None:
        if self.root.data != '*':
            print self.root.data,
            self.root.left.PreOrder()
            self.root.right.PreOrder()

You also don't need to pass root to CreateTree, if you are only using self.root which you saved in __init__

answered Aug 14, 2011 at 9:25

Roshan Mathews

5,9142 gold badges28 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

wks · Accepted Answer · 2011-08-14 10:22:29Z

0

Your CreateTree method does not mention the parameter root at all. This method always operate on self.root.

Something like this may work:

def CreateTree(self, current_node):
    current_node.data = raw_input("Enter data,'*' means empty: ")
    if current_node.data == '*':
        return
    current_node.left = Node()
    current_node.right = Node()
    self.CreateTree(current_node.left)
    self.CreateTree(current_node.right)

answered Aug 14, 2011 at 10:22

wks

1,1481 gold badge7 silver badges12 bronze badges

Comments

Pratik Deoghare · Accepted Answer · 2011-08-14 11:03:00Z

Because you are setting self.root.data = '*' in the CreateTree function by doing this self.root.data = raw_input("Enter data,'*' means empty: "). And to terminate the input prompt you have to enter '*' in the end. So last value that your self.root.data has is '*'.

Try this

    print self.root.data
    root.data = raw_input("Enter data,'*' means empty: ")
    print self.root.data
    if root.data == '*':
        return

and this

    def CreateTree(self,root):
        print self.root.data
        root.data = raw_input("Enter data,'*' means empty: ")
        print self.root.data
        if root.data == '*':
            return
        self.root.left = Node()
        self.root.right = Node()
        self.CreateTree(self.root.left)
        self.CreateTree(self.root.right)

    def PreOrder(self, root):
        print root
        print self.root
        print self.root.data
        if self.root != None:
            if self.root.data != '*':
                print self.root.data,
                PreOrder(self, self.root.left)
                PreOrder(self, self.root.right)
            else:
                print 'what the hell'

if __name__ == '__main__':
    t = Node(10,Node(),Node())
    print t.data
    bt = BTree(t)
    bt.CreateTree(t)
    bt.PreOrder(t)

to know where it went wrong.

Bill the Lizard · Accepted Answer · 2012-08-04 02:04:54Z

0

I you look at your CreateTree method, you will see, that you never use root and therefore self.root.data will always be *. If you fix that, your code has more problems, all related to self and scopes. You might want to check this.

edited Aug 4, 2012 at 2:04

Bill the Lizard

407k213 gold badges579 silver badges892 bronze badges

answered Aug 14, 2011 at 9:34

xubuntix

2,33318 silver badges20 bronze badges

Collectives™ on Stack Overflow

Python implement a preorder method of a binary tree

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related