Definitions :
- Node : data stored at one location in the tree(A,B,C,D,E,F,G,H,I,J)
- Root node : top most node in the tree from which all other nodes originate(A)
- Leaf node : A node with no sub trees(D,E,F,I,J,G)
- Child: a node that descends from an existing node(B->J)
- Parent : root of the child node (A parent B)
- Siblings : nodes that have the same parent(H,G)
- Ancestor : All nodes that can be reached by moving in an upward direction in the tree. Eg. H,C,A are ancestors of I
- Descendants : all nodes that can be reached by moving down wards through the tree. Descendants of C are G,H,I,and J
- Levels/depth : level O refers to the root node and then each level forward is represented by descendants of that root node
- Sub-tree : any node in the tree that can be viewed as the root of a new smaller tree.
- Height : the total number of levels in the tree(in our example , we have 4 levels starting at index 0->3).
- Path : set of branches taken to connect an ancestor of a node a descendant. Usually described by the set of nodes encountered along the path.
- Array representation of a binary tree: suppose line number the nodes from left to right beginning at the top and ending at the bottom. We can store various data items in corresponding elements of an array. Assume (above nodes) is a representation of a BST (Binary search tree : all nodes to the left of the root are smaller, all nodes right of root are greater than root)
- Representation of a BST through an array.
- The data from the root always appears at index 0
- If the data for a non-root node appears in component i of the array then the data for its parent is always at location [(i-1)/2] using int
- If the data for a node appears at location i of the array, then its children(if present) always have their data at locations, left child [2i+1] right child[2i+2] i represent the index of its parent node, by this rule B[2*0+1] C[2*0+2] D[2*1+1] F[2*1+2] H[2*2+1] G[2*2+2] I[2*5+1] J[2*5+2]
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
A |
B |
C |
D |
F |
G |
|
|
|
|
|
I |
J |