Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Implementing Trees

In this section we consider the implementation of trees including general trees, N-ary trees, and binary trees. The implementations presented have been developed in the context of the abstract data type framework presented in Chapter . That is, the various types of trees are viewed as classes of containers as shown in Figure .

  
Figure: Object class hierarchy

Program  introduces the Tree class. The abstract Tree class extends the abstract Container class introduced in Program .

  
Program: Abstract Tree class.

The abstract Tree class adds the following operations to those inherited from the Container class:

key

This property accesses the object contained in the root node of a tree.

getSubtree

This method returns the subtree of the given tree.

isEmpty

This bool-valued property is true if the root of the tree is an empty tree, i.e., an external node.

isLeaf

This bool-valued property is true if the root of the tree is a leaf node.

degree

This property accesses the degree of the root node of the tree. By definition, the degree of an external node is zero.

height

This property accesses the height of the tree. By definition, the height of an empty tree is -1.

depthFirstTraversal and breadthFirstTraversal

• Tree Traversals
• Tree Iterators
• General Trees
• N-ary Trees
• Binary Trees
• Binary Tree Traversals
• Comparing Trees
• Applications

Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.