Now comes my favorite part of this class, the binary tree. This is a data structure that builds upon linked lists. Simply, linked lists are one way with one pointer, like a chain. On the other hand, binary tree is more complicated with at most two branches under each data. One can even say that linked lists are binary trees but with one branch all the way. Of course there might be other tree structures with more than two branches, but what we are learning now is only the basic type.
```````````````
We still start with a 'linked list'-like structure, only with more parameters. Data is still the value we are looking at, left and right are simply named for the two branches the data connects to. Like a family tree, the data on top is a parent, and it has left children and right children.
class Node:
def __init__(self, data, left, right):
self.data = data
self.left = left
self.right = right
Of course there has to be a tree top in the whole binary tree to start with, we call it the root.
class BinaryTree(Node):
def__init__(self):
self.root = None
```````````````
Binary Tree has a much better use on data with multiple branching factors. A linked list may be a string of numbers. The Binary Tree would be able to give a tree of numbers differentiating odd and even, big and small. Normally the tree data is in a certain order so when we look for a particular piece of information, we know to look into the left branch or the right. (suppose left is for data smaller than value X, right is for data bigger than value X).
Inserting a node would not be hard in this sorted structure.
```````````````
inserting an object into the tree
def insert(self, root, object):
if root == None:
root = Node(object)
else:
if(object <= root.data):
root.left = self.insert(root.left, object)
else:
root.right = self.insert(root.right, object)
the first if clause is to place the object where should be placed.
No comments:
Post a Comment