Lesson 8 Tree

Definition of Tree

Tree: hierarchical access
mimic explanation:

• dir/subdir/subdir/file

      root

subtree subtree subtree
….. …. …..

• #card=math&code=T%20%5Cequiv%20%28root%3B%20T1%2CT_2%2C…%2CT_n%29) recursive definition
  #card=math&code=T_1%20%5Cequiv%20%28sub-root%3B%20T%7B11%7D%2CT%7B12%7D%2CT%7B13%7D%2C…%2CT%7B1m%7D%29)
  #card=math&code=T_%7Bterm%7D%20%5Cequiv%20%28root%3B%20%29) termination condition

• structure and naming

Tree representation

use vector as container

use linked list as container

• two types of pointer: child and sibling
  detailed:
  
  This is called binary tree
  left-child right-sibling representation of general tree

func constructTree(data)
if data empty
    return null
else
    create root node from data[0]
    partition data to n sets
    for i = 1 to n
        T[i] = constructTree(i-th partition of data)
    link root to T[i]'s
return address of root node

How Many nodes?

• relation between height and number of nodes
  

-1%20%5Cleq%20h%20%5Cleq%20n-1#card=math&code=lg%28n%2B1%29-1%20%5Cleq%20h%20%5Cleq%20n-1)

We try to decrease the height of the tree —— make it more similar to tree than linked list

Full Binary Tree

left: 0 operate: 2
right: 1 operate:2 + 1

We can use index to get the full binary tree’s node

front nodes of a binary tree: complete binary tree

Expression Tree

link the former infix evaluation to the tree