Understanding Binary Trees in Computer Science
Binary trees are a fundamental data structure in computer science with various applications. This content covers the basics of binary trees, including terminology, recursive definitions, node structures, and implementations in computer science. It touches on important concepts such as recursion, tree traversal, and tree node properties. Examples and images are provided to aid in understanding the concepts presented.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CS 143 Lecture 10: Binary Trees Thanks to Marty Stepp and Stuart Reges for parts of these slides
Recursion Review What do we always need when writing a recursive function? Base case Recursive case 2
Trees tree: A directed, acyclic structure of linked nodes. directed : Has one-way links between nodes. acyclic : No path wraps back around to the same node twice. binary tree: One where each node has at most two children. root Recursive definition: A tree is either: empty (null), or a root node that contains: 1 data, a left subtree, and 2 3 a right subtree. (The left and/or right subtree could be empty.) 4 5 6 7 3
Trees in computer science TreeMap and TreeSet implementations folders/files on a computer family genealogy; organizational charts AI: decision trees = compilers: parse tree a = (b + c) * d; a * cell phone T9 + d b c 4
Terminology node: an object containing a data value and left/right children root: topmost node of a tree leaf: a node that has no children branch: any internal node; neither the root nor a leaf parent: a node that refers to this one child: a node that this node refers to sibling: a node with a common parent root height = 3 1 level 1 subtree: the smaller tree of nodes on the left or right of the current node height: length of the longest path from the root to any node level or depth: length of the path from a root to a given node 2 3 level 2 4 5 6 7 level 3 5
Recursive data structure Recursive definition: A tree is either: empty (null), or a root node that contains: data, a left tree, and a right tree root root root root root 1 1 1 1 3 2 3 7 6
A tree node for integers A basic tree node object stores data, refers to left/right Multiple nodes can be linked together into a larger tree left data right 42 left data right 59 left data right 27 left data right 86 7
IntTreeNode class // An IntTreeNode object is one node in a binary tree of ints. public class IntTreeNode { public int data; // data stored at this node public IntTreeNode left; // reference to left subtree public IntTreeNode right; // reference to right subtree // Constructs a leaf node with the given data. public IntTreeNode(int data) { this(data, null, null); } // Constructs a branch node with the given data and links. public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) { this.data = data; this.left = left; this.right = right; } } left data right 8
IntTree class // An IntTree object represents an entire binary tree of ints. public class IntTree { private IntTreeNode overallRoot; // null for an empty tree methods } overallRoot 1 Client code talks to the IntTree, not to the node objects inside it. 2 3 Methods of the IntTree create and manipulate the nodes, their data and links between them. 4 5 6 7 9
IntTree constructors For now, assume we have the following constructors: public IntTree(IntTreeNode overallRoot) public IntTree(int height) The 2nd constructor will create a tree and fill it with nodes with random data values from 1-100 until it is full at the given height. overallRoot 17 IntTree tree = new IntTree(3); 41 9 29 6 81 40 10
Traversals traversal: An examination of the elements of a tree. A pattern used in many tree algorithms and methods Common orderings for traversals: pre-order: process root node, then its left/right subtrees in-order: process left subtree, then root node, then right post-order: process left/right subtrees, then root node overallRoot 17 41 9 29 6 81 40 11
Traversal example overallRoot 17 41 9 29 6 81 40 pre-order: in-order: post-order: 17 41 29 6 9 81 40 29 41 6 17 81 9 40 29 6 41 81 40 9 17 12
Traversal trick overallRoot To quickly generate a traversal: Trace a path around the tree. As you pass a node on the proper side, process it. 17 41 9 pre-order: left side in-order: bottom post-order: right side 29 6 81 40 pre-order: in-order: post-order: 17 41 29 6 9 81 40 29 41 6 17 81 9 40 29 6 41 81 40 9 17 13
Exercise overallRoot Give pre-, in-, and post-order traversals for the following tree: 42 15 9 27 86 3 48 12 39 pre: in: 15 48 27 42 86 5 12 9 3 39 post: 48 27 15 5 12 86 39 3 42 42 15 27 48 9 86 12 5 3 39 5 14
Exercise Add a method print to the IntTree class that prints the elements of the tree, separated by spaces. A node's left subtree should be printed before it, and its right subtree should be printed after it. overallRoot Example: tree.print(); 17 29 41 6 17 81 9 40 41 9 29 6 81 40 15
Exercise solution // An IntTree object represents an entire binary tree of ints. public class IntTree { private IntTreeNode overallRoot; // null for an empty tree ... public void print() { print(overallRoot); System.out.println(); // end the line of output } private void print(IntTreeNode root) { // (base case is implicitly to do nothing on null) if (root != null) { // recursive case: print left, center, right print(overallRoot.left); System.out.print(overallRoot.data + " "); print(overallRoot.right); } } } 16
Template for tree methods public class IntTree { private IntTreeNode overallRoot; ... public typename(parameters) { name(overallRoot, parameters); } private typename(IntTreeNode root, parameters) { ... } } Tree methods are often implemented recursively with a public/private pair the private version accepts the root node to process 17
Exercise Add a method contains to the IntTree class that searches the tree for a given integer, returning true if it is found. If an IntTree variable tree referred to the tree below, the following calls would have these results: overallRoot tree.contains(87) true tree.contains(60) true tree.contains(63) false tree.contains(42) false 55 87 29 -3 42 60 60 18
Exercise solution // Returns whether this tree contains the given integer. public boolean contains(int value) { return contains(overallRoot, value); } private boolean contains(IntTreeNode node, int value) { if (node == null) { return false; // base case: not found here } else if (node.data == value) { return true; // base case: found here } else { // recursive case: search left/right subtrees return contains(node.left, value) || contains(node.right, value); } } 19
Exercise Add a method named printSideways to the IntTree class that prints the tree in a sideways indented format, with right nodes above roots above left nodes, with each level 4 spaces more indented than the one above it. Example: Output from the tree below: overall root 9 19 14 11 9 7 6 6 14 7 11 19 20
Exercise solution // Prints the tree in a sideways indented format. public void printSideways() { printSideways(overallRoot, ""); } private void printSideways(IntTreeNode root, String indent) { if (root != null) { printSideways(root.right, indent + " "); System.out.println(indent + root.data); printSideways(root.left, indent + " "); } } 21
Adding to a BST Suppose we want to add new values to the BST below. Where should the value 14 be added? overall root Where should 3 be added? 7? 8 If the tree is empty, where should a new value be added? 5 11 What is the general algorithm? 2 10 19 7 4 25 22 22
Change point, version 2 What is the state of the object referred to by p after this code? public static void main(String[] args) { Point p = new Point(1, 2); change(p); System.out.println(p); } 1 2 x y p public static void change(Point thePoint) { thePoint = new Point(3, 4); } // answer: (1, 2) 3 4 x y 28
Changing references If a method dereferences a variable (with . ) and modifies the object it refers to, that change will be seen by the caller. public static void change(Point thePoint) { thePoint.x = 3; // affects p thePoint.setY(4); // affects p If a method reassigns a variable to refer to a new object, that change will not affect the variable passed in by the caller. public static void change(Point thePoint) { thePoint = new Point(3, 4); // p unchanged thePoint = null; // p unchanged What if we want to make the variable passed in become null? 29
Change point, version 3 What is the state of the object referred to by p after this code? public static void main(String[] args) { Point p = new Point(1, 2); change(p); System.out.println(p); } 1 2 x y p public static Point change(Point thePoint) { thePoint = new Point(3, 4); return thePoint; } // answer: (1, 2) 3 4 x y 30
Change point, version 4 What is the state of the object referred to by p after this code? public static void main(String[] args) { Point p = new Point(1, 2); p = change(p); System.out.println(p); } 1 2 p x y public static Point change(Point thePoint) { thePoint = new Point(3, 4); return thePoint; } // answer: (3, 4) 3 4 x y 31
x = change(x); If you want to write a method that can change the object that a variable refers to, you must do three things: 1. pass in the original state of the object to the method 2. return the new (possibly changed) object from the method 3. re-assign the caller's variable to store the returned result p = change(p); // in main public static Point change(Point thePoint) { thePoint = new Point(99, -1); return thePoint; We call this general algorithmic pattern x = change(x); also seen with strings: s = s.toUpperCase(); 32
Applying x = change(x) Methods that modify a tree should have the following pattern: old state of the node new state of the node input (parameter): output (return): parameter return node before node after your method In order to actually change the tree, you must reassign: node = change(node, parameters); node.left = change(node.left, parameters); node.right = change(node.right, parameters); overallRoot = change(overallRoot, parameters); 34
