Starting from:
$22.99
Lab09: Tree Traversal
Lab09: Tree Traversal
1. Introduction In this exercise, we will implement two Python functions in order to practice tree traversal algorithms.
2. Objectives The purpose of this assignment is to help you: • Practice preorder tree traversal and postorder tree traversal algorithms. • Refresh knowledge on tree data structure. • Get familiar with some tree traversal related applications. Note: Before you start, if you are not familiar with tree, tree traversal algorithms, you are recommended to review your lecture notes and the additional materials from Dr. Don Sheehy.
3. Background 3.1. Trees Trees data types are ideal for representing hierarchical structure. Trees are composed of nodes and nodes have 0 or more children or child nodes. A node is called the parent of its children. Each node has (at most) one parent. If the children are ordered in some way, then we have an ordered tree. We are concerned primarily with rooted trees, i.e. there is a single special node called the root of the tree. The root is the only node that does not have a parent. The nodes that do not have any children are called leaves or leaf nodes. There are many examples of hierarchical (tree-like) structures: • Class Hierarchies (assuming single inheritance). The subclass is the child and the superclasses is the parent. The python class object is the root. • File folders or directories on a computer can be nested inside other directories. The parent-child relationship encode containment. • The tree of recursive function calls in the execution of a divide-and-conquer algorithm. The leaves are those calls where the base case executes. Even though we use the family metaphor for many of the naming conventions, a family tree is not actually a tree. The reason is that these violate the one parent rule.
2
When we draw trees, we take an Australian convention of putting the root on the top and the children below. Although this is backwards with respect to the trees we see in nature, it does correspond to how we generally think of most other hierarchies. 3.2. Tree Traversal Previously, all the collections we stored were either sequential (i.e., list, tuple, and str) or nonsequential (i.e., dict and set). The tree structure seems to lie somewhere between the two. There is some structure, but it's not linear. We can give it a linear (sequential) structure by iterating through all the nodes in the tree, but there is not a unique way to do this. For trees, the process of visiting all the nodes is called tree traversal. For ordered trees, there are two standard traversals, called preorder and postorder, both are naturally defined recursively. In a preorder traversal, we visit the node first followed by the traversal of its children. In a postorder traversal, we traverse all the children and then visit the node itself. The visit refers to whatever computation we want to do with the nodes. The printpreorder method is a classic example of a preorder traversal and printpostorder method is a classic example of postorder traversal. def printpreorder(self): print(self.data) for child in self.children: child.printtree()
def printpostorder(self): for child in self.children: child.printpostoder() print(self.data) (All the contents in this section are almost directly copied and pasted from Dr. Don Sheehy’s note online1. All the credit given to Dr. Don Sheehy.) 4. Assignment In this assignment, we need to complete two methods in a given tree class. These two methods are both following the tree traversal philosophy. 4.1. Print Book Content In the background section, we mentioned that trees are ideal for representing hierarchical structure. In our daily life, book, this object, follows a standard class hierarchy which can be represented in a tree manner, where a book contains chapters and a chapter contains different sections. In this subsection, we will write a method called printbookcontent which can print the table of contents of a book in a nice way.
1 Cited from Don Sheehy’s Notes. https://github.com/donsheehy/datastructures/blob/master/prose/13_trees.md
3
Now, we may have a look at the skeleton code, which initializes a table of book contents as an instance of Tree like the following,
Tbook = [('Make Money Fast!', 0), [('1. Motivations', 2), [('1.1 Greed', 5)], [('1.2 Avidity', 10)]], [('2. Methods', 15), [('2.1 Stock Fraud', 20)], [('2.2 Ponzi Scheme', 25)], [('2.3 Bank Robbery', 30)]], [('References', 40)]] treeBook = Tree(Tbook) The tree can be visualized as the following. As we can see, the data contained in each node of the tree is a tuple. Each tuple contains the content name and the corresponding page.
An easy way to print the table of contents of this book is to call the printpreorder method which has been successfully implemented in the Tree class,
Tbook = [('Make Money Fast!', 0), [('1. Motivations', 2), [('1.1 Greed', 5)], [('1.2 Avidity', 10)]], [('2. Methods', 15), [('2.1 Stock Fraud', 20)], [('2.2 Ponzi Scheme', 25)], [('2.3 Bank Robbery', 30)]], [('References', 40)]] treeBook = Tree(Tbook) print(" Call preorderprint method:") treeBook.printpreorder() The output is,
4
The output above shows the book contents clearly but not nicely. So, in this subsection, we will implement a modified version of printpreorder method, called printbookcontent method, so that the table of contents can be printed nicely as the following on the right-hand side:
print("Preorder Print Book Content:") treeBook.printbookcontent()
original preorderprint method printbookcontent method As we can see in the two figures above, the differences between the outputs of the two methods are clearly marked. Compared with the original preorderprint method, we make printbookcontent method really fetch and print the content of each node in the tree but not just pure tuples. Further, we added a Book Title: before the title of the book, and we skip printing the page information of the title. Also, for all the following chapters and sections, we added page: before each page number. Another thing that we need to consider is that, when we are implementing the printbookcontent method, the method needs to be robust for different book titles and their corresponding pages. For example, the page of the book title can be 0, or -1, or 1 or None or even some special numbers that we not know. So, we cannot locate the node which contains book title by simply checking its page. Instead, we need to take advantage of the observation that book title node is always the root. Following are two more examples, where printbookcontent method can always locate the book title node with different corresponding page numbers.
5
4.2. Space Computation in File System In the background section, we mentioned that computer file system can be represented in a tree manner, where file folders or directories on a computer can be nested inside other directories. And, in this subsection, we will implement one method which helps to compute the space used by files in a directory and its subdirectories in a tree-structured file system. As we can see in the skeleton code, we initialize a file system like the following,
Tfile = [('CSE2050/', None), [('HWs/', None), [('hw1.doc', 5)], [('hw2.doc', 15)]], [('LABs/', None), [('lab1.py', 7)], [('lab2.py', 10)], [('lab3.py', 10)]], [('ToDoList.txt', 20)]] treeFile = Tree(Tfile) We can visualize the file system as the following. Similar to the previous example, the data contained in each node of the tree is also a tuple. The tuple contains the folder or file name and the size of each file, while the space of each directory (folder) is temporally unknown.
1. Introduction In this exercise, we will implement two Python functions in order to practice tree traversal algorithms.
2. Objectives The purpose of this assignment is to help you: • Practice preorder tree traversal and postorder tree traversal algorithms. • Refresh knowledge on tree data structure. • Get familiar with some tree traversal related applications. Note: Before you start, if you are not familiar with tree, tree traversal algorithms, you are recommended to review your lecture notes and the additional materials from Dr. Don Sheehy.
3. Background 3.1. Trees Trees data types are ideal for representing hierarchical structure. Trees are composed of nodes and nodes have 0 or more children or child nodes. A node is called the parent of its children. Each node has (at most) one parent. If the children are ordered in some way, then we have an ordered tree. We are concerned primarily with rooted trees, i.e. there is a single special node called the root of the tree. The root is the only node that does not have a parent. The nodes that do not have any children are called leaves or leaf nodes. There are many examples of hierarchical (tree-like) structures: • Class Hierarchies (assuming single inheritance). The subclass is the child and the superclasses is the parent. The python class object is the root. • File folders or directories on a computer can be nested inside other directories. The parent-child relationship encode containment. • The tree of recursive function calls in the execution of a divide-and-conquer algorithm. The leaves are those calls where the base case executes. Even though we use the family metaphor for many of the naming conventions, a family tree is not actually a tree. The reason is that these violate the one parent rule.
2
When we draw trees, we take an Australian convention of putting the root on the top and the children below. Although this is backwards with respect to the trees we see in nature, it does correspond to how we generally think of most other hierarchies. 3.2. Tree Traversal Previously, all the collections we stored were either sequential (i.e., list, tuple, and str) or nonsequential (i.e., dict and set). The tree structure seems to lie somewhere between the two. There is some structure, but it's not linear. We can give it a linear (sequential) structure by iterating through all the nodes in the tree, but there is not a unique way to do this. For trees, the process of visiting all the nodes is called tree traversal. For ordered trees, there are two standard traversals, called preorder and postorder, both are naturally defined recursively. In a preorder traversal, we visit the node first followed by the traversal of its children. In a postorder traversal, we traverse all the children and then visit the node itself. The visit refers to whatever computation we want to do with the nodes. The printpreorder method is a classic example of a preorder traversal and printpostorder method is a classic example of postorder traversal. def printpreorder(self): print(self.data) for child in self.children: child.printtree()
def printpostorder(self): for child in self.children: child.printpostoder() print(self.data) (All the contents in this section are almost directly copied and pasted from Dr. Don Sheehy’s note online1. All the credit given to Dr. Don Sheehy.) 4. Assignment In this assignment, we need to complete two methods in a given tree class. These two methods are both following the tree traversal philosophy. 4.1. Print Book Content In the background section, we mentioned that trees are ideal for representing hierarchical structure. In our daily life, book, this object, follows a standard class hierarchy which can be represented in a tree manner, where a book contains chapters and a chapter contains different sections. In this subsection, we will write a method called printbookcontent which can print the table of contents of a book in a nice way.
1 Cited from Don Sheehy’s Notes. https://github.com/donsheehy/datastructures/blob/master/prose/13_trees.md
3
Now, we may have a look at the skeleton code, which initializes a table of book contents as an instance of Tree like the following,
Tbook = [('Make Money Fast!', 0), [('1. Motivations', 2), [('1.1 Greed', 5)], [('1.2 Avidity', 10)]], [('2. Methods', 15), [('2.1 Stock Fraud', 20)], [('2.2 Ponzi Scheme', 25)], [('2.3 Bank Robbery', 30)]], [('References', 40)]] treeBook = Tree(Tbook) The tree can be visualized as the following. As we can see, the data contained in each node of the tree is a tuple. Each tuple contains the content name and the corresponding page.
An easy way to print the table of contents of this book is to call the printpreorder method which has been successfully implemented in the Tree class,
Tbook = [('Make Money Fast!', 0), [('1. Motivations', 2), [('1.1 Greed', 5)], [('1.2 Avidity', 10)]], [('2. Methods', 15), [('2.1 Stock Fraud', 20)], [('2.2 Ponzi Scheme', 25)], [('2.3 Bank Robbery', 30)]], [('References', 40)]] treeBook = Tree(Tbook) print(" Call preorderprint method:") treeBook.printpreorder() The output is,
4
The output above shows the book contents clearly but not nicely. So, in this subsection, we will implement a modified version of printpreorder method, called printbookcontent method, so that the table of contents can be printed nicely as the following on the right-hand side:
print("Preorder Print Book Content:") treeBook.printbookcontent()
original preorderprint method printbookcontent method As we can see in the two figures above, the differences between the outputs of the two methods are clearly marked. Compared with the original preorderprint method, we make printbookcontent method really fetch and print the content of each node in the tree but not just pure tuples. Further, we added a Book Title: before the title of the book, and we skip printing the page information of the title. Also, for all the following chapters and sections, we added page: before each page number. Another thing that we need to consider is that, when we are implementing the printbookcontent method, the method needs to be robust for different book titles and their corresponding pages. For example, the page of the book title can be 0, or -1, or 1 or None or even some special numbers that we not know. So, we cannot locate the node which contains book title by simply checking its page. Instead, we need to take advantage of the observation that book title node is always the root. Following are two more examples, where printbookcontent method can always locate the book title node with different corresponding page numbers.
5
4.2. Space Computation in File System In the background section, we mentioned that computer file system can be represented in a tree manner, where file folders or directories on a computer can be nested inside other directories. And, in this subsection, we will implement one method which helps to compute the space used by files in a directory and its subdirectories in a tree-structured file system. As we can see in the skeleton code, we initialize a file system like the following,
Tfile = [('CSE2050/', None), [('HWs/', None), [('hw1.doc', 5)], [('hw2.doc', 15)]], [('LABs/', None), [('lab1.py', 7)], [('lab2.py', 10)], [('lab3.py', 10)]], [('ToDoList.txt', 20)]] treeFile = Tree(Tfile) We can visualize the file system as the following. Similar to the previous example, the data contained in each node of the tree is also a tuple. The tuple contains the folder or file name and the size of each file, while the space of each directory (folder) is temporally unknown.
1 file (358.7KB)
