A binary tree is a graph that does not have any loops or cross-links, the branches do not run across each other. You may have come across trees when programming in Logo. Trees have 'nodes' where data is stored and links between nodes. Binary trees have just two links, one pointing to the left and one to the right.
Put the names of eight class members into a binary tree. Write names on cards, pick a card for the 'root' and then grow the tree with random selections. You will have to follow the rules for inserting items in the tree: if a name is greater than the one at the current node then move left, otherwise move right until an empty space is found.
Compare the number of levels in trees across the class. Can you move systematically through the tree and derive a list in alphabetical order?
Search for each name in turn and count the number of nodes that you need to find each one. Put the cards in linear order and calculate the average number of nodes you would need to find an item. How does searching a tree compare with searching a list?
Write the parts of a simple expression on the reverse of the cards e.g. 2 + 2 - put a '2' on one card, a '+' on another and so on. Place the cards in a tree formation with the + at the root and the 2s either side. Write down the expressions derived from traversing the tree in these ways:
LNR: go left as far as possible, write down the last item found; write down the value in the root of the sub-tree; check the right branch, if no left sub-branches then write down value or continue (if item is operator it will have left and right children, if it is an operand it will have no children)
NLR: write down value in root, check left and write down item found - if operator continue left, if operand check right;
LRN: go left as far as possible, write down last item found; check right including any sub-trees, if no sub-trees write down item; return to node and write down value;
(where N = node or root)
Now write the following values on cards and place them in a tree with the + at the root and the * in the right branch: 2 + 2 * 2
Traverse the tree in LRN fashion and work out the arithmetic result.
Rearrange the tree with * in the root and + in the right branch and repeat the above traversal. What result do you get?
Expressions can have the operator before or after the operands as well as in between. What advantage does postfix have over infix?