Today in the class, we learnt tree traversal. In computer science tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting each node in a tree data structure exactly once. There are many similarity and difference between Tree and Linked List. Like linked lists, trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes and we also learnt deeply in class. These references are referred to as the left and right subtrees. Like list nodes, tree nodes also contain cargo. However, compared to linked lists and other one-dimensional arrays, which have a linear order, tree structures can be traversed in many different ways. In class, we learnt inorder, preorder and postorder for depth-first searching, as well as level order for breadth first searching. Here are the graphs for these models:
Inorder
Postorder
Preorder
Level Order
From these examples, we know more about how tree traversal works. In terms of how to write the code for binary tree search and tree traversal, I find that most of the parts are using recursion algorithm to solve the problems. Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node as it is not a linear data structure. This is often done via a stack (LIFO) or queue (FIFO). As a tree is a recursive data structure, traversal is usually defined by recursion. Thus, I find out that the knowledge are all inter-related and we need to learn all of these methods to understand each other.
No comments:
Post a Comment