Lecture 12 - Binary Trees
Lecture Outline:
- Binary tree definition:
A rooted tree in which each node has at most one left and at most one right child
- Mathematical definition:
A binary tree is either empty or it consists of a node called the
root together with two binary trees called the left subtree and the
right subtree of the root.
- Terminology: child, parent, leaf, root, height, depth
- Full binary tree
- Complete binary tree
- Tree traversals
- Preorder
- Inorder
- Postorder
- Expression trees
- Binary search tree: a binary tree taht is either empty or in which each node contains a key that satisfies the conditions:
- all keys (if any) in the left subtree of the root precede the key in the root
- the key in the root precedes all the keys (if any) in its right subtree
- the left and right subtrees if the root are again search trees
- Binary search tree example:
Jim Dot Ron Tim Guy Amy Roy Eva Ann Jan Kay Tom Kim Jon
- Alternative order of presentation:
Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim Kay Ron Jan
- Java implementation: