DOC PREVIEW
USF CS 245 - Tree Operations

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

{small lecturenumber - heblocknumber :} Binary Tree Definitionaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Binary Tree Access Methodsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tree Operations -- Heightaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tree Operations -- Heightaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tree Operations -- NumNodesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tree Operations -- NumNodesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Writing Tree Functionsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tree Operations -- NumLeavesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tree Operations -- NumLeavesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Tree Traversalsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} PREORDER Traversaladdtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} PREORDER Traversaladdtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Printing Binary Treesaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} INORDER Traversaladdtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} POSTORDER Traversaladdtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} POSTORDER Traversaladdtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Expression Tree Valueaddtocounter {blocknumber}{1}Data Structures and AlgorithmsCS245-2014S-07Tree OperationsDavid GallesDepartment of Computer ScienceUniversity of San Francisco07-0: Binary Tree Definitionclass Node {Node() { }Node(Comparable elem) {this.element = element;}Node(Object element, Node left, Node right) {this.element = element;this.left = left;this.right = right;}/* Access methods on next slide */private Node left;private Node right;private Comparable element;}07-1: Binary Tree Access MethodsNode left() { void setLeft(Node left) {return left; this.left = left;} }Node right() { void setRight(Node right) {return right; this.right = right;} }Comparable element() {return element;}void setElement(Comparable element) {this.element = element;}07-2: Tree Operations – HeightReturns the height of the tree(Length of the path to the deepest leaf) + 1Height = 5 Height = 607-3: Tree Operations – Heightint height(Node tree) {if (tree == null)return 0;return 1 + MAX(height(tree.left()),height(tree.right()));}07-4: Tree Operations – NumNodesReturns the number of nodes in a treeNumber of Nodes = 8 Number of Nodes = 607-5: Tree Operations – NumNodesint numNodes(Node tree) {if (tree == null)return 0;return 1 + numNodes(tree.left(),tree.right());07-6: Writing Tree Functions123451234 567 891011 121314 15832 45Tree1Tree2Tree3Write find, numLeaves, shallowestleaf07-7: Tree Operations – NumLeavesReturns the number of leaves in a treeNumber of Leaves = 4 Number of Leaves = 107-8: Tree Operations – NumLeavesint numLeaves(Node tree) {if (tree == null)return 0;if ((tree.left() == null) &&(tree.right() == null))return 1;return numLeaves(tree.left()) +numLeaves(tree.right());}07-9: Tree TraversalsPREORDER TraversalDo operation on root of the treeTraverse left subtreeTraverse right subtreeINORDER TraversalTraverse left subtreeDo operation on root of the treeTraverse right subtreePOSTORDER TraversalTraverse left subtreeTraverse right subtreeDo operation on root of the tree07-10: PREORDE R TraversalPrinting out trees (Showing the shape of the tree in theprintout)AB CE FGABCEGHHDDF07-11: PREORDE R TraversalPrinting out trees (Showing the shape of the tree in theprintout)First print the root at current indent levelPrint the left subtree with larger indentationPrint the right subtree with larger indentation07-12: Printing Binary Treesvoid print(Node tree, int indent) {if (tree != null) {for(int i=0; i<indent; i++) {System.out.print("\t");System.out.println(tree.element().toString());print(tree.left(), indent + 1);print(tree.right(), indent + 1);}07-13: INORDER TraversalPrinting all elements in a Binary Search Tree in order(Already covered in previous slides)07-14: POSTORDER TraversalCalculating the Value of an expression tree+3 *+53207-15: POSTORDER TraversalCalculating the Value of an expression treeBase case:Return value stored at leafRecursive case:Calculate value of left subtreeCalculate value of right subtreeCalculate expression value07-16: Expression Tree Valueint value(Node tree) {if (tree.left() == null && tree.right() == null)return ((Integer) tree.element()).intValue();int left = value(tree.left());int right = value (tree.right());char op = ((Character) tree.element()).charValue();switch (op) {case ’+’:return left + right;case ’*’:return left *


View Full Document

USF CS 245 - Tree Operations

Download Tree Operations
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 Tree Operations 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 Tree Operations 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?