Implementing printing of BST in Python - problem with refactoring parameters

Question

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())

score 0 · Accepted Answer · answered May 14 '21 at 19:41

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 !

thank you very much, I appreciate so much! – sunny May 15 '21 at 08:50 — sunny, May 15 '21 at 08:50

Implementing printing of BST in Python - problem with refactoring parameters

1 Answers1

Linked