Binary Tree

[kxjakkk]

I'm trying to modify this code:

class Tree:
    def __init__(self, cargo, left=None, right=None):
        self.cargo = cargo
        self.left = left
        self.right = right
    def __str__(self):
        return str(self.cargo)

def print_tree_inorder(tree):
    if tree is None:
        return
    print_tree_inorder(tree.left)
    print(tree.cargo, end=" ")
    print_tree_inorder(tree.right)

So that it adds parentheses around every operator and pair of operands. I just don't understand where I have to put the parentheses in this to make it work... Any help would be great please!

[Hiroshe]

So that it adds parentheses around every operator and pair of operands.

What do you mean by that? Is the tree used to represent an infix notation expression? Or are you referring to the 2 typos in your code?

[kxjakkk]

I'm just suppose to modify print_tree_inorder so that it puts parentheses around every operator and pair of operands.

[TrustyTony]

We do not understand as the tree has single cargo contents, nothing about expressions. You must include example data also, output you get for that and the desired result.

[kxjakkk]

The output should look like this: (1+(2*3))

[Hiroshe]

And what does the input look like? How is the input stored?

[kxjakkk]

http://openbookproject.net/thinkcs/python/english3e/trees.html

27.4

[Hiroshe]

I think you mean 27.3. 27.4 just talk's about traversal with doesn't mean much if you don't know how it's stored.

You have a tree that looks like this:

    +
  /   \
  *    -
 /\   /\
5  6 7  8

And you want to print it out in infix notation such that every operater has parens around it, ie (5 + (4*3)).

The solution is simple:
Say your at node N. Print out "(" + print_tree(N.left) + N.operator + print_tree(N.right) + ")".

[kxjakkk]

def print_tree_inorder(tree):
    if tree is None:
        return
    print_tree_inorder("(" + print_tree_inorder(tree.left) + tree.operator + print_tree_inorder(tree.right) + ")")

s = Tree("1 2 + 3 *")
print (print_tree_inorder(s))

I get an error:

File "C:\Users\Desktop\3.py", line 59, in <module>
    print (print_tree_inorder(s))
  File "C:\Users\Desktop\3.py", line 56, in print_tree_inorder
    print_tree_inorder("(" + print_tree_inorder(tree.left) + tree.operator + print_tree_inorder(tree.right) + ")")
TypeError: Can't convert 'NoneType' object to str implicitly

[Hiroshe]

Tree doesn't understand what the cargo "1 2 + 3 *" means. You need to parse it into a tree.

Right now, your tree looks like this:

"1 2 + 3 *"
/          \
None        None

Also, we're missing a lot of information. It looks like your program has atleady 59 lines of code.

PPS. The reaosn your getting the error is because "print_tree_inorder" doesn't return a value. It prints them. And your trying to add them togeather. When I wrote "+", I assumed that it was returning the string, and not printing it.

Think about how the code works before copy and pasting it without understanding it!

[kxjakkk]

I decided to mostly just start over on the coding...

class Tree:
    def __init__(self, cargo, left=None, right=None):
        self.cargo = cargo
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.cargo)

def total(tree):
    if tree is None: return 0
    return total(tree.left) + total(tree.right) + tree.cargo

def print_tree(tree):
    if tree is None: return
    print(tree.cargo)
    print_tree(tree.left)
    print_tree(tree.right)

def print_tree_postorder(tree):
    if tree is None: return
    print_tree_postorder(tree.left)
    print_tree_postorder(tree.right)
    print(tree.cargo)

def print_tree_inorder(tree):
    if tree is None: return
    print_tree_inorder(tree.left)
    print(tree.cargo)
    print_tree_inorder(tree.right)

def print_tree_indented(tree, level=0):
    if tree is None: return
    print_tree_indented(tree.right, level+1)
    print(" " * level + str(tree.cargo))
    print_tree_indented(tree.left, level+1)


def get_token(token_list, expected):
    if token_list[0] == expected:
        del token_list[0]
        return True
    return False

def get_number(token_list):
    x = token_list[0]
    if type(x) != type(0): return None
    del token_list[0]
    return Tree(x, None, None)

tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
print_tree_inorder(tree)