How do you write this c++ function The last 3 functions are part of the \'Binary

Question

How do you write this c++ function The last 3 functions are part of the 'BinarySearchTree' class: Write a function, nodeCode, that returns the number of nodes in a binary tree.

Explanation / Answer

#include #include #define MAX_VALUE 65536 using namespace std; /* Class Node */ class Node { public: int key; Node *left, *right; bool leftThread, rightThread; }; /* Class ThreadedBinarySearchTree */ class ThreadedBinarySearchTree { private: Node *root; public: /* Constructor */ ThreadedBinarySearchTree() { root = new Node(); root->right = root->left = root; root->leftThread = true; root->key = MAX_VALUE; } /* Function to clear tree */ void makeEmpty() { root = new Node(); root->right = root->left = root; root->leftThread = true; root->key = MAX_VALUE; } /* Function to insert a key */ void insert(int key) { Node *p = root; for (;;) { if (p->key rightThread) break; p = p->right; } else if (p->key > key) { if (p->leftThread) break; p = p->left; } else { /* redundant key */ return; } } Node *tmp = new Node(); tmp->key = key; tmp->rightThread = tmp->leftThread = true; if (p->key right = p->right; tmp->left = p; p->right = tmp; p->rightThrea = false; } else { tmp->right = p; tmp->left = p->left; p->left = tmp; p->leftThread = false; } } /* Function to search for an element */ bool search(int key) { Node *tmp = root->left; for (;;) { if (tmp->key rightThread) return false; tmp = tmp->right; } else if (tmp->key > key) { if (tmp->leftThread) return false; tmp = tmp->left; } else { return true; } } } /* Fuction to delete an element */ void Delete(int key) { Node *dest = root->left, *p = root; for (;;) { if (dest->key rightThread) return; p = dest; dest = dest->right; } else if (dest->key > key) { /* not found */ if (dest->leftThread) return; p = dest; dest = dest->left; } else { /* found */ break; } } Node *target = dest; if (!dest->rightThread && !dest->leftThread) { /* dest has two children*/ p = dest; /* find largest node at left child */ target = dest->left; while (!target->rightThread) { p = target; target = target->right; } /* using replace mode*/ dest->key = target->key; } if (p->key >= target->key) { if (target->rightThread && target->leftThread) { p->left = target->left; p->leftThread = true; } else if (target->rightThread) { Node *largest = target->left; while (!largest->rightThread) { largest = largest->right; } largest->right = p; p->left = target->left; } else { Node *smallest = target->right; while (!smallest->leftThread) { smallest = smallest->left; } smallest->left = target->left; p->left = target->right; } } else { if (target->rightThread && target->leftThread) { p->right = target->right; p->rightThread = true; } else if (target->rightThread) { Node *largest = target->left; while (!largest->rightThread) { largest = largest->right; } largest->right = target->right; p->right = target->left; } else { Node *smallest = target->right; while (!smallest->leftThread) { smallest = smallest->left; } smallest->left = p; p->right = target->right; } } } /* Function to print tree */ void printTree() { Node *tmp = root, *p; for (;;) { p = tmp; tmp = tmp->right; if (!p->rightThread) { while (!tmp->leftThread) { tmp = tmp->left; } } if (tmp == root) break; cout

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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