Binary tree is the main topic. The concept is not hard to understand.
*After Test 2 I found I miss one important idea called traversal, which means visiting the nodes to do something at each. There are three types of traversal, in order, pre order and post order. I found an really amazing image to conclude these three:
The order of number is exactly the order nodes are visited.
BST
A binary search tree is a binary tree with specific order of nodes. For every node, its value is greater than all values in its left subtree and less than all values in its right subtree
About
recursion
Among the
three given topics, I think recursion is the most difficult idea (especially
when combine with other topics like trees)that I am still not fully comfortable
with.
Recursion requires you to have a different way of thinking, one
cannot find the solution in a straight way (because you do not know how many
time it would recurse, and what it the situation of it.)
Recursion needs us to change our thinking mode. Things go
recursively with a base case and recursive cases. Everything would go through
in recursive case, and finally finish in base case. All base case would gather
together to form the whole function. The change from straight solution to make
it in a base case and recursive cases is where the difficulty stands.
Week 8
The topic this week is linked list, which is far complicate than I
used to think.
I used to think linked list are trees that have just one child.
Since we have learnt Binary search tree, which children could be more than one,
and must be in certain order, linked list should not be harder.
However, linked list has more elements. From the initialize method
of linked list, we can find it has a value (which is the value of certain node
) and a nxt (refers to other similar objects). Moreover, it has a wrapper class
which assist to track the information about the entire list. It has a front, a
back and stores the size of a linked list.
Week 9
More on BTNode
A new BTNode is introduced which is called BST (binary search tree).
Compare to BTNode, BST has a strict limitation in terms of nodes. All children
nodes on the left side of parent node must be smaller than the parent node, and
the one on the right must be larger than the parent node.
