0

I've found a nice implementation of printing the BST here from BcK. I wanted to implement it into my code, but I don't really know what parameters' name I should change so it could work in my code. Could you help me with that? I guess I have to change left and right as he said, but I don't know what I should change it for. The definition I copied is print_tree, everything above is mine, so I have to change something in print_tree only


class Node:
    def __init__(self,x):
        self.key = x
        self.left = None
        self.right = None
        self.p = None

class BST:
    def __init__(self):
        self.root = None

    def BSTsearch(self,k):

        x = self.root
        while x!=None and x.key!=k:
            if k<x.key:
                x=x.left
            else:
                x=x.right
        return x

    def BSTinsert(self, z):

        x = self.root
        y = None
        while x != None:
            y=x
            if z.key<x.key:
                x=x.left
            else:
                x=x.right
        z.p=y
        if y==None:
            self.root=z
        else:
            if z.key<y.key:
                y.left=z
            else:
                y.right=z

    def bstDelete(self, z):

        if z.left == None and z.right == None:
            if z == self.root:
                self.root = None
            else:
                if z == z.p.left:
                    z.p.left = None
                else:
                    z.p.right = None
        elif z.left != None and z.right != None:
            y = self.bstMinimum(z.right)
            z.key = y.key
            self.bstDelete(y)
        else:
            if z.left != None:
                z.left.p=z.p
                if z==self.root:
                    self.root=z.left
                else:
                    if z==z.p.left:
                        z.p.left=z.left
                    else:
                        z.p.right=z.left
            else:
                z.right.p=z.p
                if z==self.root:
                    self.root=z.right
                else:
                    if z==z.p.left:
                        z.p.left=z.left
                    else:
                        z.p.right=z.left

    def bstMinimum(self, x):

        while x.left != None:
            x = x.left
        return x

    def BSTinOrder(self, x):

        if x == None: return
        self.BSTinOrder(x.left)
        print(x.key)
        self.BSTinOrder(x.right)

    def bstGetRoot(self):
        return self.root

    def print_tree(root, val="val", left="left", right="right"):
        def display(root, val=val, left=left, right=right):
            """Returns list of strings, width, height, and horizontal coordinate of the root."""
            # No child.
            if getattr(root, right) is None and getattr(root, left) is None:
                line = '%s' % getattr(root, val)
                width = len(line)
                height = 1
                middle = width // 2
                return [line], width, height, middle

            # Only left child.
            if getattr(root, right) is None:
                lines, n, p, x = display(getattr(root, left))
                s = '%s' % getattr(root, val)
                u = len(s)
                first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
                second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
                shifted_lines = [line + u * ' ' for line in lines]
                return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

            # Only right child.
            if getattr(root, left) is None:
                lines, n, p, x = display(getattr(root, right))
                s = '%s' % getattr(root, val)
                u = len(s)
                first_line = s + x * '_' + (n - x) * ' '
                second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
                shifted_lines = [u * ' ' + line for line in lines]
                return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

            # Two children.
            left, n, p, x = display(getattr(root, left))
            right, m, q, y = display(getattr(root, right))
            s = '%s' % getattr(root, val)
            u = len(s)
            first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
            second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
            if p < q:
                left += [n * ' '] * (q - p)
            elif q < p:
                right += [m * ' '] * (p - q)
            zipped_lines = zip(left, right)
            lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
            return lines, n + m + u, max(p, q) + 2, n + u // 2

        lines, *_ = display(root, val, left, right)
        for line in lines:
            print(line)





tree = BST()
tree.BSTinsert(Node(5))
tree.BSTinsert(Node(3))
tree.BSTinsert(Node(7))
tree.BSTinsert(Node(2))
tree.BSTinsert(Node(4))
tree.BSTinsert(Node(9))

#tree.BSTinOrder(tree.bstGetRoot())

tree.print_tree(tree.bstGetRoot())

1 Answer 1

0

You are almost there.

First, since you have put the print_tree under your class you should put self as the first parameter.

def print_tree(self, root, val="val", left="left", right="right"):

Second, as you can see, the default parameters for print_tree are defined according to your implementation of Node. That is, in your Node, you have defined the node value as self.key, therefore pass "key" to the val parameter.

tree.print_tree(tree.bstGetRoot(), val="key")

That's it !

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

1 Comment

thank you very much, I appreciate so much!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.