How to implement BST Tree in c++?

Question

I mean I want to make a BST tree by few nodes which each of that has a frequency so I want to implement a BST tree has been built by current nodes  the low frequency nodes must be left child of parent codes and vice versa and it start with the highest frequency . The calculation must be the lowest one created by nodes in tree. For example: Node 1 : 0.9 Node 2: 0.4 The calculation must be the lowest one created by nodes: 1 * 0.9 + 2 * 0.6 + 3 * 0.1= 2.4 Node 3: 0.1 Node 1 Node 2 Node 3

ahmad morad · Answer

hello Building code tree BST // BST tree.cpp : Defines the entry point for the console application. // #include stdafx.h #include #include #include #include #include #include #include #include #include #include #include using namespace std; //tree node //------------------------------------------ class node { public: int data; node* parent; node* leftChild; node* rightChild; node(void); }; node::node(void) { data = 0; parent = NULL; leftChild = NULL; rightChild = NULL; } //------------------------------------------ //binary search tree class bst { public: node* root; bst(void); void insert(int); void display(node* int); node* minimum(); node* maximum(); node* search(int); void inorder_tree_walk(node*); node* successor(node*); node* predecessor(node *); void transplant(node* node*); void deletion(node *); }; bst::bst(void) { root = NULL; } void bst::insert(int d) { node* newNode = new node(); newNode->data = d; if (root == NULL) { root = newNode; } else { node* tempNode = new node(); node* backTempNode = new node(); tempNode = root; while (tempNode != NULL) { backTempNode = tempNode; if (tempNode->data data) { tempNode = tempNode->rightChild; } else { tempNode = tempNode->leftChild; } } newNode->parent = backTempNode; if (backTempNode->data data) { backTempNode->rightChild = newNode; } else { backTempNode->leftChild = newNode; } } } //display binary search tree void bst::display(node *Node int level) { if (root == NULL) { cout } else { if (Node->rightChild != NULL) { display(Node->rightChild level + 1); } if (Node != root) { for (int i = 0; i { cout } } else { cout ; } cout data if (Node->leftChild != NULL) { display(Node->leftChild level + 1); } } } //return minimum node node* bst::minimum() { node* tempNode = new node(); node* backTempNode = new node(); backTempNode = tempNode = root; while (tempNode != NULL) { backTempNode = tempNode; tempNode = tempNode->leftChild; } return backTempNode; } //www.open-mind.ir //return maximum node node* bst::maximum() { node* tempNode = new node(); node* backTempNode = new node(); backTempNode = tempNode = root; while (tempNode != NULL) { backTempNode = tempNode; tempNode = tempNode->rightChild; } return backTempNode; } //Search in BST Tree node* bst::search(int Data) { node* tempNode = new node(); tempNode = root; while (tempNode != NULL) { if (tempNode->data == Data) { return tempNode; } else { if (tempNode->data { tempNode = tempNode->rightChild; } else { tempNode = tempNode->leftChild; } } } return NULL; } //inoreder tree walk = show all node in sorted mood void bst::inorder_tree_walk(node* currentNode) { if (root != NULL) { if (currentNode->leftChild != NULL) { inorder_tree_walk(currentNode->leftChild); } cout data if (currentNode->rightChild != NULL) { inorder_tree_walk(currentNode->rightChild); } } else { cout } } //successor node* bst::successor(node* currentNode) { node* tempNode = new node(); node* backTempNode = new node(); tempNode = currentNode; if (tempNode->rightChild != NULL) { tempNode = tempNode->rightChild; while (tempNode != NULL) { backTempNode = tempNode; tempNode = tempNode->leftChild; } return backTempNode; } else { backTempNode = tempNode; tempNode = tempNode->parent; while (tempNode != NULL && tempNode->rightChild == backTempNode) { backTempNode = tempNode; tempNode = tempNode->parent; } return tempNode; } } //predecessor node* bst::predecessor(node* currentNode) { node* tempNode = new node(); node* backTempNode = new node(); tempNode = currentNode; if (tempNode->leftChild != NULL) { tempNode = tempNode->leftChild; while (tempNode != NULL) { backTempNode = tempNode; tempNode = tempNode->rightChild; } return backTempNode; } else { backTempNode = tempNode; tempNode = tempNode->parent; while (tempNode != NULL && tempNode->leftChild == backTempNode) { backTempNode = tempNode; tempNode = tempNode->parent; } return tempNode; } } //transplant void bst::transplant(node* u node* v) { if (u->parent == NULL) { root = v; } else { if (u == u->parent->leftChild) { u->parent->leftChild = v; } else { u->parent->rightChild = v; } } if (v != NULL) { v->parent = u->parent; } } //remove node from tree void bst::deletion(node *z) { if (z->leftChild == NULL) { transplant(z z->rightChild); } else { if (z->rightChild == NULL) { transplant(z z->leftChild); } else { node* succesor = new node(); succesor = successor(z); if (succesor->parent != z) { transplant(succesor succesor->rightChild); succesor->rightChild = z->rightChild; succesor->rightChild->parent = succesor; } transplant(z succesor); succesor->leftChild = z->leftChild; succesor->leftChild->parent = succesor; } } delete z; } //------------------------------------------ //menu void menu() { char ch; int inttemp; node *temp = new node(); bst myTree; int select; do { system(CLS); cout cout cout cout cout cout cout cout cout cout cout cin >> select; system(CLS); switch (select) { case 0: { break; } case 1: { do { int data; cout cin >> data; myTree.insert(data); cout cin >> ch; } while (ch != 'n'); break; } case 2: { myTree.display(myTree.root 0); cout cin >> ch; break; } case 3: { temp = myTree.minimum(); if (temp != NULL) { cout data } else { cout } cout cin >> ch; break; } case 4: { temp = myTree.maximum(); if (temp != NULL) { cout data } else { cout } cout cin >> ch; break; } case 5: { cout cin >> inttemp; temp = myTree.search(inttemp); if (temp != NULL) { cout data } else { cout } cout cin >> ch; break; } case 6: { cout myTree.inorder_tree_walk(myTree.root); cout cin >> ch; break; } case 7: { cout cin >> inttemp; temp = myTree.search(inttemp); if (temp == NULL) { cout } else { temp = myTree.successor(temp); if (temp == NULL) { cout } else { cout data } } cout cin >> ch; break; } case 8: { cout cin >> inttemp; temp = myTree.search(inttemp); if (temp == NULL) { cout } else { temp = myTree.predecessor(temp); if (temp == NULL) { cout } else { cout data } } cout cin >> ch; break; } case 9: { cout cin >> inttemp; temp = myTree.search(inttemp); if (temp == NULL) { cout } else { myTree.deletion(temp); cout } cout cin >> ch; break; } default: break; } } while (select != 0); } //------------------------------------------ int main() { menu(); cin.ignore(); cin.get(); return 0; }

Joe Wilson · Answer

By the way Could use please guide me that how can I get the frequency of nodes from user in this program?

Joe Wilson · Answer

Well Thank you for your answer that was very comprehensive .