Kĩ thuật lập trình - Binary trees

Binary TreesCopyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Learn about binary treesLearn how to represent and handle a binary tree using the TreeNode classLearn about binary search treesReview sets and maps, and the java.util classes that implement them2Some Applications of TreesData retrieval (search)Priority queuesDecision systemsHierarchiesGames3Binary Tree TermsRootLeaves (nodes with no children)Left childRight childNumber of levels (equals 5 here)nodenode’s right subtree4Binary Tree PropertiesA shallow tree can hold many nodes. For example, a binary tree with 20 levels can have 220 - 1 (approximately 1,000,000) nodes.At each node a decision can be made on where to proceed, left or right (used in binary search trees).The path to the bottom is relatively short as compared to the total number of nodes.5The TreeNode ClassRepresents a node of a binary treeIs similar to ListNode (Chapter 21) only instead of next has left and rightpublic class TreeNode{ private Object value; private TreeNode left; private TreeNode right; ...Holds a reference to the left childHolds a reference to the right child6The TreeNode Class (cont’d) ... // Constructors: public TreeNode (Object v) { value = v; left = null; right = null; } public TreeNode (Object v, TreeNode lt, TreeNode rt) { value = v; left = lt; right = rt; } // Methods: public Object getValue ( ) { return value; } public TreeNode getLeft ( ) { return left; } public TreeNode getRight ( ) { return right; } public void setValue (Object v) { value = v; } public void setLeft (TreeNode lt) { left = lt; } public void setRight (TreeNode rt) { right = rt; }}7Trees and RecursionThe tree structure is recursive by nature — the left and right subtrees are smaller trees: private void traverse (TreeNode root) { // Base case: root == null, // the tree is empty -- do nothing if (root != null) // Recursive case { process (root.getValue ( )); traverse (root.getLeft ( )); traverse (root.getRight ( )); } }8TreeNode Example 1 public int countNodes (TreeNode root) { if (root == null) return 0; else return 1 + countNodes (root.getLeft ( )) + countNodes (root.getRight ( )); }(for the root)Base case9TreeNode Example 2 // returns a reference to a new tree, which is a // copy of the tree rooted at root public TreeNode copy (TreeNode root) { if (root == null) return null; else return new TreeNode (root.getValue ( ), copy (root.getLeft ( )), copy (root.getRight ( ))); }10 private void traversePreorder (TreeNode root) { if (root != null) { process (root.getValue()); traversePreorder (root.getLeft( )); traversePreorder (root.getRight( )); } }TraversalsPreorder: first process the root, then traverse the left and right subtrees.A/ \B C / \ D EA B D E C11 private void traverseInorder (TreeNode root) { if (root != null) { traverseInorder (root.getLeft( )); process (root.getValue( )); traverseInorder (root.getRight( )); } }Traversals (cont’d)Inorder: first traverse the left subtree, then process the root, then traverse the right subtree.A/ \B C / \ D ED B E A C12 private void traversePostorder (TreeNode root) { if (root != null) { traversePostorder (root.getLeft( )); traversePostorder (root.getRight( )); process (root.getValue( )); } }Traversals (cont’d)Postorder: first traverse the left and right subtrees, then process the root.A/ \B C / \ D ED E B C A13Traversals (cont’d)Preorder: root  left  rightInorder: left  root  rightPostorder: left  right  root12331221314Binary Search Trees (BST)BST contains Comparable objects (or a comparator is supplied).For each node, all the values in its left subtree are smaller than the value in the node and all the values in its right subtree are larger than the value in the node. 15 / \ 8 20 / \ 1 12 15 / \ 12 20 / \ 1 8a BSTnot a BST15BST (cont’d)BSTs combine the benefits of sorted arrays for quick searching and linked lists for inserting and deleting values.16 // root refers to a BST; the nodes hold Strings private boolean contains (TreeNode root, String target) { if (root == null) return false; int diff = target.compareTo ((String) root.getValue ( )); if (diff == 0) return true; else if (diff 0) return contains (root.getRight ( ), target); }BST (cont’d)Recursive contains17 private boolean contains (TreeNode root, String target) { TreeNode node = root; while ( node != null ) { int diff = target.compareTo (node.getValue ()); if (diff == 0) return true; else if (diff 0 node = node.getRight (); } return false; }BST (cont’d)Iterative contains18A BST Classpublic class MyTreeSet{ private TreeNode root; ... private boolean contains (Object target) { return contains (root, target); } private boolean contains (TreeNode root, Object target) { if (root == null) return false; ... } ...}Private recursive helper method19BST (cont’d)The smallest nodeThe largest node20Adding a Node private TreeNode add (TreeNode node, Object value) { if (node == null) node = new TreeNode(value); else { int diff = ((Comparable)value).compareTo (root.getValue( )); if (diff 0) root.setRight (add (root.getRight( ), value)); } return node; }Private recursive helper method21BST: Removing the Root Node503025602075407090697250302560207540709069725030256020754070906972Step 1:Find the smallest node of the right subtree Step 2:Unlink that node and promote its right child into its placeStep 3:Link that note in place of the root and remove the old root22BST (cont’d)When the tree is balanced (“bushy”) the add, remove, and contains methods take O(log n) time, where n is the number of nodes in the tree.If nodes are added randomly, the BST can degenerate into a nearly linear shape. More sophisticated algorithms help keep the tree balanced.23java.util.TreeSetIs implemented as a balanced BST.compareTo (or comparator’s compare) is used by the add, contains, and remove methods.An iterator returned by the iterator method implements inorder traversal.Inorder traversal of any BST retrieves values in ascending order.24java.util.TreeSet (cont’d)Never mind...25java.util.TreeMapIs implemented as a BST for keys.compareTo (or comparator’s compare) for keys is used by the put, get, containsKey, and remove methods.The keySet method returns a TreeSet.26java.util.TreeMap (cont’d)27Review:Name a few applications of trees.Why is recursion applicable to trees?What is a leaf of a tree?What is a subtree?Which property makes binary trees suitable for data retrieval applications?28Review (cont’d):What is the largest possible number of nodes in a binary tree with 10 levels?Can the TreeNode class be used to represent a node in a doubly-linked list?What is the sequence of values in preorder and postorder traversals of the following tree? A / \ B C / \ D E29Review (cont’d):What is a Binary Search Tree?Inorder traversal of a BST has a neat property. What is it?Which of the following trees are BSTs? 3 / \ 1 5 / \ 2 4 1 / \ 2 3 / \ 4 5 4 / \ 2 5 / \ 1 330