Last active
August 9, 2019 01:58
-
-
Save ankona/dd7dc099851955b230faf286eb0e5411 to your computer and use it in GitHub Desktop.
Binary Tree DFS & BFS
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from collections import deque | |
class Node: | |
def __init__(self, value, lchild=None, rchild=None): | |
self.value = value | |
self.lchild = lchild | |
self.rchild = rchild | |
class BT: | |
def __init__(self, root=None): | |
self.level = deque() | |
self.root = root | |
self.q = deque() | |
def __find(self, item, parent): | |
if not parent: | |
return False | |
if parent.value == item: | |
return True | |
if parent.value > item: | |
return self.__find(item, parent.lchild) | |
elif parent.value < item: | |
return self.__find(item, parent.rchild) | |
def find(self, item): | |
return self.__find(item, self.root) | |
def __contains__(self, item): | |
return self.find(item) | |
def __insert(self, val, parent): | |
if val <= parent.value: | |
if parent.lchild is None: | |
parent.lchild = Node(val) | |
else: | |
self.__insert(val, parent.lchild) | |
if val > parent.value: | |
if parent.rchild is None: | |
parent.rchild = Node(val) | |
else: | |
self.__insert(val, parent.rchild) | |
def add(self, val): | |
if self.root is None: | |
self.root = Node(val) | |
else: | |
self.__insert(val, self.root) | |
return self | |
def traverse_depth(self, parent=None): | |
if parent is None: | |
self.q.clear() | |
parent = self.root | |
if parent is None: | |
return | |
if parent.lchild: | |
self.traverse_depth(parent.lchild) | |
# print(parent.value) | |
self.q.append(parent) | |
if parent.rchild: | |
self.traverse_depth(parent.rchild) | |
def traverse_breadth(self, parent=None): | |
if not parent and self.root: | |
self.q.clear() | |
self.level.clear() | |
parent = self.root | |
self.level.append(parent) | |
if parent is None: | |
return | |
current_node = self.level.popleft() | |
while current_node: | |
self.q.append(current_node) | |
if current_node.lchild: | |
self.level.append(current_node.lchild) | |
if current_node.rchild: | |
self.level.append(current_node.rchild) | |
if len(self.level) > 0: | |
current_node = self.level.popleft() | |
else: | |
current_node = None | |
def print_traversal(self): | |
for node in self.q: | |
print(node.value) | |
# Example Data | |
# 50 | |
# 25 75 | |
# 12 37 63 87 | |
# 6 18 31 44 57 69 81 93 | |
bt = BT() | |
bt.add(50).add(25).add(75).add(12).add(37).add(63) \ | |
.add(87).add(6).add(18).add(31).add(44).add(57) \ | |
.add(69).add(81).add(93) | |
print('DFS') | |
bt.traverse_depth() | |
bt.print_traversal() | |
print('BFS') | |
bt.traverse_breadth() | |
bt.print_traversal() | |
print('bsearch') | |
print(f'{63 in bt}') | |
print(f'{23 in bt}') | |
print(f'{93 in bt}') | |
print(f'{6 in bt}') | |
print(f'{45 in bt}') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment