Binary Trees
Embrace the elegance and power of binary trees in computer science through this engaging exploration. Uncover the intricate structures, traversal methods, and applications of binary trees. Discover how these fundamental data structures optimize operations, from searching to sorting, and enhance efficiency in algorithms. Dive into the depths of binary trees, from balanced to unbalanced variants, and grasp their significance in shaping modern computing landscapes.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Simple Recursion Questions (5 minutes) Write a function to compute the sum of just the positive numbers in an array of integers. First, solve the problem using iteration. Then, using the technique shown in this chapter, convert your iterative function to a recursive function. Write a function that is passed an array of integers and a target number and that returns the number of occurrences of the target in the array. Solve the problem first using iteration, then recursion.
Introduction In this lecture we will explore a new data structure known as a binary tree. Like linked lists, binary trees are composed of interconnected nodes. But unlike linked lists, which involve a one-dimensional (straight line or linear ) sequence, binary trees can branch in two directions, which gives them a two- dimensional structure (or non-linear ). Binary trees are linked structures, they share many of the useful properties of linked lists. It is fairly easy to grow or shrink a binary tree by rearranging the links of the nodes.
Introduction Firstly the basic binary tree terminology and basic binary tree operations will be explored, and then particular kind of binary tree known as a binary search tree will be introduced. Binary search trees are used to capture high/low relationships and provide an efficient structure for keeping track of data that have a natural ordering. As we study binary trees, we will find that recursion comes into play quite often. Many binary tree operations are best written recursively.
root Binary Tree Basics Simple binary tree of integer values. As we did with linked lists, we refer to each different data value as a node. This tree has a total of six nodes. Viewed upside down, the diagram looks more like a tree. At the bottom of this structure is a node storing the value 12. We refer to this value as the root of the tree. All nodes are connected either directly or indirectly to the root node. root
Basics In this diagram, the nodes that store the values 12, 18, and 7 have connections branching out and down. These nodes are referred to as branch nodes (internal nodes). The nodes storing the values 23, 4, and 13 are at the top (or if you consider tree as upside down bottom) of this tree and have nothing above (or below) them. They are referred to as leaf nodes or leaves of the tree. Internal Node Leaf Node
Definition of Binary Tree Binary Tree A binary tree is either 1. an empty tree or 2. a root node (typically storing some data) that refers to two other trees known as the left sub tree and the right sub tree. The key phrase in this definition is subtree. The tree is composed of smaller trees. This definition is recursive. The base case or simple case is an empty tree that has no nodes at all.
Definition The recursive case describes a tree of the following form: This recursive definition will be a useful way to think about trees as we write binary tree code. The definition will help us to more precisely define the concepts of a branch node and a leaf node.
Branch (internal ) and Leaf Node Branch (Branch Node) A node that has one or more nonempty subtrees. Leaf (Leaf Node) A node that has two empty subtrees. Using recursive definition, let s explore how we can form various kinds of trees. The simplest kind of tree is an empty tree, which can t really be drawn because it contains no values.
Once you understand the concept of an empty tree, you can use the second part of the definition to create a new kind of tree that is composed of a root node with left and right subtrees that are both empty. root 12 Left and right subtrees are empty
Now you can use the recursive rule to say that a tree can be a root node with a left tree that is empty and a right tree that is a leaf root 12 7 By using recursive definition, different forms are possible, allowing you to construct binary tree in many form.
Parent/Child/Sibling/Ancestor/Descendant For every node p that has a nonempty subtree with root node q, we say that p is the parent of q and q is the child of p, which leads logically to ancestor relationships (parent of parent of . . .),descendant relationships (child of child of . . .), and sibling relationships (two nodes with the same parent). overall root node, which stores the value 12. It has two nonempty subtrees. Let us return to our original tree:
Root of a Tree (Overall Root) The node at the top of a binary tree, the only node in the tree that has no parent. The root node, which stores the value 12. It has two nonempty subtrees. Left subtree Right subtree
Node and Tree Classes When we studied linked lists, we built from a simple building block that looks like this: Our basic building block for a binary tree will be similar, but instead of one link, it will have two:
Implementation As we did with linked lists, we will first study how to manipulate a binary tree of simple int values. Here is a class definition for our binary tree nodes. class IntBinaryTreeNode { public: int data; IntBinaryTreeNode *left; IntBinaryTreeNode *right; // constructs a leaf node with given data IntBinaryTreeNode(int dat):data(dat), left(NULL), right(NULL){} };
IntBinaryTreeNode Like our linked list node, this node is very simple; it has some public fields and a a constructor. The node has a field of type int for storing the data contained in this node and two links of type IntBinaryTreeNode for the left and right subtrees. class IntBinaryTreeNode { public: int data; IntBinaryTreeNode *left; IntBinaryTreeNode *right; // constructs a leaf node with given data IntBinaryTreeNode(int dat):data(dat), left(NULL), right(NULL){} }; The node class is NOT well encapsulated, but as we saw with linked lists, this is common practice.
Binarty Tree Class Just as we could reach every node of a linked list by starting at the front and moving forward, we can reach every node of a binary tree by starting at the overall root and moving down in the tree. As a result, we need only one field in the tree class: a reference to the root of the tree: class IntBinaryTree { private: IntBinaryTreeNode *root; public: IntBinaryTree() :root(NULL) {} As we did with our linked lists, we ll represent the empty tree by storing the value NULL in the root field:
Tree Traversals Tree Traversals: One of the fundamental task with binary trees is to be able to perform a binary tree traversal, that is visiting each node once (in one of three defined orders). Before we become familiar with recursive programs, we may tend to think about computation iteratively, I visit this node first, then this one, then this one, and so on. Each iteration, the program says I just visited this node, so now let me find the next node to visit. (as we did with Linked Lists, array, that is linear data structures). Surprisingly, such a computation is hard to code since binary trees are non linear data strucutres.
Tree Traversals Binary Tree A binary tree is either 1. an empty tree or 2. a root node (typically storing some data) that refers to two other trees known as the left subtree and the right subtree. By above defintion it is clear that binary tree is composed of three parts. There is the root node, its left subtree and its right subtree.
Tree Traversals Because the tree is defined recursively, it is easiest to use a recursive approach to this problem. As a result, we want to traverse the entire left subtree without dealing with any of the elements from the right and, in a separate operation, traverse the entire right subtree without dealing with any of the elements from the left. Given this decision, there are three classic binary tree traversals. You can process the root before you traverse either subtree, in between traversing the two subtrees or after you traverse both subtrees.
Tree Traversals You can process the root before you traverse either subtree, in between traversing the two subtrees or after you traverse both subtrees.
Tree Traversals The three classic orders to visit the nodes of a binary tree are 1. Pre-Order traversal , (vLR) 2. In- Order traversal, and (LvR) 3. Post Order traversal, (LRv) in which the root is visited before, between, or after its left and right subtrees are visited.
Tree Traversals The three classic orders to visit the nodes of a binary tree are 1. Pre-Order traversal , 2. In- Order traversal, and 3. Post Order traversal, in which the root is visited before, between, or after its left and right subtrees are visited. For example, consider the following simple tree: 1. A pre-order traversal visits the root, then the left subtree, then the right subtree, yielding the sequence [7, 6, 5]. 2. An in-order traversal visits the left subtree, then the root, then the right subtree, yielding the sequence [6, 7, 5]. 3. A post-order traversal visits the left subtree, then the right subtree, then the root, which yields [6, 5, 7].
Traversal Example A more complex tree, we simply use the recursive nature of this definition to carry out the traversal. For example, consider the following tree. The overall root stores the value 2, so we know that the different traversals will look like this: Preorder traversal: [2, <left>, <right>] Inorder traversal: [<left>, 2, <right>] Postorder traversal: [<left>, <right>, 2]
Traversal Example vLR The overall root stores the value 2, so we know that the different traversals will look like this: Preorder traversal: [2, <left>, <right>] Inorder traversal: [<left>, 2, <right>] Postorder traversal: [<left>, <right>, 2] vLR vLR vLR vLR The left subtree of this tree stores the value 0 and has an empty right subtree. We know that each of the occurrences of <left> is going to be replaced by an appropriate traversal: vLR vLR vLR vLR:visit Root Node, visit Left Sub Tree, visit Right Sub Tree 2, 0, 7, 6, 5, 3, 1, 8, 9,4
Pre-Order Traversal Preorder traversal: [2, <left>, <right>] Preorder traversal: [0, <left>, <right>]
Pre-Order Traversal Preorder traversal: [0, <left>, <NULL>] Preorder traversal: [7, <left>, <right>] Preorder traversal: [6, <NULL>, <NULL>]
Tree Traversal Preorder traversal: [2, 0, 7, 6, 5, 3, 1, 8, 9, 4] Inorder traversal: [6, 7, 5, 0, 2, 8, 1, 3, 9, 4] Postorder traversal: [6, 5, 7, 0, 8, 1, 4, 9, 3, 2]
Tree Traversals The three classic orders to visit the nodes of a binary tree are 1. Pre-Order traversal , 2. In- Order traversal, and 3. Post Order traversal, in which the root is visited before, between, or after its left and right subtrees are visited.
Pre-Order Taversal vLR vLR vLR vLR vLR vLR PreOrder(vLR) Traversal: 12,18,23,7,4,13 InOrder(LvR) Traversal:
In-Order Taversal LvR LvR LvR LvR LvR LvR InOrder(LvR) Traversal:23, 18,12, 4,7,13
Post-Order Taversal LRv LRv LRv LRv LRv LRv PostOrder(LRv) Traversal:23, 18,4,13,7,12
RecursiveAlgorithm for Computing the Number of Nodes We will now develop a recursive algorithm that will compute the number of nodes in a binary tree. Specifications: Preconditions: The input is any binary tree. Trees with an empty subtree are valid trees. So are trees consisting of a single node and the empty tree. Postconditions: The output is the number of nodes in the tree. Size: The size of an instance is the number of nodes in it. Sub instances: The sub instances of our instance tree will be the tree s left and its right subtree. These are valid instances that are strictly smaller than ours because the root (and the other subtree) have been removed. Sub solutions: We ask one friend to recursively count the number of nodes in the left subtree and another friend to do so in the right subtree. Solution: The number of nodes in our tree is the number in its left subtree plus the number in its right subtree plus one for the root.
RecursiveAlgorithm for Computing the Number of Nodes Base Cases: The empty tree is sufficiently small that we can solve it in a brute force way. The number of nodes in it is zero. if(root==NULL) test if root (or binary tree is empty or not) Sub instances: Recursively Find the number of Nodes in left SubTree, and Recursively Find the number of Nodes in right SubTree, since root itself count as 1(one) the return value would be 1+count(number of Nodes int left sub tree)+ count(number of Nodes int right sub tree)
