A tree is a finite non-empty set of elements
Used to represent a hierarchical data, meaning that there is a superior-subordinate type relationship
The root of a tree is the element at the highest level of the hierarchy
A subtree is a smaller tree that is contained within the original tree
A parent is an element that has a subordinate element
A child is an element that has a superior element
Siblings are child elements with the same parent
Elements with no child elements are known as leaves
The degree of an element is the number of children that it has
The degree of a tree is the maximum of its element degree
A binary tree is a finite collection of elements where an element has at most two subtrees (or children)
The differences between a binary tree and a tree:
A binary tree can be empty
Each element in a binary tree has at most two subtrees, while each element in a tree can have any number of subtrees
The height of a binary tree is the number of levels in it
A complete binary tree is a binary tree in which each level of the tree is completely filled, with the exception of the bottom level. If the bottom level is incomplete, the nodes are in the leftmost positions
A full binary tree is a binary tree where every parent node has 2 children
Each element is assigned a number starting from the top and working towards the bottom, from left to right. Each element is stored in the array position corresponding to the assigned number.
This type of representation wastes space if there are a number of missing elements on the binary tree and it is useful only when the number of missing elements is small and the tree is complete.
Each element is represented by a node with two link fields (leftChild and rightChild) and a data field.
A leaf node has a leftChild and rightChild link of null. The root node will be pointed to by a pointer variable
A binary tree traversal is when each element of a tree is "visited" exactly one time
During the "visit", any action that needs to be performed is performed
4 types of traversals:
Preorder
Inorder
Postorder
Level order
With the first three traversals, the left subtree is traversed before the right
The difference between the three comes from the difference in the time that the element is "visited"
Each node is "visited" before its left and right subtrees are visited
if (t is not null) process node preorder(t->leftChild) preorder(t->rightChild) endif
Each node is "visited" after its left subtree but before its right subtree
if (t is not null) inorder(t->leftChild) process node inorder(t->rightChild) endif
Each node is "visited" after its left and right subtree are visited
if (t is not null) postorder(t->leftChild) postorder(t->rightChild) process node endif
Elements are visited by level from top to bottom. Within levels, elements are visited from left to right
while (there are elements in the tree)
process the node
if (there is a left child)
push onto a queue
endif
if (there is a right child)
push onto a queue
endif
pop the queue
endwhile
One use of binary trees is to represent arithmetic expressions
Each arithmetic operator may have one or two operands. If there is a left operand, it is the left subtree. If there is a right operand, it is the right subtree. The leaf elements are either constants or variables.
a * b + c / d
(a * b) + (c / d)
A preorder traversal results in the prefix form of an expression
The root of a tree(subtree) will precede its left and right subtree, respectively
(a * b) ==> *ab
(c / d) ==> /cd
(a * b) + (c / d) ==> + * a b / c d
Prefix notation always has the root first
An inorder traversal results in the infix form of an expression
The root of a tree(subtree) will be between its left and right subtrees
(a * b) ==> a*b
(c / d) ==> c/d
(a * b) + (c / d) ==> a * b + c / d
Infix notation always has the root towards the middle
A postorder traversal results in the postfix form of an expression
The root of a tree(subtree) will follow both the left and right subtrees
(a * b) ==> ab*
(c / d) ==> cd/
(a * b) + (c / d) ==> a b * c d / +
Postfix notation always has the root last
A binary tree can be drawn from the infix and either of the other -fix notations
Preorder: + - a b * x y
Inorder: a - b + x * y
Inorder: C X T S K A E B J P Postorder: C S K T X E J B P A