false

Class Notes
(838,386)

Canada
(510,872)

University of Waterloo
(18,599)

Computer Science
(798)

CS 234
(31)

Robert Sproule
(8)

Lecture

Unlock Document

Computer Science

CS 234

Robert Sproule

Summer

Description

CS 234 – Lecture 12, Binary Trees and Heaps
June 13, 2013
Binary Trees:
• Binary Trees are another
representation of data that we can use, sometimes more effectively than, say, a
Python list or a linked list
Some important features of a tree are:
• Root (A)
• Left Child (B is the left child of A)
• Right Child (E is the right child of
B)
• Siblings (D and E are siblings)
• Interior Nodes (B is an interior
Node)
• Height (The number of levels –
height 4)
• Depth (A is depth 0, F is depth 2)
• Ancestors (The ancestors of E are B and A)
• Descendants (The des. of C are F and H)
• Special Types of Binary Trees:
o Full Binary Tree – every node has either ZERO or TWO children
o Perfect Binary Tree – all leaves are at the SAME level
o Complete Binary Tree – all levels besides the last are full, and the last
level has all nodes as far to the left as possible NOTE: A perfect binary tree is both full and complete
• Properties of Binary Trees:
o A perfect binary tree of height h has exactly 2 – 1 nodes
Ex. A perfect tree of height 4 would have 15 nodes
o A perfect binary tree of size n has a height of log 2n+1)
Ex. A perfect tree of size 31 would have height 5
h-1 h
o A complete binary tree of height h has a size n such that 2 <= n <= 2 – 1
• Memory Model of a Tree
A tree is stored in data in a manner similar to that of a
linked list. We declare a node structure with 3+ fields,
including a data field, as well as a field for both left and
right subtrees. The left and right hold other nodes, or
None if that child is empty. This forms the recursive tree
structure. The data field holds whatever information you
wish to store in your tree.
The figure to the left shows the root node and both of its
children in memory. The next level of the tree could have
up to 4 nodes. • Tree Traversals
o The traversal of a tree is iteration over the nodes of the tree, one at a time.
Different types of iterations would be used for different purposes. We define
these iterations into two main classes
o Depth First Traversal:
Pre-Order Traversal – we analyze the root node first, then traverse the
left subtree, then traverse the right subtree (the root becomes FIRST)
In-Order Traversal – we traverse the left subtree first, then the root node,
then traverse the right subtree (in ORDER from left to right)
Post-Order Traversal – we traverse the left subtree first, then the right
subtree, then the root node (the root becomes LAST)
o Breadth First Traversal:
We visit the nodes from top to bottom, left to right
This is much harder to code than the depth first traversals; while depth
first can

More
Less
Related notes for CS 234

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.