COMP SCI 11 WITH C++
COMP SCI 11 WITH C++ CSC 1254
Popular in Course
Popular in ComputerScienence
This 9 page Class Notes was uploaded by Miss Emery VonRueden on Tuesday October 13, 2015. The Class Notes belongs to CSC 1254 at Louisiana State University taught by W. Duncan in Fall. Since its upload, it has received 7 views. For similar materials see /class/222858/csc-1254-louisiana-state-university in ComputerScienence at Louisiana State University.
Reviews for COMP SCI 11 WITH C++
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/13/15
CBC 1254 Lecture 20 Introduction to Binary Trees November 12 2009 0 Characteristics of Some ADTs o Terminology o ADT Binary Search Tree Operations 0 Binary Search Tree Representation o Binary Tree Traversal 1 Characteristics of Some ADTs The ADTs unordered list7 stack7 and queue are all positionoriented7 and their operations have the form 0 Insert a data item at the 2 position 0 Delete the data item at the 2 position 0 Ask question about the data item at the 2 position The ADT ordered list is valueoriented lts operations are of the form 0 Insert a data item containing the value X 0 Delete a data item containing the value X 0 Ask a question about a data item containing the value X The next two ADTs we will discuss are binary tree ADT and7 the more useful7 binary search tree ADT While all the ADTs we have covered thus far are linear7 trees are non linear The main difference between the binary tree ADT and the binary search tree ADT is that while binary tree ADT is positioned oriented7 binary search tree ADT is value oriented We will implement only the binary search tree ADT in this course 2 Terminology De nition 1 A tree is a set of one or more nodes7 partitioned into root node and subsets that are subtrees of the root De nition 2 The parent of node n is the node directly above node n in the tree De nition 3 A child of node n is a node directly below node n in the tree De nition 4 The root is the only node in the tree without a parent De nition 5 A leaf is a node without children De nition 6 Siblings are nodes with a common parent De nition 7 An ancestor of node n is any node on the path from the root to 71 De nition 8 A descendant of node n is a node on a path from n to a leaf De nition 9 A subtree of node n is a tree that consists of a child if any of n and the child7s descendants De nition 10 The height of a tree is the number of edges on the longest path from the root to a leaf An empty tree has a height of 1 a tree with only one node has a height of 0 De nition 11 A binary tree is a set of nodes that is either empty or partitioned into a root node and one or two subsets that are binary subtrees of the root Each node has at most two children7 the left child and the right child De nition 12 The leftright child of node n is a node directly below and to the leftright of node n in a binary tree 2 De nition 13 The leftright subtree of node n in a binary tree is the leftright child if any of node 71 plus its descendants De nition 14 A binary search tree is a binary tree where the value in any node n is greater than the value in every node in n7s left subtree7 but less than the value of every node in n7s right subtree De nition 15 An empty tree is a binary tree with no node De nition 16 A perfect binary tree is a binary tree of height h with no missing nodes All leaves are at level n and all other nodes each have two children De nition 17 A full binary tree is a binary tree in which each node has 0 or two children De nition 18 A complete binary tree is a binary tree of height h that is perfect to level h 7 1 and has level h lled in from left to right De nition 19 A balanced binary tree is a binary tree in which the left and right subtrees of any node have heights that differ by at most 1 3 ADT Binary Search Tree Operations De nition 20 The ADT binary search tree is a binary tree in which the value in any node n is greater than the value in every node in n7s left subtree7 but less than the value of every node in n7s right subtree along with the following operations 1 Create an empty binary search tree 3 Destroy a binary search tree 00 Determine whether a binary search tree is empty 4 Insert a new item into a binary search tree 9 Delete the item with a given search key from the binary search tree CT Traverse the items in a binary search tree in preordler7 inordler7 or pos torder 4 Binary Search Tree Representation Although binary search trees may be implemented using arrays7 it is typically implemented using pointers Here is the representation used template lttypename Ugt template lttypename Tgt class BstreeltTgtNode public Constructs a node with a given data value param s the data to store in this node NodeltTgtT 5 private T data NodeltTgt left NodeltTgt right friend class BstreeltUgt template lttypename Tgt class Bstree public member functions private member functions for internal use only NodeltTgt root The rst class represents a data node and the second represents the root of the tree The root is simply a reference to a node There are many different kinds of implementation but this is the one we will use Here is a diagram showing a binary search here with 7 nodes and an empty binary tree data data data data data data Figure 1 a binary search trees with 7 data nodes left and an empty binary search tree right 5 Binary Tree Traversal There are three major binary tree traversal algorithms 51 Preorder Traversal if T is not empty visit the root of T preorder LeftChild T preorder RightChild T 52 Inorder Traversal if T is not empty inorder LeftChildT visit the root of T inorder RightChildT 53 Postorder Traversal if T is not empty postorder LeftChildT postorder RightChildT visit the root of T 6 Function Pointers A function pointer is a pointer that denotes a function rather than an object Example mt fnptr mt 1 mt b The pointer may point to any function that takes two integer parameters and returns an integer Function pointers are very useful in having functions serve as an arguments to other functions Consider the functions below Example 1 int sumint p int q return pq int prodint 5 int t return st int arithmeticint X int y int fnint a int b return fnXy coutltltquotsum quotltltarithmetic34sumltltendl coutltltquotproduct quotltltarithmetic34prodltltendl This outputs sum 7 product 12 The syntax for function pointers can be a bit unwieldy With the help of typedefs we can make it a little more manageable Example 2 typedef int FunctionType int a int b int powerint p int q int 1 int pwr 1 for i1 iltq i PWr PWr P return pwr int sumeSquaresint X int y FunctionType f return fX2 fy2 coutltltquotsum of squares quotltltsumeSquares34powerltltendl This outputs sum of squares 25 This makes the function header easier to follow We will see more appli cation of function pointers in the binary search tree implementation Problem 1 Suppose the data values of a binary search tree7 as described above7 are integers How would you nd the sum of all the even numbers in the tree Problem 2 Show the binary search tree before an after each of the follow ing data is inserted into it 92 24 6 7 11 8 22 4 5 16 19 20 78 Problem 3 Show the contents ofthe initially empty binary search b before and after each dleletion7 assuming inorder predecessor replacernent strategy insert92 insert24 insert6 insert7 insert11 insert8 insert22 delete24 insert4 insert5 insert16 delete24 insert19 insert20 insert78 delete6 O O O O O O O O O O U O O O O O Problem 4 Repeat problem 37 assuming inorder successor replacernent strategy
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'