Monash University >
CSSE >
CSE1303 >
Part A >
Lectures > Lecture A12 notes
CSE1303 Computer Science
Semester 3 (summer), 2003
Part A
Lecture A12 notes: Binary Trees
In this lecture
Reading:
- Kruse 9
- Standish 9
- Langsam 5
- Deitel & Deitel 12.7
What is a Binary Tree?
- A Binary Tree is either empty, or contains a node together with two subtrees called the left subtree and the right subtree.
Traversal Methods
- Here are three ways to traverse a binary tree:
- Preorder Traversal:
Visit the node
Traverse the left subtree
Traverse the right subtree
- Inorder Traversal:
Traverse the left subtree
Visit the node
Traverse the right subtree
- Postorder Traversal:
Traverse the left subtree
Traverse the right subtree
Visit the node
- They all traverse the left subtree before the right subtree.
- The name of the travesal method depends on when the node is visited.
What is a Expression Tree?
- An Expression Tree is a binary tree, built up from operands and operators.
- Also known as a parse tree.
- Used in compilers.
- Preorder corresponds to prefix notation.
- Inorder corresponds to infix notation.
- Postorder corresponds to postfix, or reverse Polish, notation.
[ Top |
Home ]
Last Updated: Tuesday 02 December 2003 22:29:28