## Slide #1.

Chapter 10: Trees APPLICATIONS IMPLEMENTATIONS TRAVERSALS BALANCING CS 240 1
More slides like this

## Slide #2.

Sample Tree Root Tree Abstract Data The tree abstract data type Type provides a hierarchical structure to the representation of certain types of relationships. In addition to constructors and a destructor, the tree ADT needs the following functions: • isEmpty - to determine whether the tree contains any entries • insert - to insert a new entry at the appropriate location within the tree • traverse - some mechanism to explore the tree Leaf Leaf Node Node Leaf Node Leaf Leaf Leaf Node Leaf Node Leaf Node Leaf Node CS 240 Node Leaf Leaf 2
More slides like this

## Slide #3.

Binary Tree ADT The binary tree abstract data type is a structure in which entries are configured to have at most two offspring. The binary aspect of this structure makes it particularly useful in applications where individual choices are needed, making it possible to recursively proceed to the right offspring or to the left offspring of the current node. For example, video games frequently present a player with two options, using a game tree to keep track of the alternatives selected by the player. CS 240 Sample Binary Tree Root Leaf Node Node Node Node Leaf Node Leaf Leaf Node Node Leaf Node Leaf Leaf 3
More slides like this

## Slide #4.

Basic Binary Tree Terminology value sibling sibling nodes nodes value value value value value value value value value parent parent node node value value value child child node node value leaf leaf nodes nodes CS 240 value value 4
More slides like this

## Slide #5.

Application: Heap By keeping the data in each node greater than or equal to the data in both of its subtrees, the nodes with the highest values are closer to the root and, consequently, more 325 accessible. 1000 875 700 425 275 25 CS 240 650 575 150 250 400 75 350 100 5
More slides like this

## Slide #6.

Application: Binary Search Tree This structure keeps the data in each node's left subtree less than or equal to the node's data, and the data in the node's right subtree greater than or equal to the node's data. When the data is well distributed, this 23 significantly reduces data search time. 14 41 90 50 38 31 CS 240 72 74 67 97 82 79 99 98 6
More slides like this

## Slide #7.

Application: Binary Expression Tree This structure strategically places the binary operators in the upper nodes, and the primitive operands in the leaf nodes, facilitating the quick evaluation of the overall expression. + Example: (A+B)/C+D*((E+F)%(G/ H)) + A C * D B + E CS 240 % - F G H 7
More slides like this

## Slide #8.

Binary Tree: Array · Place root in slot 0 Implementation · Place left child of slot k's node in slot 2 *k+1 · Place right child of slot k's node in slot 2*k+2     · Locate parent of slot k's node in slot (k   - 1) / 2                          CS 240 00 11 22 33 44 55 66 77 88 99 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27         28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53 54 54 55 55     56 56 57 57 58 58 59 59 60 60 61 61 62 62 63 63 64 64 65 65 66 66 67 67 68 68 69 69 70 70 71 71 72 72 73 73 74 74 75 75 76 76 77 77 78 78 79 79 80 80 81 81 82 82 83 83  84 84 85 85 86 86 87 87 88 88 89 89 90 90 91 91 92 92 93 93 94 94 95 95 96 96 97 97 98 98 99 99 100 100 101 101 102 102 103 103 104 104 105 105 106 106 107 107 108 108 109 109 110 110 111 111    112 112 113 113 114 114 115 115 116 116 117 117 118 118 119 119 120 120 121 121 122 122 123 123 124 124 125 125 126 126 127 127 128 128 129 129 130 130 131 131 132 132 133 133 134 134 135 135 136 136 137 137 138 138 139 139 140 140 141 141 142 142 143 143 144 144 145 145 146 146 147 147 148 148 149 149 150 150 151 151 152 152 153 153 154 154 155 155 156 156 157 157 158 158 159 159 160 160 161 161 162 162 163 163 164 164 165 165 166 166 167 167 168 168 169 169 170 170 171 171 172 172 173 173 174 174 175 175 176 176 177 177 178 178 179 179 180 180 181 181 182 182 183 183 184 184 185 185 186 186 187 187 188 188 189 189 190 190 191 191 192 192 193 193 194 194 195 195 196 196 197 197 198 198 199 199 200 200 201 201 202 202 203 203 204 204 205 205 206 206 207 207 208 208 209 209 210 210 211 211 212 212 213 213 214 214 215 215 216 216 217 217 218 218 219 219 220 220 221 221 222 222 223 223  8
More slides like this

## Slide #9.

Binary Tree: Array Implementation // Class declaration file: BinTree.h ///////////////////////////////////////////////////////////////////////// // This file contains the array implementation of the binary tree ADT. // ///////////////////////////////////////////////////////////////////////// #include #include #include using namespace std; #ifndef BIN_TREE_H //////////////////////////////////////////////////////////// // DECLARATION SECTION FOR THE BINARY TREE CLASS TEMPLATE // //////////////////////////////////////////////////////////// const int MAX_TREE_NODES = 15; template class binary_tree { public: // Class constructors binary_tree(); binary_tree(const binary_tree &bt); CS 240 // Member functions bool isEmpty(); void insert(const E &item); void preorder_traverse(int location); void inorder_traverse(int location); void postorder_traverse(int location); binary_tree& operator = (const binary_tree &bt); void display_array(); 9
More slides like this

## Slide #10.

protected: // Data members struct node { bool vacant; E data; }; // // // // // The node structure is set up so that if the vacant field is FALSE, then the data field is irrelevant. node tree[MAX_TREE_NODES]; int number_nodes; }; // Array of nodes // Number of nodes in tree // Member function void insertStartingHere(const E &item, int location); /////////////////////////////////////////////////////////////// // IMPLEMENTATION SECTION FOR THE BINARY TREE CLASS TEMPLATE // /////////////////////////////////////////////////////////////// // Default constructor. // template binary_tree::binary_tree() { number_nodes = 0; for (int i = 0; i < MAX_TREE_NODES; i++) tree[i].vacant = true; } CS 240 // Copy constructor. // template binary_tree::binary_tree(const binary_tree &bt) { number_nodes = bt.number_nodes; for (int i = 0; i < MAX_TREE_NODES; i++) if (bt.tree[i].vacant) tree[i].vacant = true; else tree[i] = bt.tree[i]; } 10
More slides like this

## Slide #11.

// Assignment operator. // template binary_tree& binary_tree::operator = (const binary_tree &bt) { number_nodes = bt.number_nodes; for (int i = 0; i < MAX_TREE_NODES; i++) if (bt.tree[i].vacant) tree[i].vacant = true; else tree[i] = bt.tree[i]; return *this; } // Empty function. // template bool binary_tree::isEmpty() { return (number_nodes == 0); } // Insert function; inserts via insertStartingHere function. // template void binary_tree::insert(const E &item) { assert(number_nodes < MAX_TREE_NODES); // Room in tree? insertStartingHere(item, 0); number_nodes++; } CS 240 11
More slides like this

## Slide #12.

// Preorder_traverse function; prints tree contents in preorder. // template void binary_tree::preorder_traverse(int location) { if ((location < MAX_TREE_NODES) && (!tree[location].vacant)) { cout << tree[location].data << '\t'; preorder_traverse(2 * location + 1); preorder_traverse(2 * location + 2); } return; } // Inorder_traverse function; prints tree contents in inorder. // template void binary_tree::inorder_traverse(int location) { if ((location < MAX_TREE_NODES) && (!tree[location].vacant)) { inorder_traverse(2 * location + 1); cout << tree[location].data << '\t'; inorder_traverse(2 * location + 2); } return; } CS 240 // Postorder_traverse function; prints tree contents in postorder. // template void binary_tree::postorder_traverse(int location) { if ((location < MAX_TREE_NODES) && (!tree[location].vacant)) { postorder_traverse(2 * location + 1); postorder_traverse(2 * location + 2); cout << tree[location].data << '\t'; } return; } 12
More slides like this

## Slide #13.

// Display_array function; prints tree contents as an // // array, printing the word vacant if a node is vacant. // template void binary_tree::display_array() { int index; for (int i = 0; i < MAX_TREE_NODES/5; i++) { for (int j = 0; j < 5; j++) { index = (MAX_TREE_NODES / 5) * j + i; cout << setw(2) << index << " = "; if (tree[index].vacant) cout << setw(6) << "vacant" << setw(3) << ""; else cout << setw(6) << tree[index].data << setw(3) << ""; } cout << endl; } } // InsertStartingHere function; inserts item into tree using ordering (i.e., // // inserting smaller values to the left and larger values to the right). // template void binary_tree::insertStartingHere(const E &item, int location) { assert(location < MAX_TREE_NODES); // Must be legitimate array index if (tree[location].vacant) { tree[location].data = item; tree[location].vacant = false; } else if (item < tree[location].data) insertStartingHere(item, 2 * location + 1); else insertStartingHere(item, 2 * location + 2); } CS 240 #define BIN_TREE_H #endif 13
More slides like this

## Slide #14.

Sample Driver For Array Implementation // Program file: TreeDriver.cpp ////////////////////////////////// // This program illustrates the // // creation of a binary tree. // ////////////////////////////////// #include #include "BinTree.h" using namespace std; void print_tree(binary_tree &tree); // The main function queries the // // user for new tree elements. // void main() { binary_tree tree; int number; cout << "Enter a number: "; cin >> number; while (number > 0) { tree.insert(number); tree.display_array(); cout << "Enter a number: "; cin >> number; } } CS 240 // The print_tree function outputs the final // // contents of the tree, first by displaying // // the entire array, then by printing out // // the non-vacant tree elements in inorder, // // preorder, and postorder. // void print_tree(binary_tree &tree) { cout << "Array contents:" << endl; tree.display_array(); cout << endl << "Inorder traversal: " << endl; tree.inorder_traverse(0); cout << endl; cout << "Preorder traversal: " << endl; tree.preorder_traverse(0); cout << endl; cout << "Postorder traversal: " << endl; tree.postorder_traverse(0); cout << endl << endl; } print_tree(tree); 14
More slides like this

## Slide #15.

CS 240 15
More slides like this

## Slide #16.

Application For Array Implementation: Heaps // Class declaration file: heap.h // This file contains the array // implementation of the heap ADT. #include "BinTree.h" #include #include // // // #ifndef HEAP_H // DECLARATION SECTION FOR // THE HEAP CLASS TEMPLATE template class heap: public binary_tree { public: // Class constructors heap(); heap(const heap &h); }; CS 240 // Member functions void insert(const E &item); heap& operator = (const heap &h); // IMPLEMENTATION SECTION FOR // THE HEAP CLASS TEMPLATE // Default constructor. // template heap::heap(): binary_tree() { } // Copy constructor. // template heap::heap(const heap &h) { number_nodes = h.number_nodes; for (int i=0; i heap& heap::operator = (const heap &h) { number_nodes = h.number_nodes; for (int i=0; i
More slides like this

## Slide #17.

// Insert function; inserts into the heap to retain the heap structure // and to ensure non-fragmentation of the array structure, moving low // elements down when a high element is inserted. template void heap::insert(const E &item) { int location, parent; assert(number_nodes < MAX_TREE_NODES); } // // // // Now walk the new item up the tree, starting at location location = number_nodes; parent = (location-1) / 2; while ((location > 0) && (tree[parent].data < item)) { tree[location] = tree[parent]; location = parent; parent = (location-1) / 2; } tree[location].data = item; tree[location].vacant = false; number_nodes++; #define HEAP_H #endif CS 240 17
More slides like this

## Slide #18.

Example Driver For The Heap Application // Program file: heapdriv.cpp // This program illustrates // the creation of a heap. #include #include "heap.h" // // // void print_heap(heap &tree); // The main function queries the // // user for new heap elements. // void main() { heap tree; int number; CS 240 } cout << "Enter a number: "; cin >> number; while (number > 0) { tree.insert(number); tree.display_array(); cout << "Enter a number: "; cin >> number; } print_heap(tree); // The print_heap function outputs // // the final contents of the heap, // // first by displaying the entire // // array, then by printing out the // // non-vacant heap elements in in- // // order, preorder, and postorder. // void print_heap(heap &tree) { cout << "Array contents: \n"; tree.display_array(); cout << "\nInorder traversal: \n"; tree.inorder_traverse(0); cout << "\nPreorder traversal: \n"; tree.preorder_traverse(0); cout << "\nPostorder traversal: \n"; tree.postorder_traverse(0); cout << endl << endl; } 18
More slides like this

## Slide #19.

CS 240 19
More slides like this

## Slide #20.

Binary Tree: Linked List Implementation // Class declaration file: bintree.h // This file contains the array implementation of the binary tree ADT. // #ifndef BIN_TREE_H #include #include #include #include // DECLARATION SECTION FOR LINKED VERSION OF BINARY TREE template class binary_tree { public: // Class constructors and destructor binary_tree(); binary_tree(const binary_tree &bt); ~binary_tree(); // Member functions bool isEmpty() const; void insert(const E &item); void preorderTraverse(ofstream &os) const; void inorderTraverse(ofstream &os) const; void postorderTraverse(ofstream &os) const; binary_tree& operator = (const binary_tree &bt); CS 240 20
More slides like this

## Slide #21.

protected: // Data members struct node; typedef node *node_ptr; struct node { E data; node_ptr left; node_ptr right; }; node_ptr root; // Member functions node_ptr get_node(const E &data); }; void void void insertIntoTree(node_ptr &treeRoot, const E &data); copyTree(node_ptr treeRoot) const; destroyTree(node_ptr treeRoot); void void void preorderOutput(node_ptr treeRoot, ofstream &os) const; inorderOutput(node_ptr treeRoot, ofstream &os) const; postorderOutput(node_ptr treeRoot, ofstream &os) const; // IMPLEMENTATION SECTION FOR LINKED VERSION OF BINARY TREE // Default constructor. // template binary_tree::binary_tree() { root = NULL; } CS 240 21
More slides like this

## Slide #22.

// Copy constructor. // template binary_tree::binary_tree(const binary_tree &bt) { root = NULL; copyTree(bt.root) } // Assignment operator. // template binary_tree& binary_tree::operator = (const binary_tree &bt) { root = NULL; copyTree(bt.root); return *this; } // Function copyTree: Starting at the node pointed to by // parameter treeRoot, this function recursively copies the // elements of an existing tree into the *this tree. By // proceeding in a preorder fashion, this function ensures // that the elements of *this will correspond exactly (in // value and position) to the elements of the existing tree. template void binary_tree::copyTree(node_ptr treeRoot) const { if (treeRoot != NULL) { insert(treeRoot->data); copyTree(treeRoot->left); copyTree(treeRoot->right); } } CS 240 // // // // // // 22
More slides like this

## Slide #23.

// Destructor. // template binary_tree::~binary_tree() { destroyTree(root); root = NULL; } // Function destroyTree: returns all memory associated with // the tree to the system heap, by recursively destroying // the two subtrees and then deleting the root. template void binary_tree::destroyTree(node_ptr treeRoot) { if (treeRoot != NULL) { destroyTree(treeRoot->left); destroyTree(treeRoot->right); delete treeRoot; } } // // // // Empty function. // template bool binary_tree::isEmpty() const { return root == NULL; } CS 240 23
More slides like this

## Slide #24.

// Insert function. // template void binary_tree::insert(const E &item) { insertIntoTree(root, item); } // Function insertIntoTree: recursively inserts parameter // // item into tree using binary search tree assumption. // template void binary_tree::insertIntoTree(node_ptr &treeRoot, const E &item) { if (treeRoot == NULL) treeRoot = get_node(item); else if (item < treeRoot->data) insertIntoTree(treeRoot->left, item); else insertIntoTree(treeRoot->right, item); } CS 240 24
More slides like this

## Slide #25.

// Function preorderTraverse. // template void binary_tree::preorderTraverse(ofstream &os) const { preorderOutput(root, os); } // Function preorderOutput: Outputs contents of // // the tree into parameterized file by recursively // // traversing the tree in preorder. // template void binary_tree::preorderOutput(node_ptr treeRoot, ofstream &os) const { if (treeRoot != NULL) { os << treeRoot->data << endl; preorderOutput(treeRoot->left, os); preorderOutput(treeRoot->right, os); } } CS 240 25
More slides like this

## Slide #26.

// Function inorderTraverse. // template void binary_tree::inorderTraverse(ofstream &os) const { inorderOutput(root, os); } // Function inorderOutput: Outputs contents of // // the tree into parameterized file by recursively // // traversing the tree in inorder. // template void binary_tree::inorderOutput(node_ptr treeRoot, ofstream &os) const { if (treeRoot != NULL) { inorderOutput(treeRoot->left, os); os << treeRoot->data << endl; inorderOutput(treeRoot->right, os); } } CS 240 26
More slides like this

## Slide #27.

// Function postorderTraverse. // template void binary_tree::postorderTraverse(ofstream &os) const { postorderOutput(root, os); } // Function postorderOutput: Outputs contents of // // the tree into parameterized file by recursively // // traversing the tree in postorder. // template void binary_tree::postorderOutput(node_ptr treeRoot, ofstream &os) const { if (treeRoot != NULL) { postorderOutput(treeRoot->left, os); postorderOutput(treeRoot->right, os); os << treeRoot->data << endl; } } CS 240 27
More slides like this

## Slide #28.

// Function get_node: Dynamically allocates space for a new // // tree node, placing the parameter item's value into the // // new node, and initializing both of its pointers to NULL. // template typename binary_tree::node_ptr binary_tree::get_node(const E &item) { node_ptr temp = new node; } assert(temp != NULL); temp->data = item; temp->left = NULL; temp->right = NULL; return temp; #define BIN_TREE_H #endif CS 240 28
More slides like this

## Slide #29.

Example Driver For The Linked List Implementation // Program file: testtree.cpp // // // // // // // // // This program illustrates working with a binary tree. The input consists of an unordered list of integers from a file. The output consists of three files containing the preorder, inorder, and postorder traversals of the binary search tree that is constructed from the input integers. #include #include #include input_file.open("numbers.txt"); pre_file.open("preordered.txt"); in_file.open("inordered.txt"); post_file.open("postordered.txt"); input_file >> number; while (!input_file.eof()) { tree.insert(number); input_file >> number; } input_file.close(); "BinTree.h" tree.preorderTraverse(pre_file); tree.inorderTraverse(in_file); tree.postorderTraverse(post_file); void main() { int number; ifstream input_file; ofstream pre_file; ofstream in_file; ofstream post_file; binary_tree tree; pre_file.close(); in_file.close(); post_file.close(); } CS 240 return; 29
More slides like this

## Slide #30.

File Contents 79 numbers.tx t 79 54 47 43 13 49 78 23 24 78 42 76 31 74 29 47 79 14 68 96 CS 240 54 79 47 43 49 13 47 23 14 76 74 68 24 42 31 29 78 96 78 79 54 47 43 13 23 14 24 42 31 29 49 47 78 76 74 68 78 79 96 13 14 23 24 29 31 42 43 47 47 49 54 68 74 76 78 78 79 79 96 14 29 31 42 24 23 13 43 47 49 47 68 74 76 78 78 54 96 79 79 preordered.txt inordered.txt postordered.txt 30
More slides like this

## Slide #31.

Additional Tree Traversal Member Function #1 // Public function to “spell out” the values from the root to the tree’s // // leaf nodes, with the results output on a separate line for each leaf. // template void BinaryTree::spellFromTop(ofstream &os) { continueSpelling(root, os, ""); } // Protected function to concatenate the char value of the current subtree’s // // root to the str param. until a leaf is reached, whereupon str is output. // template void BinaryTree::continueSpelling(nodePtr treeRoot, ofstream &os, string str) { if (treeRoot == NULL) return; else { str += char(treeRoot->data); if ((treeRoot->left == NULL) && (treeRoot->right == NULL)) os << str << endl; else { continueSpelling(treeRoot->left, os, str); continueSpelling(treeRoot->right, os, str); } } } CS 240 31
More slides like this

## Slide #32.

Applying spellFromTop To A Sample Tree str: “MI” str: “MIC” M I O str: “MIL” C str: M “MOM” L str: “MICE” E output “MICE” str: “MILL” K output “MILK” str: “MO” str: P “MOP” output “MOM” str: “MILK” CS 240 str: “M” L output “MILL” str: “MOPS” S output “MOPS” 32
More slides like this

## Slide #33.

Additional Tree Traversal Member Function #2 // Public function to output the sequence of left and right // comprise the longest path from the tree’s root to one of template void BinaryTree::outputLongestPath(ofstream &os) { os << longestPath(root); } CS 240 offspring that its leaf nodes. // // // Protected function to recursively generate a string indicating which // // offspring (left or right) yield the longest path from the root to a leaf. // template string BinaryTree::longestPath(nodePtr treeRoot) { if (treeRoot == NULL) return ""; else { string leftStr = longestPath(treeRoot->left); string rightStr = longestPath(treeRoot->right); if (leftStr.size() > rightStr.size()) { leftStr.insert(0, 'L'); return leftStr; } else { rightStr.insert(0, 'R'); return rightStr; } } } 33
More slides like this

## Slide #34.

Applying outputLongest To A Sample Tree “LRR” “LRR” leftStr: rightStr: “L” “R”“” “” leftStr: rightStr: “” “” CS 240  rightStr: “RRL” “RL” “RL” leftStr:  rightStr: “LL” “RL”  leftStr: rightStr: “LRR” “” “RR” “RR”   Final result: “LLRR” leftStr: “LLRR” “L” “L” leftStr: rightStr: “” “R” “RR” “R”  leftStr: “L” rightStr: “” “” “” leftStr: “” rightStr: “” “” “”  leftStr: rightStr: “” “”   “L” “L” leftStr: “L” rightStr: “”“” “”   leftStr: “” rightStr: “” 34
More slides like this

## Slide #35.

AVL Trees Although an average search in an nnode binary search tree is O(logn), the worst case could be as bad as O(n). An AVL (Adelson-Velskii and Landis) tree places a balance condition on a binary search tree by requiring the left and right subtrees of each node to have heights differing by at most one. During insertion, this is accomplished by means of single and double rotations. Single rotations: Note that in each of the trees illustrated at right: (any element of X)  k1  (any element of Y)  k2  (any element of Z) So when a new element’s insertion causes an imbalance, “rotate” the tree to restore the balance. CS 240 k22 k11 Z X Y k11 k22 X Y Z 35
More slides like this

## Slide #36.

Single Rotation Examples 2 7 1 4 3 1 1 2 2 7 INSERT INSERT 5 5 3 0 1 4 4 5 3 1 1 2 2 7 ROTATE ROTATE 1 2 3 0 4 5 5 3 1 1 4 3 0 4 5 5 8 4 8 4 INSERT INSERT 99 99 7 5 9 3 9 2 7 5 9 8 9 3 ROTATE ROTATE 9 3 9 2 8 4 9 8 7 5 9 8 9 2 9 9 9 9 CS 240 36
More slides like this

## Slide #37.

k1 Double Rotations If a single rotation doesn’t A restore balance, a double rotation will. Note that in the two trees illustrated at right: (any value in A)  k1  (any value in B)  k2  (any value in C)  k3  Also note that in the two trees k1 value in illustrated at(any right: D) (any value in E)  k  1 E (any value in F)  k2  (any value in G)  k3  (any value in H) If a single rotation fails to restore balance after a new insertion, a double rotation may CS 240 be tried. k3 k22 B D C k2 k1 A k3 B C D k3 H k2 F G k2 k1 E k3 F G H 37
More slides like this

## Slide #38.

Double Rotation Example 2 5 1 6 9 4 9 1 9 3 6 3 1 INSERT INSERT 47 47 6 4 2 5 1 6 9 4 9 1 9 4 1 3 6 3 1 SINGLE SINGLE ROTATIO ROTATIO N N 6 4 1 6 9 4 9 1 9 3 1 3 6 INSERT INSERT 47 47 6 4 4 1 9 1 6 3 1 3 6 4 9 6 4 9 STILL UNBALANCED 2 5 1 6 4 1 1 9 3 1 4 1 6 4 4 7 DOUBLE DOUBLE ROTATIO ROTATIO N N 4 7 CS 240 1 9 4 1 4 9 3 1 3 6 4 1 2 5 1 9 1 6 9 4 7 2 5 2 5 3 6 4 9 4 7 BALANCED! 6 4 38
More slides like this

## Slide #39.

General Trees There are occasions when nonbinary trees are needed Application Example: Game Trees 6 2 8 3 7 1 5 4 6 8 3 2 7 1 5 4 6 8 3 2 7 1 5 4 CS 240 6 8 3 2 7 1 5 4 6 2 8 3 7 1 5 4 2 8 6 3 7 1 5 4 6 2 8 1 3 7 5 4 6 2 8 3 5 7 1 4 6 2 8 3 5 7 1 4 6 2 8 3 5 7 1 4 6 2 8 3 7 1 5 4 6 2 8 3 7 4 1 5 6 2 3 7 8 1 5 4 39
More slides like this

## Slide #40.

Binary Implementation Of General Trees A common approach for implementing general trees is to use binary trees, with offspring and sibling pointers Actual tree F A B C G H D I E J K L M N A B C F D G Binary representation, with left pointers for “first offspring” and right pointers for “next sibling” CS 240 H I J E K L M N 40
More slides like this