CSC 1061 Week 12 Binary Tree PDF

CSC 1061 BINARY SEARCH TREE  OBJECTIVES AGENDA: WEEK 12 Explain tree-based algorithms 1. Why: Tree Data Structure Design and implement classes for 2. Tree Terms binary tree nodes and binary trees 3. Binary Search Trees Explain the trave...

CSC 1061 BINARY SEARCH TREE  OBJECTIVES AGENDA: WEEK 12 Explain tree-based algorithms 1. Why: Tree Data Structure Design and implement classes for 2. Tree Terms binary tree nodes and binary trees 3. Binary Search Trees Explain the traversal algorithms for 4. BinNode class (Element of BinTree) the common binary tree traversals 5. BinTree class (Container Data Structure) Understand what a tree data 1. Default Constructor structure is and how it is used. 2. isEmpty Implement trees using classes and 3. Add references. 4. Traversals Implement trees as a recursive 5. Rule of 3 data structure. PRE-CHALLENGE Complete 8.2 Examples of Trees Tutorial in RuneStone Come up with your own example of a Tree to share. WHY TREE DATA STRUCTURE Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the increase in the data size. Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure. We'll focus on Binary Search Trees, but other trees are Heaps, Full Trees, Complete Trees, and B-Tree that we'll talk about later TREE TERMS (VOCABULARY AND DEFINITIONS) Root: It is the topmost node of a tree. Edge: It is the link (pointer) between any two nodes. Leaf: Nodes that do NOT contain any pointer to any child nodes. Depth of a Node: The depth of a binary node is the number of edges from the root to the node. Height of a Tree: The height of a Tree is the height of the root node or the depth of the deepest node Degree of a Node: The degree of a node is the total number of branches of that node. Forest: A collection of disjoint trees is called a forest. BINARY TREE OVERVIEW A tree is a non-linear data structure. In computer science, the tree is upside down. The root is at the top The relationship between a binary node and the one below it is: parent / child relationship. Each binary node has 1 and only 1 parent. A tree is often used to represent a hierarchy A directory structure on a UNIX machine. The root directory is the top!) The binary tree is a useful data structure for rapidly storing sorted data and rapidly ​retrieving stored data.​ BINARY SEARCH TREE (PROGRAMIZ) A binary tree is a tree where the binary nodes have data and pointers to at most 2 children (left and right). For a Binary Search Tree: the left pointer is used to represent children with values that are less than or equal to the parent node A binary node with no children is called a leaf node. BINARY SEARCH TREE OF COLORS Draw in and add the following items as ordered to the Binary Search Tree (string comparison) 1. Red 2. Yellow 3. Green 4. Orange 5. Blue 6. Violet BINNODE (ELEMENT CLASS OF TREE) BinNode Class is: Address of Node Private helper class for BinTree The structure of the element data stored in the Binary Tree left* right* Encapsulates: data left pointer and right pointer BinNode class: NOT Dynamic! It has NO allocation or deallocation of memory NOT A container! – NO adding, removing, finding, etc. BINARY TREE DATA STRUCTURE CLASS A container of BinNode elements that are allocated on the heap at runtime. A BinNode* is allocated with each add and deallocated with each remove to ensure the tree only uses the exact amount of memory Add (12) again to the tree BINARY TREE: CREATING THE TREE Like all data template structures, our class BinTree { Binary Tree data structure will start BinNode* root = nullptr; out empty Initialize root to public: root 0x0 nullptr to create BinTree() {} an empty Tree in }; the default constructor BINARY TREE: ISEMPTY The ability to check if a tree is empty or not is common functionality that is implemented for each data structure. To check if a tree is empty, compare the root pointer to nullptr. // true root 0x0 // false root 0x4b 0x4b // empty // not-empty data template 0x0 0x0 bool BinTree::isEmpty() { return (root == nullptr); } BINARY TREE: ADD TO EMPTY TREE template void BinTree::add(T item) { // allocate a new Binary Node* BinNode* tmp = new BinNode(item); if( isEmpty() ) { root = tmp; // set root to the new binary node to link into tree return; // return to stop function – completed task } else { } } BINARY TREE: ADD TO NON-EMPTY TREE Do NOT use recursion to add, a loop is more efficient to traverse down into the subtree to add the new binary node to. Subtree left is BinNode* cursor = root; // Set cursor to start at beginning of tree while(cursor != nullptr) // determine subTree path: left or right if(tmp->data data) // Left subTree if(cursor->left == nullptr) // spot is OPEN, set cursor->left to tmp return else cursor = cursor->left // move cursor to left subTree else // add to the Right subTree use the same process. BINARY TREE TRAVERSALS Traversing a tree means visiting every node in the tree. Linear data structures like arrays and linked list have only one way to read the data. A hierarchical data structure like a tree can be traversed in four different ways, but ONLY using recursion to enable backtracking through the sub trees! 1. In Order (Left, Process, Right) 2. Pre Order (Process, Left, Right) 3. Post Order (Left, Right, Process) 4. Backward In Order (Right, Process, Left) BINARY TREE TRAVERSAL: DESIGN A design style template to keep the class BinTree {​ pointers Node* root = nullptr; hidden, is to create a void inOrder(Node*); // private​ public function that public: will in turn call void inOrder() { inOrder(root); } a private function that }; takes the root BINARY TREE TRAVERSAL: IN ORDER template void BinTree::inOrder(Node* cursor){ if(cursor != nullptr) { // checking against stopping case inOrder(cursor->left); // Left recursive call std::cout data right); // Right recursive call } } BINARY TREE RULE OF 3 Trees are dynamic; therefore, require the rule of 3 functions be overridden to manage heap memory! 1. Copy Constructor – make a deep copy of source on heap BinTree(const BinTree& source); 2. Assignment Operator – make a deep copy of source on heap BinTree& operator=(const BinTree& source); 3. Destructor – destroy all memory allocated on the heap ~BinTree() { free(root); } BINARY TREE: DEEP COPY OF MEMORY Assignment operator – you will first need to: Check for self-assignment Free existing memory by calling free (you must write the free private member function): free(this->root); For both copy constructor and assignment operator: 1. Initialize memory: this->root = nullptr; 2. Traverse through source using a pre-order recursive traversal member function that you must write: copyTree(source->root); Each item in sources's tree, process by making a deep copy by calling add(cursor->data); that will allocate memory and link memory into the tree.