CS 2114 Lecture Notes - Lecture 25: Binary Tree, Mobile Suit Gundam, Preorder
29 Apr 2018
School
Department
Course
Professor
Daniel T. Eisert CS-2114
1
Lecture 25 – ADT Tree
April 18, 2018 (Week 13)
Class Business
Project V final submission is due Thursday, April 26. The contribution report
and ethics discussion are both due Sunday, April 29.
Last lab session is Wednesday, April 25.
OpenDSA Homework on Trees is due Monday, April 30.
Individual Design Homework is due Monday, April 30 (review Vending UML).
Debugging
Use Breakpoint Properties and add a condition if you want to view iteration
290, for example (such that i == 200).
Tree
Terminology
- Root: the top of the tree.
- Edge: the side branches of a tree.
- Siblings: nodes on the same level.
- Children: the descendants of a higher node.
- Leaves: termini of the tree (at the bottom)—the base case of the tree.
- Subtree: every tree is made up of a subtree.
- Height: the number of levels in a tree.
- Full Tree (Binary Tree): every parent has two children.
- Complete Tree (Binary Tree): It is full except for on the last level and
is filled from left to right. Complete trees are ALWAYS balanced.
- Balanced Tree: The nodes are spread evenly across the tree with no
more than a one level difference.
- Maximum Number of Nodes in a Binary Tree:
Efficiency
- It is more efficient to traverse a tree that is balanced.
- The ADT Tree is used more often than other data structures.
Applications
- Searching – map and set objects.
- Video games – trees for decision making.
- Networking – managing router-tables.
Traversals
Traversals can pass through a node without visiting it. The order in which we
visit items is not unique. Recursion is often a good approach to use. One must:
1. Visit the root
2. Visit the root’s left subtree.
3. Visit the root’s right subtree.
Types of Traversals: See Reading 11 Notes.
1. Preorder – visit the root before the children (left to right).
2. Inorder – visit the root between visiting nodes in the root’s subtrees
(like a hook from the left to the right).
3. Postorder – visit the root after visiting the nodes in a subtree (parent
after—left to right before going to the parent).
4. Level-order – not always recursive; process in a queue or a stack (go
down at each level).
Recursive
Implementation
Without Separate
Nodes
Benefit of a No Node Class:
- Simplicity
- Implement all operations recursively
Benefit of an Inner Node Class:
- Conceptually think about nodes
Benefit of Separate Node Class:
- Reusable code at the cost of a more complicated design
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Project v final submission is due thursday, april 26. The contribution report and ethics discussion are both due sunday, april 29. Opendsa homework on trees is due monday, april 30. Individual design homework is due monday, april 30 (review vending uml). Use breakpoint properties and add a condition if you want to view iteration. 290, for example (such that i == 200). Edge: the side branches of a tree. Children: the descendants of a higher node. Leaves: termini of the tree (at the bottom) the base case of the tree. Subtree: every tree is made up of a subtree. Height: the number of levels in a tree. Full tree (binary tree): every parent has two children. Complete tree (binary tree): it is full except for on the last level and is filled from left to right. Balanced tree: the nodes are spread evenly across the tree with no more than a one level difference.
