22 2 Trees 22 3 Trees Previously we ve talked about how to store objects in a linear Introduction to Programming II Trees sequence Arrays ArrayLists LinkedLists Trees are a useful recursive data structure If we keep them sorted we can find elements more quickly than in a list examples A These are nice when we care about keeping everything in Chris Brooks B A C B order Department of Computer Science Finding particular elements can take a while though D C E University of San Francisco D F A B D Department of Computer Science University of San Francisco p 1 22 4 Tree Terminology Department of Computer Science University of San Francisco p 2 22 5 Implementing a tree E F G Department of Computer Science University of San Fra 22 6 Implementing a tree A struct representing a tree containing strings Parent Child C Since C doesn t have constructors it s often helpful to make them ourselves Leaf node typedef struct treeNode treeptr Root node Make a method called makeNode that takes a string as input and returns a new treeNode typedef struct treeNode char data treeptr left treeptr right treeNode Edge between nodes Path Ancestor Descendant Depth of a node n Length of path from root to n We need to declare a type called treeptr because otherwise the C compiler doesn t know what a treeNode is until the definition is processed Height of a tree Depth of deepest node 1 Department of Computer Science University of San Francisco p 4 Department of Computer Science University of San Francisco p 5 Department of Computer Science University of San Fra 22 7 Binary Search Trees 22 9 Finding a node 22 8 Adding methods to BST Binary Trees For each node n value stored at node n value stored in left void insert treeptr root char newdata treeNode newNode subtree First the Base Case when is it easy to determine if an element is stored in a Binary Search Tree if strcmp root data newdata 0 if root left NULL newNode makeNode newdata root left newNode return else return insert root left newdata else if root right NULL newNode makeNode newdata root right newNode return else return insert root right newdata For each node n value stored at node n value stored in right subtree Department of Computer Science University of San Francisco p 7 22 10 Finding an Element in a BST Department of Computer Science University of San Francisco p 8 22 11 Finding an Element in a BST First the Base Case when is it easy to determine if an element is stored in a Binary Search Tree If the tree is empty then the element can t be there If the element is stored at the root then the element is there Department of Computer Science University of San Francisco p 10 Department of Computer Science University of San Fra 22 12 Finding an Element in a BST Next the Recursive Case how do we make the problem smaller Next the Recursive Case how do we make the problem smaller Both the left and right subtrees are smaller versions of the problem Which one do we use Department of Computer Science University of San Francisco p 11 Department of Computer Science University of San Fran 22 13 Finding an Element in a BST 22 14 Finding an Element in a BST Next the Recursive Case how do we make the problem smaller Both the left and right subtrees are smaller versions of the problem Which one do we use If the element we are trying to find is the element stored at the root use the left subtree Otherwise use the right subtree 22 15 Finding an Element in a BST Next the Recursive Case how do we make the problem smaller Both the left and right subtrees are smaller versions of the problem Which one do we use If the element we are trying to find is the element stored at the root use the left subtree Otherwise use the right subtree How do we use the solution to the subproblem to solve the original problem Department of Computer Science University of San Francisco p 13 To find an element e in a Binary Search Tree T smaller Both the left and right subtrees are smaller versions of the problem Which one do we use If the element we are trying to find is the element stored at the root use the left subtree Otherwise use the right subtree How do we use the solution to the subproblem to solve the original problem The solution to the subproblem is the solution to the original problem this is not always the case in recursive algorithms Department of Computer Science University of San Francisco p 14 22 17 Exercise 22 16 Finding an Element in a BST Next the Recursive Case how do we make the problem Department of Computer Science University of San Fran 22 18 Searching in trees Implement the find treeNode root char object method If T is empty then e is not in T Write a main that inserts names into the tree and tests find If the root of T contains e then e is in T Count how many recursive calls it takes to find something If e the element stored in the root of T Look for e in the left subtree of T How is this related to the number of elements in the tree So how long does it take to find something in a tree What if the tree is perfectly balanced What if it s completely unbalanced Otherwise Look for e in the right subtree of T Department of Computer Science University of San Francisco p 16 Department of Computer Science University of San Francisco p 17 Department of Computer Science University of San Fran 22 19 Counting nodes 22 20 Counting nodes So how would we count the number of nodes in a tree 22 21 Counting leaves How would we change node counting to only count the number If the tree is null return 0 Otherwise return 1 the number of nodes in the left subtree of leaves Add a countLeaves treeNode root function the number of nodes in the right subtree Exercise add a countNodes treeNode root function to our tree data structure Department of Computer Science University of San Francisco p 19 22 22 Tree traversals Department of Computer Science University of San Francisco p 20 22 23 Tree traversals Many times when working with a tree you need to visit every single node in a particular order For example how would we print out all of the names in alphabetical order 22 24 In order traversal Many times when working with a tree you need to visit every single node in a particular order For example how would we print out all of the names in alphabetical order Want to first visit the leftmost child then its parent then that parent s right child This is called an in order traversal Department of Computer Science University of San Francisco p 22 Department of Computer Science University …
View Full Document
Unlocking...