Unformatted text preview:

small lecturenumber - hepage : Treessmall lecturenumber - hepage : Treessmall lecturenumber - hepage : Tree Terminologysmall lecturenumber - hepage : Implementing a treesmall lecturenumber - hepage : Implementing a treesmall lecturenumber - hepage : Binary Search Treessmall lecturenumber - hepage : Adding methods to BSTsmall lecturenumber - hepage : Finding a nodesmall lecturenumber - hepage : Finding an Element in a BSTsmall lecturenumber - hepage : Finding an Element in a BSTsmall lecturenumber - hepage : Finding an Element in a BSTsmall lecturenumber - hepage : Finding an Element in a BSTsmall lecturenumber - hepage : Finding an Element in a BSTsmall lecturenumber - hepage : Finding an Element in a BSTsmall lecturenumber - hepage : Finding an Element in a BSTsmall lecturenumber - hepage : Exercisesmall lecturenumber - hepage : Searching in treessmall lecturenumber - hepage : Counting nodessmall lecturenumber - hepage : Counting nodessmall lecturenumber - hepage : Counting leavessmall lecturenumber - hepage : Tree traversalssmall lecturenumber - hepage : Tree traversalssmall lecturenumber - hepage : In order traversalsmall lecturenumber - hepage : ExerciseIntroduction to Programming IITreesChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p. 1/??22-2: Trees•Previously, we’ve talked about how to store objects in a linearsequence.◦Arrays◦ArrayLists◦LinkedLists•These are nice when we care about keeping everything inorder.•Finding particular elements can take a while, though.Department of Computer Science — University of San Francisco – p. 2/??22-3: Trees•Trees are a useful recursive data structure.•If we keep them sorted, we can find elements more quickly thanin a list.•examples:AB CD EFABCDAB CF GD EDepartment of Computer Science — University of San Francisco – p. 3/??22-4: Tree Terminology•Parent / Child•Leaf node•Root node•Edge (between nodes)•Path•Ancestor / Descendant•Depth of a node n◦Length of path from root to n•Height of a tree◦(Depth of deepest node) + 1Department of Computer Science — University of San Francisco – p. 4/??22-5: Implementing a tree•A struct representing a tree containing strings:typedef struct treeNode*treeptr;typedef struct treeNode {char*data;treeptr left;treeptr right;} treeNode;•We need to declare a type called ’treeptr’, because otherwisethe C compiler doesn’t know what a treeNode is until thedefinition is processed.Department of Computer Science — University of San Francisco – p. 5/??22-6: Implementing a tree•Since C doesn’t have constructors, it’s often helpful to makethem ourselves.•Make a method called makeNode that takes a string as inputand returns a new treeNode.Department of Computer Science — University of San Francisco – p. 6/??22-7: Binary Search Trees•Binary Trees•For each node n, (value stored at node n) > (value stored in leftsubtree)•For each node n, (value stored at node n) < (value stored inright subtree)Department of Computer Science — University of San Francisco – p. 7/??22-8: Adding methods to BSTvoid insert(treeptr root, char*newdata) {treeNode*newNode;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);}}}Department of Computer Science — University of San Francisco – p. 8/??22-9: Finding a node•First, the Base Case – when is it easy to determine if anelement is stored in a Binary Search Tree?Department of Computer Science — University of San Francisco – p. 9/??22-10: Finding an Element in a BST•First, the Base Case – when is it easy to determine if anelement 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 thereDepartment of Computer Science — University of San Francisco – p. 10/??22-11: Finding an Element in a BST•Next, the Recursive Case – how do we make the problemsmaller?Department of Computer Science — University of San Francisco – p. 11/??22-12: Finding an Element in a BST•Next, the Recursive Case – how do we make the problemsmaller?◦Both the left and right subtrees are smaller versions of theproblem. Which one do we use?Department of Computer Science — University of San Francisco – p. 12/??22-13: Finding an Element in a BST•Next, the Recursive Case – how do we make the problemsmaller?◦Both the left and right subtrees are smaller versions of theproblem. Which one do we use?◦If the element we are trying to find is < the element storedat the root, use the left subtree. Otherwise, use the rightsubtree.Department of Computer Science — University of San Francisco – p. 13/??22-14: Finding an Element in a BST•Next, the Recursive Case – how do we make the problemsmaller?◦Both the left and right subtrees are smaller versions of theproblem. Which one do we use?◦If the element we are trying to find is < the element storedat the root, use the left subtree. Otherwise, use the rightsubtree.•How do we use the solution to the subproblem to solve theoriginal problem?Department of Computer Science — University of San Francisco – p. 14/??22-15: Finding an Element in a BST•Next, the Recursive Case – how do we make the problemsmaller?◦Both the left and right subtrees are smaller versions of theproblem. Which one do we use?◦If the element we are trying to find is < the element storedat the root, use the left subtree. Otherwise, use the rightsubtree.•How do we use the solution to the subproblem to solve theoriginal problem?◦The solution to the subproblem is the solution to the originalproblem (this is not always the case in recursive algorithms)Department of Computer Science — University of San Francisco – p. 15/??22-16: Finding an Element in a BSTTo find an element e in a Binary Search Tree T :•If T is empty, then e is not in T•If the root of T contains e, then e is in T•If e < the element stored in the root of T :◦Look for e in the left subtree of TOtherwise◦Look for e in the right subtree of TDepartment of Computer Science — University of San Francisco – p. 16/??22-17: Exercise•Implement the find(treeNode *root, char *object)


View Full Document

USF CS 112 - Trees

Documents in this Course
Structs

Structs

4 pages

Strings

Strings

27 pages

Queues

Queues

3 pages

Trees

Trees

24 pages

Arrays

Arrays

5 pages

ArrayList

ArrayList

24 pages

Stacks

Stacks

2 pages

Stacks

Stacks

8 pages

Trees

Trees

24 pages

Stacks

Stacks

8 pages

Queues

Queues

16 pages

Queues

Queues

17 pages

Queues

Queues

17 pages

Load more
Download Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 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 Trees 2 2 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?