This week, the definition of tree is introduced in class, which includes the definition of several terms such as leaf(node with no children), internal node, subtree, height of a tree and so on. Then, the three kinds of orders to read a tree are also introduced, including the preorder, postorder and inorder.
In order to present the value of each node with the given order, some recursion methods are used to reduce the work load, such as preorder can be represented as [tl[0]] + preorder(tl[1]) + preorder(tl[2]), which can be find out by listing several examples based on the given tree.
Moreover, the way to present inorder is inorder(tl[1]) + [tl[0]] + inorder(tl[2]) and postorder is postorder(tl[1]) + postorder(tl[2]) + [tl[0]]. For each of the tree, a list with either int value or list can be used to present trees, such as [5, [4, None, None], [3, [2, None, None], [1, None, None]]], where None represents no children for the nodes with value that is in the position index 0.
Since the tree is also a kind of ADT, we can create several methods such as check whether a value is contained in the tree by creating a method __contain__ and so on.
One thing that needs to pay attention is that when writing the codes with comprehension, sometimes we need to write "()" and sometimes a list is needed. To provide an example, when using the function sum to find the sum of the given numbers, we need to write sum([numbers]) instead of sum(numbers) since it can sum up the numbers in the list but not the single numbers. Furthermore, writing a square bracket is also necessary when the comprehension is complicated.
-Flora
No comments:
Post a Comment