Реализация бинарного дерева поиска


Мне нужен анализ кода с точки зрения правильности, логичности, стиль, эффективность, читаемость кода, и "весть" - Несс.

class Node(object):
    def __init__(self, data=None, leftchild=None, rightchild=None):
        self.data = data
        self.leftchild = leftchild
        self.rightchild = rightchild

class BinarySearchTree(object):
    def __init__(self, root=None):
        self.root = root

    def get_root(self):
        '''Return the root node.'''
        return self.root

    def insert(self, item):
        '''Insert an element into the bst.'''
        if self.root is None:
            self.root = Node(item)
        else:
            while self.root is not None:

                if item < self.root:
                    if node.leftchild is not None:
                        node.leftchild.insert(item)
                    else:
                        node.leftchild = Node(item)
                else:
                    if item > self.root:
                        if node.rightchild is not None:
                            node.rightchild.insert(item)
                        else:
                            node.rightchild = Node(item)                



    def remove(self, node, item):
        """Remove an element from bst."""
        if node is None:
            return node
        if item < node.data:
            self.remove(node.leftchild, item)
        elif item > node.data:
            self.remove(node.rightchild, item)
        else:
            if node.leftchild is None:
                tmp = node.rightchild
                node = None
                return tmp

            elif node.rightchild is None:
                tmp = node.leftchild
                node = None
                return tmp

            else:
                tmp = self.get_min(node.rightchild)
                node.data = tmp
                node.rightchild = self.remove(node.rightchild, tmp)
        return node

#The procedure begins its search at the root and traces a simple path 
#downward in
#the tree. For each node it encounters, it compares the item with node.
#If the two items are equal, the search terminates. If the item is smaller,
#the search continues in the left subtree of the node, since the binary-searchtree
#property implies that iem could not be stored in the right subtree.
#And Vice-Versa.

    def recursive_search(self, node, item):
        '''Recursively search an element.'''
        if node == None or node.data == item:
            return node
        else:
            if item < node.data:
                return self.recursive_search(node.leftchild, item)
            else:
                return self.recursive_search(node.rightchild, item)

#On most computers, the iterative version is more efficient
    def iterative_search(self, node, item):
        '''Iteratively search an element.'''
        while node != None and item != node.data:
            if item < node.data:
                node = node.leftchild
            else:
                node = node.rightchild
        return node

#We can always find an element in a binary search tree whose key is a 
#minimum by
#following left child pointers from the root until we encounter a NIL
    def get_min(self, node):
        '''Get the minimum value.'''
        while node.leftchild != None:
            node = node.leftchild
        return node

    def get_max(self, node):
        '''Get the maximum value.'''
        while node.rightchild != None:
            node = node.rightchild
        return node

#We break the code for TREE-SUCCESSOR into two cases. If the right subtree
#of the tree is nonempty, then the successor of tree is just the leftmost
#node in tree'sright subtree.
#On the other hand, if the right subtree of the tree is empty then it means
#we will have to look for the largest node in the left subtree.
    """Successor and predecessor"""
    def successor(self, node):
        if node.rightchild != None:
            return get_min(node.rightchild)
        else:
            return get_max(node.lefchild)

    def size(self, node):
        '''Fetch the number of items in the bst.'''
        if node is None:
            return 0
        else:
            return 1 + self.size(node.leftchild) +self.size(node.rightchild)


    def inorder(self, node):
        '''Inorder traversal'''
        if node:
            self.inorder(node.leftchild)
            print (node.data)
            self.inorder(node.rightchild)

    def preorder(self, node):
        '''Pre-order Traversal.'''
        if node:
            print (node.data)
            self.preorder(node.leftchild)
            self.preorder(node.rightchild)

    def postorder(self, node):
        '''Post-order Traversal.'''
        if node:
            self.postorder(node.leftchild)
            self.postorder(node.rightchild)
            print (node.data)

    def printLevelOrder(root):
        #Base Case
        if root is None:
            return

        # Create an empty queue for level order traversal
        queue = []

        # Enqueue Root and initialize height
        queue.append(root)

        while(len(queue) > 0):
                    # Print front of queue and remove it from queue
            print( queue[0].data)
            node = queue.pop(0)

                    #Enqueue left child
            if node.left is not None:
                queue.append(node.left)

                    # Enqueue right child
            if node.right is not None:
                queue.append(node.right)


896
4
задан 1 апреля 2018 в 11:04 Источник Поделиться
Комментарии