KEMBAR78
Programming Project 6.5 | PDF
Scribd
Upload
6 views2 pages

Programming Project 6.5

The document outlines a programming project to implement binary-search tree functions, including search, insert, and in-order print methods. It provides a base code for a LinkedBinaryTree class with a nested Node class and methods for tree operations. The main section demonstrates inserting values into the tree and searching for specific keys, along with a placeholder for the implementation of the required functions.

Uploaded by

c.am.usp.am.m
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
6 views2 pages

Programming Project 6.5

The document outlines a programming project to implement binary-search tree functions, including search, insert, and in-order print methods. It provides a base code for a LinkedBinaryTree class with a nested Node class and methods for tree operations. The main section demonstrates inserting values into the tree and searching for specific keys, along with a placeholder for the implementation of the required functions.

Uploaded by

c.am.usp.am.m
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

Chapter 11 - Programming Project: Implement following binary-search tree functions:

- search(key)

- insert(key)

- print_in_order(): prints the keys in the binary tree in ascending order.

# Use a given base code

import queue

class LinkedBinaryTree:
class _Node:
__slots__ = '_el', '_l', '_r'

def __init__(self, element, left=None, right=None):


self._el = element
self._l = left
self._r = right

def __init__(self):
self._root = None
self._size = 0

def __len__(self):
return self._size

def height(self):
return self._height(self._root)

def _height(self, p):


if not p:
return 0
return 1 + max(self._height(p._l), self._height(p._r))

def _in_order(self, p):


if p:
yield from self._in_order(p._l)
yield p._el
yield from self._in_order(p._r)

def _pre_order(self, p):


if p:
yield p._el
yield from self._pre_order(p._l)
yield from self._pre_order(p._r)

def _post_order(self, p):


if p:
yield from self._post_order(p._l)
yield from self._post_order(p._r)
yield p._el

def breadth_first(self):
q = queue.Queue()
q.put(self._root)
while not q.empty():
p = q.get()
if p:
print(p._el)
if p._l:
q.put(p._l)
if p._r:
q.put(p._r)

def bst_insert(self, key):


if self._root is None:
self._root = self._Node(key)
else:
self._bst_insert(self._root, key)
self._size += 1

def _bst_insert(self, node, key):


# Your code here
pass

def bst_search(self, key):


return self._bst_search(self._root, key)

def _bst_search(self, node, key):


# Your code here
pass

def print_in_order(self):
# Your code here
pass

if __name__ == "__main__":
tree = LinkedBinaryTree()
for value in [7, 3, 2, 5, 6, 9, 1, 4, 8, 10]:
tree.bst_insert(value)

print("Search for 4:", tree.bst_search(4)) # true


print("Search for 2:", tree.bst_search(2)) # false

print("In-order traversal:")
tree.print_in_order()

You might also like