I'm new to python, I'm building a tree, this is my code:

class BinaryTree():
    def __init__(self, dado, left = None, right = None):
        self.dado = dado
        self.left = left
        self.right = right

I want to make a function to represent the binary tree, represented by nested parentheses. This function receives the root and shows, in one line, the structure of the elements. For example, the tree:

is displayed as (1 (2 () ()) (3 () (4 () ()))).

In this tree, the root of the tree is represented by the outermost parentheses, followed by the parentheses that encompass the left child (2 () ()) of the root, and then the parentheses that encompass the right child (3 () ( 4 () ) ( ))) from the root. The left node has no children ()() while the right node has a child (4()()), and this is also a leaf ()().

I tried to create the function but I couldn't leave it with the expected output... the result of my function comes out like this:

1
2
3
4

my code, trying to create a function, was this:

def show(node):
    string = []                                       
    if not node: 
        return      
    print(node.dado)
    show(node.left) 
    show(node.right)  

CodePudding user response：

You already implemented inorder traverse of your tree, which is good. You missed two things:

1. What do you want to print if node is null? -> empty brackets
2. What do you want to print before and after each step? -> brackets

So your function could look like that:

def show(node):
    if not node:
        print("()", end="")
        return
    print(f"({node.dado} ", end="")
    show(node.left)
    print(" ", end="")
    show(node.right)
    print(")", end="")

The end parameter of print prevent it to adding newline character at the end.

CodePudding user response：

Yet another variation:

def show(node):
    print(end='(')
    if node:
        print(node.dado, end=' ')
        show(node.left)
        print(end=' ')
        show(node.right)
    print(end=')')

CodePudding user response：

You should indeed use recursion for this, but your attempt is not adding any parentheses, and outputs line breaks.

For the base case -- when a node is None -- the string should be "()". When the node is not None, it is a matter of combining the recursive results of the two children with the node's own value.

Here is a function for that:

def serialize(node):
    if not node:
        return "()"
    return f"({node.dado} {serialize(node.left)} {serialize(node.right)})"

Here is how you could use it:

# Create tree that's used as example in the question
root = BinaryTree(1, BinaryTree(2), BinaryTree(3, None, BinaryTree(4)))
# Create the string for it
print(serialize(root))   # (1 (2 () ()) (3 () (4 () ())))