List of Lists Representation
Let’s formalize this definition of the tree data structure by providing some functions that make it easy for us to use lists as trees.
In a tree represented by a list of lists, we will begin with Python’s list data structure and write the functions defined above. Although writing the interface as a set of operations on a list is a bit different from the other abstract data types we have implemented, it is interesting to do so because it provides us with a simple recursive data structure that we can look at and examine directly. In a list of lists tree, we will store the value of the root node as the first element of the list. The second element of the list will itself be a list that represents the left subtree. The third element of the list will be another list that represents the right subtree. To illustrate this storage technique, let’s look at an example. Figure 1 shows a simple tree and the corresponding list implementation.
myTree = ['a', #root
['b', #left subtree
['d', [], []],
['e', [], []] ],
['c', #right subtree
['f', [], []],
[] ]
]
Notice that we can access subtrees of the list using standard list indexing. The root of the tree is myTree[0]
, the left subtree of the root is myTree[1]
, and the right subtree is myTree[2]
. ActiveCode 1 illustrates creating a simple tree using a list. Once the tree is constructed, we can access the root and the left and right subtrees. One very nice property of this list of lists approach is that the structure of a list representing a subtree adheres to the structure defined for a tree; the structure itself is recursive! A subtree that has a root value and two empty lists is a leaf node. Another nice feature of the list of lists approach is that it generalizes to a tree that has many subtrees. In the case where the tree is more than a binary tree, another subtree is just another list.
0 comments Comments
Leave a comment
 Basic Data Structures

Objectives

What Are Linear Structures?

What is a Stack?

The Stack Abstract Data Type

Implementing a Stack in Python

What Is a Queue?

The Queue Abstract Data Type

Implementing a Queue in Python

What Is a Deque?

The Deque Abstract Data Type

Implementing a Deque in Python

Lists

The Unordered List Abstract Data Type

Implementing an Unordered List: Linked Lists

The Ordered List Abstract Data Type

Implementing an Ordered List

Vocabulary and Definitions

 Sorting and Searching
 Trees and Tree Algorithms
 Graphs and Graph Algorithms