A binary tree is a tree-like structure that has a root and in which each vertex has no more than two children. Each child of a vertex is called a left or right child.
Implementing a binary tree can be complex. The code below shows a simple implementation using a Tree Class. The first few methods have been implemented.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
class BinaryTree(): def __init__(self,rootid): self.left = None self.right = None self.rootid = rootid def getLeftChild(self): return self.left def getRightChild(self): return self.right def setNodeValue(self,value): self.rootid = value def getNodeValue(self): return self.rootid
There are three ways of traversing a binary tree: pre-order, in-order and post-order.
|Root||Left sub-tree||Left sub-tree|
|Left sub-tree||Root||Right sub-tree|
|Right sub-tree||Right sub-tree||Root|
- Implement the code given to start the binary tree implementation.
- Add the insertRightChild and insertLeftChild
- Now add the functions for printing the tree in pre-order order, in-order and post-order.
When you have tried the above exercises, you can download the whole program here.
- Previous - Linked Lists