A basic implementation of a binary tree structure.
A binary tree is basically a structure with nodes connected by edges. Each node has a maximum of two children, which are usually called as the left child node and the right child node. The first node of the tree is commonly referred to as the root.
The structure of our binary tree will be divided in 2 classes (Node and BinaryTree) and 1 builder function (BuildTree).
The Node class is responsible for storing the node data (or the node value) and referring (or not) to child nodes that will be connected to its left and right edges. So, the node class will have 3 attributes: data, left and right.
class Node(object):
def __init__(self, data):
self._data = data
self._left = None
self._right = None
@property
def data(self):
return self._data
@data.setter
def data(self, value):
self._data = value
@property
def left(self):
return self._left
@left.setter
def left(self, value):
self._left = Node(value)
@property
def right(self):
return self._right
@right.setter
def right(self, value):
self._right = Node(value)
def __str__(self):
left = self._left and self._left.data
right = self._right and self._right.data
return f'Node [{self._data}] {{left: {left}, right: {right}}}'
N = Node(5)
print(N)
Node [5] {left: None, right: None}
The BinaryTree class has just 1 attribute, which is the root. This attribute is a Node object and starts the chain of Node object that will compound the tree itself. The print method is based on level-order traversal algorithm, but it will be covered in another notebook.
class BinaryTree(object):
def __init__(self, value=None):
self._root = value and Node(value)
@property
def root(self):
return self._root
@root.setter
def root(self, value):
self._root = Node(value)
def __str__(self):
# print level-order
order, stack = [], [self._root]
while stack:
node = stack.pop(0)
if node:
order += [node.data]
stack += [node.left, node.right]
return " -> ".join([f'{e}' for e in order])
The BuildTree function receive 2 arguments. The first one is the root of a BinaryTree object and the second is the list of pair values (left and right) for each node. The first pair is the left and right of the root and other ones are respective to the other nodes, following the top/down and left/right order. If the pair has -1 as value, it means the current node has no child in this edge (this happens always with leaf nodes).
def BuildTree(root, values):
if isinstance(root, Node):
# Init stacking the root node
stack = [root]
# Loop through values
for l, r in values:
# Get the first element from the stack
node = stack.pop(0)
# Store left node if not -1
if l != -1:
node.left = l
stack += [node.left]
# Store right node if not -1
if r != -1:
node.right = r
stack += [node.right]
For example, having the following binary tree:
The build function would be:
BT = BinaryTree(5)
BuildTree(BT.root, [
[2, 3],
[4, 1],
[9, 8],
[6, 7],
[-1, -1],
[-1, -1],
[10, -1],
[-1, -1],
[-1, -1],
[-1, -1]
])
print(BT)
5 -> 2 -> 3 -> 4 -> 1 -> 9 -> 8 -> 6 -> 7 -> 10