Created
May 19, 2018 22:44
-
-
Save scriptpapi/f05a0a9d24d633388af0c917f5109f9f to your computer and use it in GitHub Desktop.
Simple implementation of Breadth-First Search on a binary tree
This file contains hidden or 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
# Simple implementation of Breadth-First Search on a binary tree | |
from collections import deque | |
class Node: | |
def __init__(self, newData): | |
self.data = newData | |
self.left = None | |
self.right = None | |
def getData(self): | |
return self.data | |
def setData(self, newData): | |
return self.data | |
def getLeftChild(self): | |
return self.left | |
def setLeftChild(self, newData): | |
self.left = newData | |
def getRightChild(self): | |
return self.right | |
def setRightChild(self, newData): | |
self.right = newData | |
class BTree: | |
def __init__(self, newData): | |
self.root = Node(newData) | |
def insert(self, newData): | |
if self.root is None: | |
self.root = Node(newData) | |
else: | |
self._insert(newData, self.root) | |
def _insert(self, newData, node): | |
if newData < node.getData(): | |
if node.getLeftChild() is not None: | |
self._insert(newData, node.getLeftChild()) | |
else: | |
node.setLeftChild(Node(newData)) | |
else: | |
if node.getRightChild() is not None: | |
self._insert(newData, node.getRightChild()) | |
else: | |
node.setLeftChild(Node(newData)) | |
def BFS_search(self, data): | |
if self.root.getData() == data: | |
return True | |
else: | |
bfsQ = deque() | |
bfsQ.append(self.root.getLeftChild()) | |
bfsQ.append(self.root.getRightChild()) | |
found = False | |
while bfsQ.popleft() is not None: | |
tmp = bfsQ.popleft() | |
if tmp.getData() == data: | |
found = True | |
break | |
else: | |
bfsQ.append(tmp.getLeftChild()) | |
bfsQ.append(tmp.getRightChild()) | |
return found |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment