Skip to content

Instantly share code, notes, and snippets.

@scriptpapi
Created May 19, 2018 22:44
Show Gist options
  • Save scriptpapi/f05a0a9d24d633388af0c917f5109f9f to your computer and use it in GitHub Desktop.
Save scriptpapi/f05a0a9d24d633388af0c917f5109f9f to your computer and use it in GitHub Desktop.
Simple implementation of Breadth-First Search on a binary tree
# 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