3
\$\begingroup\$

Note: I do know that Python libraries provide Binary Search Tree. This implementation has been done to practice python, and data structures and Algorithms.

This is a implemented Binary Search Tree, feel free to make any suggestions about syntax, logic, or simply anything that you think i should become aware of.

Methods:

tree_insert(i) - handles inserting values, it will refuse to accept a key that already exist.

walk_tree(type) - walks the tree from root, default is in-order
inorder_tree_walk(node)
preorder_tree_walk(node)
postorder_tree_walk(node)


Search_tree_from_root(search_type, key) - looks for key from root based on type given
tree_min() - finds max key
tree_max() - finds min key
tree_search_recursive(key) - search for key from root recursively
tree_search_iterative(key) - search for key from root iteratively

tree_successor(key)- finds successor of the key
tree_predecessor(key)- finds predecessor of the key

tree_delete(i) - handles deleting a key. Delete method, uses the transplant method to move branches around
transplant(second,first)
tree_burn() - deletes everything in tree

How to use:

from binarySearchTree import BTree


def main():
print("_____INSERT____")
my_tree = BTree()
my_list = [12, 5, 18, 2, 9, 15, 19, 17, 13]
for i in my_list:
    my_tree.tree_insert(i)
print("INSERT DONE")

print("______________TREE_INSET_TRY_Duplicate______________________")
my_tree.tree_insert(12)

print("____________GET_ROOT_KEY_____________________")
print(my_tree.get_root())
print("______________TREE_WALK______________________")
my_tree.walk_tree(3)
my_tree.walk_tree(2)
my_tree.walk_tree()

print("__________TREE_SEARCH_FROM_ROOT_______________")
my_tree.search_tree_from_root(0, 15)
my_tree.search_tree_from_root(1, 19)
my_tree.search_tree_from_root(2)
my_tree.search_tree_from_root(3)

print("_____KEY_SUCCESSOR____")
my_tree.tree_successor(12)

print("_____KEY_PREDECESSOR____")
my_tree.tree_predecessor(5)

print("______________TREE_Delete______________________")
my_tree.tree_delete(100)

print("______________TREE_Delete______________________")
my_tree.tree_delete(15)

print("______________TREE_WALK______________________")
my_tree.walk_tree()

print("______________TREE_BURN______________________")
my_tree.burn_tree()


if __name__ == "__main__":
    main()

OutPUT:

_____INSERT____
INSERT DONE
______________TREE_INSET_TRY_Duplicate______________________
12  already Exist, can not add
____________GET_ROOT_KEY_____________________
12
______________TREE_WALK______________________
_____TREE_WALK_POSTORDER____
2
9
5
13
17
15
19
18
12
_____TREE_WALK_PREORDER____
12
5
2
9
18
15
13
17
19
_____TREE_WALK_INORDER____
2
5
9
12
13
15
17
18
19
__________TREE_SEARCH_FROM_ROOT_______________
_____ITERATIVE_TREE_SEARCH____
15
_____RECURSIVE_TREE_SEARCH____
19
_____TREE_MAX____
19
_____TREE_MIN____
2
_____KEY_SUCCESSOR____
13
_____KEY_PREDECESSOR____
2
______________TREE_Delete______________________
search Done
Not Found
______________TREE_Delete______________________
search Done
Delete Done
______________TREE_WALK______________________
_____TREE_WALK_INORDER____
2
5
9
12
13
17
18
19
______________TREE_BURN______________________
19
search Done
Delete Done
18
search Done
Delete Done
17
search Done
Delete Done
13
search Done
Delete Done
12
search Done
Delete Done
9
search Done
Delete Done
5
search Done
Delete Done
2
search Done
Delete Done

Process finished with exit code 0

Classes:

# simple node class
class TreeNode:
    # constructor
    def __init__(self, data=None):
        self.value = data
        self.right_child = None
        self.left_child = None
        # only used in delete and transplant can also use predecessor and SUCCESSOR instead
        self.prev_node = None

# binary search tree class
class BTree:
    # constructor
    def __init__(self):
        self.root = TreeNode(None)
        self.count = 0

    # insert method
    def tree_insert(self, value):
        # make new node
        new_node = TreeNode(value)
        # pointer that walks the tree to find the spot
        tracer = self.root
        # follow the pointer that is walking the tree to find a spot, always one step behind
        tracer_trailer = None
        while tracer is not None:
            tracer_trailer = tracer
            if tracer.value is None:
                break
            else:
                if new_node.value < tracer.value:
                    tracer = tracer.left_child
                elif new_node.value == tracer.value:
                    print(value, " already Exist, can not add")
                    break
                else:
                    tracer = tracer.right_child
                self.count += 1
        # Set Pointers that cause key to be inserted
        if tracer_trailer.value is None:
            self.root = new_node
        elif new_node.value == tracer_trailer.value:
            return False
        elif new_node.value < tracer_trailer.value:
            new_node.prev_node = tracer_trailer
            tracer_trailer.left_child = new_node
        else:
            new_node.prev_node = tracer_trailer
            tracer_trailer.right_child = new_node

# delete method, uses the transplant method to move branches around
    def tree_delete(self, key):
        root = self.root
        if root is not None:
            node = self.tree_search_iterative(root, key)
            print("search Done")
            if node is not None:
                # removing node has no left child
                if node.left_child is None:
                    self.transplant(node, node.right_child)
                # removing node has no right child
                elif node.right_child is None:
                    self.transplant(node, node.left_child)
                # removing node has two children
                else:
                    # find successor in that side
                    temp = self.tree_min(node.right_child)
                    if temp.prev_node != node:
                        self.transplant(temp, temp.right_child)
                        temp.right_child = node.right_child
                        temp.right_child.prev_node = temp

                    self.transplant(node, temp)
                    temp.left_child = node.left_child
                    temp.left_child.prev_node = temp
                print("Delete Done")
                self.count -= 1
            else:
                print("Not Found")

    # used in delete; handles moving nodes and transplanting nodes
    def transplant(self, first_node, second_node):
        if first_node.prev_node is None:
            self.root = second_node
        elif first_node == first_node.prev_node.left_child:
            first_node.prev_node.left_child = second_node
        else:
            first_node.prev_node.right_child = second_node
        if second_node is not None:
            second_node.prev_node = first_node.prev_node


# --------in-order, pre-order, post-order tree walks-------------
    def inorder_tree_walk(self, node):
        if node is not None:
            self.inorder_tree_walk(node.left_child)
            print(node.value)
            self.inorder_tree_walk(node.right_child)

    def preorder_tree_walk(self, node):
        if node is not None:
            print(node.value)
            self.preorder_tree_walk(node.left_child)
            self.preorder_tree_walk(node.right_child)

    def postorder_tree_walk(self, node):
        if node is not None:
            self.postorder_tree_walk(node.left_child)
            self.postorder_tree_walk(node.right_child)
            print(node.value)

    # accessor to three different tree walks, will do it from root, default is in-order
    def walk_tree(self, walk_type=None):
        root = self.root
        if walk_type == 3:
            print("_____TREE_WALK_POSTORDER____")
            self.postorder_tree_walk(root)
        elif walk_type == 2:
            print("_____TREE_WALK_PREORDER____")
            self.preorder_tree_walk(root)
        else:
            print("_____TREE_WALK_INORDER____")
            self.inorder_tree_walk(root)

# --------recursive, iterative, max, min, search methods-------------
    def tree_search_recursive(self, node, key):
        if node is not None:
            if node is not None:
                if key == node.value:
                    return key
                if key < node.value:
                    return self.tree_search_recursive(node.left_child, key)
                else:
                    return self.tree_search_recursive(node.right_child, key)
        else:
            print("NOT FOUND")

    def tree_search_iterative(self, node, key):
        if key is not None:
            while True:
                if node is None:
                    return None
                if key == node.value:
                    break
                if key < node.value:
                    node = node.left_child
                else:
                    node = node.right_child
            return node
        else:
            print("NOT FOUND")

    def tree_max(self, node):
        if node is not None:
            while node.right_child is not None:
                node = node.right_child
            return node
        else:
            print("Tree is empty")

    def tree_min(self, node):
        if node is not None:
            while node.left_child is not None:
                node = node.left_child
            return node
        else:
            print("Tree is empty")

    # search for a key using iterative, recursive, or search for max and min from root, default is Iterative
    def search_tree_from_root(self, search_type=None, key=None):
        root = self.root
        if root is not None:
            if search_type == 3:
                print("_____TREE_MIN____")
                found_node = self.tree_min(root)
                if found_node is not None:
                    print(found_node.value)
                else:
                    print("Not Found")

            elif search_type == 2:
                print("_____TREE_MAX____")
                found_node = self.tree_max(root)
                if found_node is not None:
                    print(found_node.value)
                else:
                    print("Not Found")
            elif search_type == 1:
                print("_____RECURSIVE_TREE_SEARCH____")
                found_node = self.tree_search_recursive(root, key)
                if found_node is not None:
                    print(found_node)
                else:
                    print("Not Found")
            elif search_type == 0:
                print("_____ITERATIVE_TREE_SEARCH____")
                found_node = self.tree_search_iterative(root, key)
                if found_node is not None:
                    print(found_node.value)
                else:
                    print("Not Found")
        else:
            print("Tree is Empty")

# successor and predecessor methods
    def tree_successor(self, key):
        root = self.root
        if root is not None:
            node = self.tree_search_iterative(root, key)

            if node.right_child is not None:
                found_node = self.tree_min(node.right_child)
                if found_node is not None:
                    print(found_node.value)
                return found_node

            prev = node.prev_node

            while prev is not None and node == node.right_child:
                node = prev
                prev = prev.prev_node

            if prev is not None:
                print(prev.value)

            return prev

        else:
            print("Tree is empty")

    def tree_predecessor(self, key):
        root = self.root
        if root is not None:
            node = self.tree_search_iterative(root, key)

            if node.left_child is not None:
                found_node = self.tree_max(node.left_child)
                if found_node is not None:
                    print(found_node.value)
                return found_node

            prev = node.prev_node

            while prev is not None and node == node.left_child:
                node = prev
                prev = prev.prev_node

            if prev is not None:
                print(prev.value)

            return prev
        else:
            print("Tree is empty")

    def get_root(self):
        return self.root.value

    def __iter__(self):
        return self.walk_tree()

    def __len__(self):
        return self.count

    def burn_tree(self):
        while self.root is not None:
            highest_num = self.tree_max(self.root)
            print(highest_num.value)
            self.tree_delete(highest_num.value)
            self.count -= 1
\$\endgroup\$

2 Answers 2

5
\$\begingroup\$

Here's some general critique.

  1. Don't call it a BTree -- that's a related but significantly different data structure. Call it a MyBinaryTree.
  2. It's not necessary for the methods to all have the word "tree" in them. That just adds wordiness and doesn't help with code readability.
  3. Don't use print statements to signal errors. What if your code is used in a situation without a console, such as a batch/background process or GUI? Python has a very good exception mechanism; use it.
  4. Don't use print statements for logging progress or debug info; use the built-in logging library.
  5. Also, the "already exists" error should exit the function, not break. Throwing an exception already takes care of that.
  6. Your preorder_tree_walk and postorder_tree_walk don't work as intended, as is evident from their output. Look carefully at how you recurse.
  7. Extra comma here def search_tree_from_root(self, search_type=None, key=None,):
  8. Don't use magic numbers to implement an enumeration. Instead use a real enumeration. You'll have to move up to Python 3.4 or later -- which you should do anyway.
\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your help, i will correct the mistakes. for some reason i call in order inside both post-order and pre-order, i fixed thoes. \$\endgroup\$
    – BlooB
    Commented Sep 21, 2017 at 17:48
4
\$\begingroup\$

Python 3.x provides collections.abc which includes Abstract Base Classes useful for defining classes that will emulate certain Python container behavior.

As you have written it, your tree class appears to behave like a MutableSet more than anything else - you can insert and remove items, check for membership, and iterate over all the items.

I suggest you implement the MutableSet interface. You might also try Reversible, and you can certainly include some other iterator types (pre-order, post-order) as specially-named methods.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.