CSC148 2015winter

Week 8 Binary Tree and Tree Traversal

In week 8 we mainly talked about binary tree, binary search tree, and tree traversal. On the base of learning tree for few weeks, it was easier for us to understand binary tree and binary search tree in some degree. That is because binary tree is a special case of tree, and binary search tree is a special case of binary tree. But there still some parts we need to pay a close attention to (e.g. efficiency).

l Brief definition

1. Binary tree:

a tree with branching factor 2. We call the children the left and the right children. (Attention: if there is a child, its branching factor is still two)

→ variation of Tree

2. Binary search tree:

A binary tree with these additional property:

For every node, its values is 1) greater than all values in its left subtree,

2) less than all values in its right subtree.

(Its follows that any subtree of a binary search tree is also a binary search tree)

→ variation of Binary search tree

l Difference on recursion between Tree, Binary tree and Binary search tree

Although the structures on Tree, Binary tree and Binary search tree are quite similar, when we write codes, we have more efficient ways to deal with the special case.

For instance, the function contains:

1. Tree

For Tree, using the root as base case, recursion to all tree’s children(tracing every branch)

2. Binary Tree

# This version① of contains prevents such calls. (complicates)

# This version② of contains doesn't prevent such calls. It recurses right past the leaves to None.

For Binary Tree, compared to Tree, we still use root as base case. But we can seen from version①, we add the condition “if node.left(right)”before the recursion. It is more efficient since if there is no left or right branch we don’t need to check it again.

3. Binary Search Tree

# this version① prevents recursing past the leaves, so it does not handle None.

# This version② recurses all the way to None.

For Binary Search Tree, compared to Binary Tree, we do much more efficient steps. Seen from version①, we add another condition “if v<node.data” before the condition “if node.left (right)” . We take advantage of the order of Binary Search Tree, at each code, if we don’t find v, we know the value of v compare to the left or right side. Therefore, we just do the recursion to one side, and are able to ignore the other side!

l Tree Traversal

ü Algorithm Inorder(tree)

1. Traverse the left subtree, i.e., call Inorder(left-subtree)

2. Visit the root.

3. Traverse the right subtree, i.e., call Inorder(right-subtree)

ü Algorithm Preorder(tree)

1. Visit the root.

2. Traverse the left subtree, i.e., call Preorder(left-subtree)

3. Traverse the right subtree, i.e., call Preorder(right-subtree)

ü Algorithm Postorder(tree)

1. Traverse the left subtree, i.e., call Postorder(left-subtree)

2. Traverse the right subtree, i.e., call Postorder(right-subtree)

3. Visit the root.

Some experience in solving this:

Because the definitions of this part seems very simple to understand, I didn’t pay much attention to them at first. However, when I start to do the exercise, it became messy, and it is surprised me that I could not tell the difference between inorder, preorder and postorder precisely each time and always made stupid mistakes. Then, I searched on the internet, and I found the teaching videos with a lot of examples on YouTube is really beneficial. The remainder is “practice is the shortcut!” When you practice some, you will find it really easy and won’t regret after exam because of losing marks on this part. （Y^o^Y）