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