Unformatted text preview:

COP 3540 Data Structures with OOPWhy Trees?Slide 3TreesSlide 5Slide 6Slide 7How Do Binary Search Trees Work?Unbalanced TreesTrees in Java CodeSlide 11Slide 12The Tree ClassSlide 14Slide 15Slide 16Sample Binary TreeJava Code for Inserting a NodeSlide 20Traversing the TreeInorder Traversal – Binary Tree (LNR Traversal)Java Code for Traversing – Inorder Recursive…Slide 24Priority: L-N-RSlide 26Pre-Order (NLR) and Post-Order (LRN) TraversalsCan see only the order of recursive calls is changed.Pre-Order and Post-order TraversalsSlide 30Post-Order Traversal – LRN.Evaluating a Postfix Notation – postorder traversal…Enter: Pseudo Code for Iterative Scans:Slide 34Slide 35Finding Maximum and Minimum Values1COP 3540 Data Structures with OOP Chapter 8 - Part 1Binary Trees2Why Trees?Trees are one of the fundamental data structures.Many real-world phenomena cannot be represented w/data structures we’ve had so far.Think of arrays:Easy to search, especially if ordered.•O(log2n) performance! Great. (binary search)Inserting; Deleting? Horrible if ordered. Must find item or place before actions.3Why Trees?How about Linked Lists?Inserts and deletes? Great. Take O(1) time – the best you can get! (if inserting / deleting from one end)Searching? Search to insert / delete/ change? Not nearly as good as O(1) or even O(log2n)! •On average, must search n/2 items!•Process requires O(n) time. •Ordering the linked list may help, as we must still search to find.4TreesFirst, trees in general.Consists of nodes connected by edges.Trees have indegree <=1, no cycles;•Implies one ‘path’ to a node.Trees with indegree > 1 and cycles = graphs.•More later on graphs.5TreesGeneral TreeEdges connect nodes.Only way to get to one node is along an indicated path (edges) and these are downward.Edges are represented in a program by ‘references;’ nodes as likely primitives or objects.One node at top of tree called the root. Can only have one root.Binary Trees have ‘outdegree’ <= 2 for ALL nodes.Multi-way tree can have outdegree >= 2 for at least one node (see above).rootedgenodeABECDFHG6TreesGeneral TreeParent: All nodes have exactly one parent.Child: Any node may have one or more lines coming from it: childrenBinary tree has at most two children emanating from a node.Leaf: node with no childrenSubtree: any node may be considered to be a root of a subtree, even leaves.Visiting: term used to indicate that a node is visited under program control – usually to process the data at that node. Merely passing over a node does not constitute a visit.Traversing: refers to visiting all nodes in a tree in a prescribed manner.Levels: start with level 0.Keys: normally what is displayed on the tree, like A, B, C, … above.rootedgenodeABECDFHG7TreesBinary TreeBinary Tree: every node has no more than two children.A child node is called a left child or right child, but may, in turn, be the root of a subtree!A node in a binary tree may have no children.We normally talk in terms of binary search trees.In theory (logical; abstraction), can exist to any number of levels; in practice (i.e. implementation), can run out of memory space.rootedgenodeABEDFHG8How Do Binary Search Trees Work?Need to carry out basic tree operations such as finding a node, traversing a tree (get around in the tree), adding a node, deleting a node, etc. This is what this chapter is all about.9Unbalanced TreesrootADFHGNote: tree is ‘unbalanced.’This means nodes are mostly on one side or the other.Tree may be nearly balanced until certain levelsThen, it may become quite unbalanced. Skewed.Trees can become unbalanced due to the way they were created.Generally, they are more balanced, if randomly developed.Greatly prefer balanced trees. Have very welcome properties Unbalanced trees present problems in efficiently processing them.Red-Black trees address unbalanced trees (further ahead).10Trees in Java CodeSo, how do we implement binary trees in Java?Normally, we will store the nodes at unrelated places in memory with references to children as we are accustomed to do.Can also represent a tree in memory as an array, with children located in specific positions within this array.Will look later at this.Let’s look at some code segments now.11We need a class of node objects.These will contain appropriate data and up to two references to children (can have MORE, as we shall see later…)The Node Classclass Node{int iData; // data used as key valuedouble fData // other dataNode leftChild; // this node’s left childNode rightChild; // this node’s right child. public void displayNode(){// whatever…}// end display()} // end class Node.12Sometimes the data might be objects rather than primitives, and better simply referenced in the Node itself.class Node{Person p; // reference to a person object Node leftChild; // this node’s left childNode rightChild; // this node’s right child. public void displayNode(){// whatever…}// end display()} // end class Node.class Person{int iData;double fData; …} // end class person13The Tree ClassNeed a tree class from which a tree object can be instantiated.Will call class Tree with one field: a Node variable that references the root.Identical to ‘first’ and ‘last’ for linked lists…(get started)Also, since we do not allocate the entire structure at one time (like an array), we can ONLY have a pointer to the first element or root.Consider the basic format of a Tree class:14 class Tree {private Node root; // only data field in Tree; but key!public void find (int key){ // stub: not showing details of this method here}// end find()public void insert (int id, double dd){ // stub; placeholder}// end insert()pubic void delete (int id){ // stub}// end delete() } // end class Tree.Tree Class15 class TreeApp { public static void main (String [ ] args){Tree theTree = new Tree; // make a tree. // creates an object of type Tree. (previous slide) theTree.insert (50, 1.5); //insert three nodestheTree.insert(25, 1.7); // invoking tree methods…theTree.insert(75, 1.9); // no implementations shown yet.Node found = theTree.find(25); // find node with key 25if (found != null) // So what does this do???System.out.println (“Found the node with key 25”);elseSystem.out.pirntln(“ Could not find node with key 25”);// end main() } //


View Full Document

UNF COP 3540 - Binary Trees

Download Binary 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 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 Binary 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?