Problem understanding Trees: Write a C++ program to read in as set of numbers an

Question

Problem understanding Trees:

Write a C++ program to read in as set of numbers and build an ordered binary tree. Your input file is TreeNbrsV2.txt. The file has integer numbers recorded in it and it also has duplicates numbers. You will read in a number, search the tree and if the input value is not found, insert a new node in the tree for the given value. If the input value is found, then you will count the value read in as a duplicate number, ie bump the counter. Each node will have a ‘value’ field (the number read in) and a counter use to count the number of duplicates of said value. You are to input a single value then either insert or count the value after searching the tree. (You are not to do any other calculation below while reading and updating the binary tree.)

After building the tree, do the following tasks:

a.   Print out the tree in inorder (the first 20 values)

b.   Print out the tree in preorder. (the first 20 values)

c.   Print out the tree in postorder. (the first 20 values)

d.   Print out the number of nodes in the tree.

e.   Sum up all the values in the tree (duplicates have to be counted duplicated times) and compute the average. Print the sum and the average.

f.   Count the number of duplicates that was read in.

g.   Count the number of leafs in the tree.

h.   Print the number of nodes that have only one (1) child

i.   Print the value that is the deepest leaf down in the tree.

j.   Travers the tree and delete all nodes where the sum of the digits is less than 9

k.   Print out the tree in inorder (the first 20 values)

l.    Print out the number of nodes in the tree.

m. Sum up all the values in the tree (duplicates have to be counted duplicated times) and compute the average. Print the sum and the average.

**Testing code with:

56 109 51 92 111 166 124 150 29 156 122 162 23 44 178 158 37 59 119 28
33 96 69 170 134 149 113 183 135 137 39 43 88 180 136 154 134 66 77 111
20 28 189 75 190 131 108 28 95 60 189 186 129 49 104 101 165 133 71 95
83 77 157 109 130 23 132 34 31 90 163 22 157 96 62 142 148 143 85 65
46 40 126 21 48 132 83 43 123 75 161 81 143 140 129 30 35 174 21 108
125 157 106 100 146 147 169 48 190 178 138 62 166 189 162 71 19 190 39 79
28 182 78 103 147 109 47 191 23 169 67 117 158 41 158 122 149 108 174 154
74 54 120 75 87 176 26 150 88 55 139 113 48 97 155 135 42 58 54 97
102 76 166 79 40 25 137 33 119 42 158 53 116 187 63 63 65 116 85 176
73 26 70 91 185 130 92 130 119 134 70 35 165 100 149 163 152 159 80 81
151 108 52 143 142 191 86 73 65 45 116 175 86 76 131 169 62 27 135 185
90 29 106 70 115 17 175 160 122 38 115 73 181 165 26 49 189 189 180 59
105 46 182 99 100 83 57 155 98 153 119 26 139 122 45 88 129 178 167 100
136 34 61 33 23 165 189 118 63 116 74 143 84 81 17 54 167 77 20 111
28 180 118 181 47 165 119 102 49 152 155 118 109 149 49 149 161 71 188 56
43 21 110 184 92 72 126 116 108 79 62 52 35 95 56 190 21 113 79 121
166 129 108 191 35 112 164 133 128 22 180 24 47 26 106 168 183 38 28 30
130 47 52 120 54 150 99 137 130 123 163 150 38 174 148 136 113 114 146 78
127 167 165 158 161 151 59 31 120 91 96 127 37 191 78 105 116 39 85 35
79 122 125 58 69 142 69 56 56 116 126 166 64 51 125 87 154 139 185 144
115 87 30 60 59 177 144 97 180 119 94 91 94 17 160 191 190 64 128 23
45 149 22 135 167 98 109 159 89 153 131 42 129 152 30 191 112 137 77 50
128 52 188 134 127 142 157 61 87 116 36 42 168 186 100 69 63 83 145 35
68 126 160 131 136 69 17 79 102 18 102 49 162 32 143 144 160 25 181 51
24 128 182 179 19 141 17 94 46 95 65 187 94 104 140 113 79 153 62 167
56 52 94 83 147 43 153 163 128 189 170 187 57 66 105 80 57 43 129 21
117 55 75 95 157 74 119 167 175 156 45 177 124 66 19 50 130 29 43 117
127 45 60 101 172 82 153 21 77 173 139 142 115 152 98 133 68 99 143 74
129 188 86 153 138 89 59 154 134 163 52 83 115 171 96 32 101 24 88 122
170 179 101 176 21 189 124 36 149 180 174 50 53 102 109 115 142 180 140 109
146 53 183 67 126 167 88 37 68 101 172 125 67 90 71 143 135 151 79 126
148 85 43 172 154 65 148 142 80 33 97 22 34 104 153 94 141 145 19 85
138 90 82 55 17 139 60 102 159 74 129 87 61 48 107 80 177 32 89 156
107 112 120 81 118 157 186 75 177 26 184 97 81 123 170 171 167 150 84 64
66 173 28 144 184 158 71 107 180 141 143 144 107 125 180 34 116 18 134 26
62 20 44 76 117 78 115 137 179 64 71 170 63 105 123 105 102 138 31 57
106 184 111 105 83 71 160 149 67 22 92 156 145 64 115 64 126 190 188 31
180 67 37 29 63 145 36 54 136 177 131 36 82 182 162 150 160 62 168 165
149 164 44 79 62 30 168 145 90 44 67 36 32 157 45 35 164 180 160 54
26 55 166 148 30 159 100 52 63 25 46 80 163 182 91 85 97 87 65 134
178 150 27 43 152 55 70 96 41 190 165 51 74 108 61 97 60 18 53 42
72 43 166 63 51 82 131 84 42 80 59 63 90 64 143 98 115 121 46 72
168 79 142 185 132 128 53 108 31 61 48 19 153 55 24 147 32 98 47 183
117 103 104 178 107 92 79 126 60 45 83 169 25 104 25 46 45 26 70 98
165 116 84 30 176 70 167 97 160 75 92 22 53 56 20 18 85 151 44 78
156 115 74 20 66 137 169 115 173 136 45 151 125 61 188 95 87 173 96 159
152 130 65 181 139 180 154 127 153 126 100 178 126 35 132 86 104 186 75 17
163 31 84 132 72 132 147 81 129 80 99 46 177 77 176 116 172 82 68 83
107 121 152 190 165 105 19 124 48 181 55 50 183 57 165 30 45 176 120 42
188 152 116 38 150 134 95 137 160 17 68 71 142 165 176 160 153 172 158 192

Explanation / Answer

#include #include /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { char data; struct node* left; struct node* right; }; /* Prototypes for utility functions */ int search(char arr[], int strt, int end, char value); struct node* newNode(char data); /* Recursive function to construct binary of size len from Inorder traversal in[] and Preorder traversal pre[]. Initial values of inStrt and inEnd should be 0 and len -1. The function doesn't do any error checking for cases where inorder and preorder do not form a tree */ struct node* buildTree(char in[], char pre[], int inStrt, int inEnd) { static int preIndex = 0; if(inStrt > inEnd) return NULL; /* Pick current node from Preorder traversal using preIndex and increment preIndex */ struct node *tNode = newNode(pre[preIndex++]); /* If this node has no children then return */ if(inStrt == inEnd) return tNode; /* Else find the index of this node in Inorder traversal */ int inIndex = search(in, inStrt, inEnd, tNode->data); /* Using index in Inorder traversal, construct left and right subtress */ tNode->left = buildTree(in, pre, inStrt, inIndex-1); tNode->right = buildTree(in, pre, inIndex+1, inEnd); return tNode; } /* UTILITY FUNCTIONS */ /* Function to find index of value in arr[start...end] The function assumes that value is present in in[] */ int search(char arr[], int strt, int end, char value) { int i; for(i = strt; i data = data; node->left = NULL; node->right = NULL; return(node); } /* This funtcion is here just to test buildTree() */ void printInorder(struct node* node) { if (node == NULL) return; /* first recur on left child */ printInorder(node->left); /* then print the data of node */ printf("%c ", node->data); /* now recur on right child */ printInorder(node->right); } /* Driver program to test above functions */ int main() { char in[] = {'D', 'B', 'E', 'A', 'F', 'C'}; char pre[] = {'A', 'B', 'D', 'E', 'C', 'F'}; int len = sizeof(in)/sizeof(in[0]); struct node *root = buildTree(in, pre, 0, len - 1); /* Let us test the built tree by printing Insorder traversal */ printf("Inorder traversal of the constructed tree is "); printInorder(root); getchar(); }

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.