Data Structures with Generic Types in Python/

...

/

BinaryTree: A Basic Binary Tree

BinaryTree: A Basic Binary Tree

Learn BinaryTree implementation.

We'll cover the following...

The simplest way to represent a node, u, in a binary tree is to explicitly store the (at most three) neighbours of u:

class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()

When one of these three neighbours is not present, we set it to None. In this way, both external nodes of the tree and the parent of the root correspond to the value None.

The binary tree itself can then be represented by a reference to its root node, r:

class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()
        
    def initialize(self):
        self.r = None

We can compute the depth of a node, u, in a binary tree by counting the number of steps on the path from u to the root:

class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()
        
    def depth(self, u):
        d = 0
        while (u != self.r):
            u = u.parent
            d += 1
        return d

Recursive algorithms

Using recursive algorithms makes it very easy to compute facts about binary trees. For example, to compute the size of (number of nodes in) a binary tree rooted at node u, we recursively compute the sizes of the two subtrees rooted at the children of u, sum up these sizes, and add one:

class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()
    
    def _size(self, u):
        if u == self.nil: return 0
        return 1 + self._size(u.left) + self._size(u.right)

To compute the height of a node u, we can compute the height of u’s two subtrees, take the maximum, and add one:

class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()
        
    def _height(self, u):
        if u == self.nil: return 0
        return 1 + max(self._height(u.left), self._height(u.right))

Traversing binary trees

The two algorithms from the previous section both use recursion to visit all the nodes in a binary ...

Ask