UAF CS 311 - Introduction to Trees Binary Trees (33 pages)

Previewing pages 1, 2, 15, 16, 17, 32, 33 of 33 page document View the full content.
View Full Document

Introduction to Trees Binary Trees



Previewing pages 1, 2, 15, 16, 17, 32, 33 of actual document.

View the full content.
View Full Document
Unformatted text preview:

Introduction to Trees Binary Trees CS 311 Data Structures and Algorithms Lecture Slides Wednesday November 11 2009 Glenn G Chappell Department of Computer Science University of Alaska Fairbanks CHAPPELLG member ams org 2005 2009 Glenn G Chappell Unit Overview Handling Data Sequences Major Topics Data abstraction Introduction to Sequences Smart arrays Array interface Basic array implementation Exception safety Allocation efficiency Generic containers Linked Lists Node based structures More on Linked Lists E N DO Sequences in the C STL Stacks Queues 11 Nov 2009 CS 311 Fall 2009 2 Review Stacks A Stack is 1 Start Empty Stack A kind of container A Last In First Out LIFO structure A restricted version of a Sequence 2 Push 2 Conceptually a Stack carries out the idea of top down design Three primary operations push pop getTop 3 Push 7 4 Pop A Stack can be implemented simply as a wrapper around some existing Sequence type 7 2 2 5 Pop Empty again 6 Push 5 11 Nov 2009 2 CS 311 Fall 2009 5 3 Review Queues A Queue is A kind of container A restricted version of a Sequence First In First Out FIFO Conceptually a Queue carries out the idea of waiting in line Three primary operations enqueue dequeue getFront 1 Start Empty Queue 2 Enqueue 2 3 Enqueue 7 4 Dequeue A Queue can be implemented As a wrapper around some existing Sequence type Using a circular buffer 5 Dequeue Empty again 6 Enqueue 5 11 Nov 2009 CS 311 Fall 2009 F F F F F F B 2 2 7 B 7 B B B 5 B 4 Review Where Are We The Big Problem Our problem for much of the rest of the semester Store a collection of data items all of the same type Operations Access items one item retrieve find all items traverse Add new item insert Eliminate existing item delete All this needs to be efficient in both time and space A solution to this problem is a container Generic containers those in which client code can specify the type of data stored 11 Nov 2009 CS 311 Fall 2009 5 Unit Overview The Basics of Trees Major Topics Introduction to Trees Binary Trees Binary Search Trees Treesort 11 Nov 2009 CS 311 Fall 2009 6 Introduction to Trees What is a Tree By a tree mathematicians mean a structure like this Each dot is called a vertex note the Latin plural vertices or a node I will use vertex for the element of the tree as a conceptual object and node for the small data substructure representing it Each line is called an edge Each edge joins two vertices A tree is connected all one piece and there are no cycles 11 Nov 2009 CS 311 Fall 2009 7 Introduction to Trees Rooted Trees Introduction Often we use trees to represent hierarchical structures We place one vertex at the top and we call it the root Each other vertex of the tree hangs from some vertex The result is a rooted tree From now on in this class tree means rooted tree 11 Nov 2009 CS 311 Fall 2009 root 8 Introduction to Trees Rooted Trees Terminology 1 5 Some of the terminology for rooted trees comes from plants Root is an obvious example Another A vertex with nothing hanging off of it is called a leaf Leaves are shown in green What if a tree has just one vertex 11 Nov 2009 CS 311 Fall 2009 9 Introduction to Trees Rooted Trees Terminology 2 5 Other terminology comes from family trees To illustrate this we label a vertex v in the tree at right The vertex that v hangs from shown in red is v s parent Every vertex except the root has exactly one parent v The vertices that hang from v shown in blue are v s children A leaf has no children The other children of v s parent shown in orange are v s siblings 11 Nov 2009 CS 311 Fall 2009 10 Introduction to Trees Rooted Trees Terminology 3 5 The parent of v and its parent and its parent etc are v s ancestors These are shown in red v s children and their children and their children etc are v s descendants v These are shown in blue 11 Nov 2009 CS 311 Fall 2009 11 Introduction to Trees Rooted Trees Terminology 4 5 The vertices of a rooted tree come in levels The root is at level 1 Each other vertex has a level 1 greater than its parent Level 3 which includes v is shown in orange We often draw vertices at the same level in a horizontal row 1 2 3 v 4 5 The height of a tree is the number of levels 6 This tree has height 8 Note Some people define height slightly differently 7 8 11 Nov 2009 CS 311 Fall 2009 12 Introduction to Trees Rooted Trees Terminology 5 5 A subtree consists of a node and all its descendants Given a node n the subtree rooted at n consists of n and all its descendants Given a node n a subtree of n is a subtree rooted at some child of n Shown in green is a subtree of v It is the subtree rooted at v s child w 11 Nov 2009 CS 311 Fall 2009 v w 13 Introduction to Trees Rooted Trees General Trees A general tree is a somewhat more precise version of what we have been talking about A general tree consists of a node called the root and zero or more subtrees of the root each of which is a general tree Note that a general tree must have at least one node The above is a recursive definition 11 Nov 2009 CS 311 Fall 2009 14 Binary Trees Overview Our next ADT is Binary Tree We will cover What a Binary Tree is Three special kinds Traversals Implementation Applications What is missing above Binary Trees in the C STL because there aren t any Not in the interface anyway They are used internally 11 Nov 2009 CS 311 Fall 2009 15 Binary Trees What a Binary Tree Is Idea A Binary Tree consists of a set T of nodes so that either T is empty no nodes or T consists of a node r the root and two subtrees of r each of which is a Binary Tree the left subtree and the right subtree a We make a strong distinction between left and right subtrees Sometimes we use them for very different things An empty Binary Tree is a Binary Tree with no nodes 11 Nov 2009 CS 311 Fall 2009 a b b Different Binary Trees Empty Binary Tree 16 Binary Trees What a Binary Tree Is ADT Data A set of nodes Operations Create empty Create given a root and two subtrees Destroy isEmpty getRootData setRootData Access to data in root node attachLeft attachRight Attach a child to the root attachLeftSubtree attachRightSubtree Attach a subtree to the root detachLeftSubtree detachRightSubtree Detach a subtree from the root leftSubtree rightSubtree Returns a subtree preorderTraverse inorderTraverse postorderTraverse …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Introduction to Trees Binary Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Trees Binary Trees and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?