Facebook
From xxx, 4 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 204
  1. //struktury
  2. #include<iostream>
  3. using namespace std;
  4.  
  5. struct BstNode {
  6.         int data;
  7.         BstNode* left;
  8.         BstNode* right;
  9.         BstNode* stary;
  10. };
  11.  
  12. BstNode* GetNewNode(int data) {
  13.         BstNode* newNode = new BstNode();
  14.         newNode->data = data;
  15.         newNode->left = newNode->right = NULL;
  16.         return newNode;
  17. }
  18.  
  19.  
  20. BstNode* Insert(BstNode* root, int data) {
  21.         if (root == NULL) { // empty tree
  22.                 root = GetNewNode(data);
  23.         }
  24.         // if data to be inserted is lesser, insert in left subtree.
  25.         else if (data <= root->data) {
  26.                 root->left = Insert(root->left, data);
  27.         }
  28.         // else, insert in right subtree.
  29.         else {
  30.                 root->right = Insert(root->right, data);
  31.         }
  32.         return root;
  33. }
  34.  
  35. BstNode* Insertbst(BstNode* root, int data) {
  36.         if (root == NULL) { // empty tree
  37.                 root = GetNewNode(data);
  38.         }
  39.         // if data to be inserted is lesser, insert in left subtree.
  40.         else if (data <= root->data) {
  41.                 root->left = Insertbst(root->left, data);
  42.                 root->left->stary = root;
  43.         }
  44.         // else, insert in right subtree.
  45.         else {
  46.                 root->right = Insert(root->right, data);
  47.                 root->right->stary = root;
  48.  
  49.  
  50.         }
  51.         return root;
  52. }
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59. bool Search(BstNode* root, int data) {
  60.         if (root == NULL) {
  61.                 return false;
  62.         }
  63.         else if (root->data == data) {
  64.                 return true;
  65.         }
  66.         else if (data <= root->data) {
  67.                 return Search(root->left, data);
  68.         }
  69.         else {
  70.                 return Search(root->right, data);
  71.         }
  72. }
  73. void Inorder(BstNode* root) {
  74.         if (root == NULL) return;
  75.  
  76.         Inorder(root->left);       //Visit left subtree
  77.         cout<<root->data<<"   ";  //Print data
  78.         Inorder(root->right);      // Visit right subtree
  79. }
  80.  
  81.  
  82.  
  83. BstNode* FindMin(BstNode* root)
  84. {
  85.         while (root->left != NULL) root = root->left;
  86.         return root;
  87. }
  88.  
  89.  
  90. int max(BstNode* root)
  91. {
  92.         BstNode* temp = root;
  93.         while (temp->right != NULL)
  94.                 temp = temp->right;
  95.         return(temp->data);
  96. }
  97.  
  98. int min(BstNode* root)
  99. {
  100.         BstNode* temp = root;
  101.         while (temp->left != NULL)
  102.                 temp = temp->left;
  103.         return(temp->data);
  104. }
  105.  
  106. BstNode* usunliscie(BstNode* root) {
  107.         if (root == NULL)
  108.                 return NULL;
  109.         if (root->left == NULL && root->right == NULL)
  110.         {
  111.                 delete root;
  112.                 return NULL;
  113.         }
  114.  
  115.         root->left = usunliscie(root->left);
  116.         root->right = usunliscie(root->right);
  117.  
  118.         return root;
  119. }
  120.  
  121.  
  122. BstNode* Delete(BstNode* root, int data) {
  123.         if (root == NULL) return root;
  124.         else if (data < root->data) root->left = Delete(root->left, data);
  125.         else if (data > root->data) root->right = Delete(root->right, data);
  126.         // znaleziono
  127.         else {
  128.                 // Case 1:  nie ma dzieci
  129.                 if (root->left == NULL && root->right == NULL) {
  130.                         delete root;
  131.                         root = NULL;
  132.                 }
  133.                 //Case 2: jedno dziecko
  134.                 else if (root->left == NULL) {
  135.                          BstNode* temp = root;
  136.                         root = root->right;
  137.                         delete temp;
  138.                 }
  139.                 else if (root->right == NULL) {
  140.                         BstNode* temp = root;
  141.                         root = root->left;
  142.                         delete temp;
  143.                 }
  144.                 // case 3: 2 dzieci -  sprowadzam do postaci zeby bylo jedno dziecko
  145.                 else {
  146.                         BstNode* temp = FindMin(root->right);
  147.                         root->data = temp->data;
  148.                         root->right = Delete(root->right, temp->data);
  149.                 }
  150.         }
  151.         return root;
  152. }
  153.  
  154.  
  155. BstNode* minn(BstNode* root)
  156. {
  157.         while (root->left)
  158.                 root = root->left;
  159.         return root;
  160.  
  161. }
  162.  
  163. BstNode* maxx(BstNode* root)
  164. {
  165.         while (root->right)
  166.                 root = root->right;
  167.         return root;
  168. }
  169. void nastepnik(BstNode* root, BstNode*& pop, int x)
  170. {
  171.         if (root == NULL)
  172.         {
  173.                 pop = NULL;
  174.                 return;
  175.         }
  176.         if (root->data == x) {
  177.                 if (root->right)
  178.                         pop = minn(root->right);
  179.         }
  180.         else if (x < root->data)
  181.         {
  182.                 pop = root;
  183.                 nastepnik(root->left, pop, x);
  184.         }
  185.         else {
  186.                 nastepnik(root->right,pop, x);
  187.         }
  188. }
  189.  
  190. void poprzednik(BstNode* root, BstNode*& pop, int x)
  191. {
  192.         if (root == NULL)
  193.         {
  194.                 pop = NULL;
  195.                 return;
  196.         }
  197.         if (root->data == x) {
  198.                 if (root->left)
  199.                         pop = maxx(root->left);
  200.         }
  201.         else if (x < root->data)
  202.                 poprzednik(root->left, pop, x);
  203.         else {
  204.                 pop = root;
  205.                 poprzednik(root->right, pop, x);
  206.         }
  207. }
  208.  
  209.  
  210. // Rotacja w lewo
  211. //---------------
  212. void rot_L(BstNode*& root, BstNode* A)
  213. {
  214.         BstNode* B = A->right, *p = A->stary;
  215.  
  216.         if (B)
  217.         {
  218.                 A->right = B->left;
  219.                 if (A->right) A->right->stary = A;
  220.  
  221.                 B->left = A;
  222.                 B->stary = p;
  223.                 A->stary = B;
  224.  
  225.                 if (p)
  226.                 {
  227.                         if (p->left == A) p->left = B; else p->right = B;
  228.                 }
  229.                 else root = B;
  230.         }
  231. }
  232.  
  233. // Rotacja w prawo
  234. //----------------
  235. void rot_R(BstNode*& root, BstNode* A)
  236. {
  237.         BstNode* B = A->left, *p = A->stary;
  238.  
  239.         if (B)
  240.         {
  241.                 A->left = B->right;
  242.                 if (A->left) A->left->stary = A;
  243.  
  244.                 B->right = A;
  245.                 B->stary = p;
  246.                 A->stary = B;
  247.  
  248.                 if (p)
  249.                 {
  250.                         if (p->left == A) p->left = B; else p->right = B;
  251.                 }
  252.                 else root = B;
  253.         }
  254. }
  255.  
  256.  
  257. int main() {
  258.         BstNode* root = NULL;  
  259.         BstNode* pop = NULL;
  260.  
  261.         root = Insertbst(root, 15);
  262.         root = Insertbst(root, 10);
  263.         root = Insertbst(root, 20);
  264.         root = Insertbst(root, 25);
  265.         root = Insertbst(root, 8);
  266.         root = Insertbst(root, 12);
  267.  
  268.         Inorder(root);
  269.         root=Delete(root, 10);
  270.         cout << endl;
  271.         Inorder(root);
  272.         nastepnik(root, pop, 12);
  273.         cout << endl << pop->data;
  274.  
  275.         rot_R(root, root->right);
  276.  
  277.         system("pause");
  278.         return 0;
  279.  
  280. }
  281. //klasy
  282. #include<iostream>
  283. using namespace std;
  284.  
  285. class BST {
  286.  
  287.         struct BstNode {
  288.                 int data;
  289.                 BstNode* left;
  290.                 BstNode* right;
  291.                 BstNode* stary;
  292.         };
  293.  
  294.         BstNode* root;
  295.  
  296.         BstNode* GetNewNode(int data) {
  297.                 BstNode* newNode = new BstNode();
  298.                 newNode->data = data;
  299.                 newNode->left = newNode->right = NULL;
  300.                 return newNode;
  301.         }
  302.  
  303.  
  304.         BstNode* Insertbst(BstNode* root, int data) {
  305.                 if (root == NULL) { // empty tree
  306.                         root = GetNewNode(data);
  307.                 }
  308.                 // if data to be inserted is lesser, insert in left subtree.
  309.                 else if (data <= root->data) {
  310.                         root->left = Insertbst(root->left, data);
  311.                         root->left->stary = root;
  312.                 }
  313.                 // else, insert in right subtree.
  314.                 else {
  315.                         root->right = Insertbst(root->right, data);
  316.                         root->right->stary = root;
  317.  
  318.  
  319.                 }
  320.                 return root;
  321.         }
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.         bool Search(BstNode* root, int data) {
  329.                 if (root == NULL) {
  330.                         return false;
  331.                 }
  332.                 else if (root->data == data) {
  333.                         return true;
  334.                 }
  335.                 else if (data <= root->data) {
  336.                         return Search(root->left, data);
  337.                 }
  338.                 else {
  339.                         return Search(root->right, data);
  340.                 }
  341.         }
  342.         void Inorder(BstNode* root) {
  343.                 if (root == NULL) return;
  344.  
  345.                 Inorder(root->left);       //Visit left subtree
  346.                 cout << root->data << "   ";  //Print data
  347.                 Inorder(root->right);      // Visit right subtree
  348.         }
  349.  
  350.  
  351.  
  352.         BstNode* FindMin(BstNode* root)
  353.         {
  354.                 while (root->left != NULL) root = root->left;
  355.                 return root;
  356.         }
  357.  
  358.  
  359.         int max(BstNode* root)
  360.         {
  361.                 BstNode* temp = root;
  362.                 while (temp->right != NULL)
  363.                         temp = temp->right;
  364.                 return(temp->data);
  365.         }
  366.  
  367.         int min(BstNode* root)
  368.         {
  369.                 BstNode* temp = root;
  370.                 while (temp->left != NULL)
  371.                         temp = temp->left;
  372.                 return(temp->data);
  373.         }
  374.  
  375.         BstNode* usunliscie(BstNode* root) {
  376.                 if (root == NULL)
  377.                         return NULL;
  378.                 if (root->left == NULL && root->right == NULL)
  379.                 {
  380.                         delete root;
  381.                         return NULL;
  382.                 }
  383.  
  384.                 root->left = usunliscie(root->left);
  385.                 root->right = usunliscie(root->right);
  386.  
  387.                 return root;
  388.         }
  389.  
  390.  
  391.         BstNode* Delete(BstNode* root, int data) {
  392.                 if (root == NULL) return root;
  393.                 else if (data < root->data) root->left = Delete(root->left, data);
  394.                 else if (data > root->data) root->right = Delete(root->right, data);
  395.                 // znaleziono
  396.                 else {
  397.                         // Case 1:  nie ma dzieci
  398.                         if (root->left == NULL && root->right == NULL) {
  399.                                 delete root;
  400.                                 root = NULL;
  401.                         }
  402.                         //Case 2: jedno dziecko
  403.                         else if (root->left == NULL) {
  404.                                 BstNode* temp = root;
  405.                                 root = root->right;
  406.                                 delete temp;
  407.                         }
  408.                         else if (root->right == NULL) {
  409.                                 BstNode* temp = root;
  410.                                 root = root->left;
  411.                                 delete temp;
  412.                         }
  413.                         // case 3: 2 dzieci -  sprowadzam do postaci zeby bylo jedno dziecko
  414.                         else {
  415.                                 BstNode* temp = FindMin(root->right);
  416.                                 root->data = temp->data;
  417.                                 root->right = Delete(root->right, temp->data);
  418.                         }
  419.                 }
  420.                 return root;
  421.         }
  422.  
  423.  
  424.         BstNode* minn(BstNode* root)
  425.         {
  426.                 while (root->left)
  427.                         root = root->left;
  428.                 return root;
  429.  
  430.         }
  431.  
  432.         BstNode* maxx(BstNode* root)
  433.         {
  434.                 while (root->right)
  435.                         root = root->right;
  436.                 return root;
  437.         }
  438.         void nastepnik(BstNode* root, BstNode*& pop, int x)
  439.         {
  440.                 if (root == NULL)
  441.                 {
  442.                         pop = NULL;
  443.                         return;
  444.                 }
  445.                 if (root->data == x) {
  446.                         if (root->right)
  447.                                 pop = minn(root->right);
  448.                 }
  449.                 else if (x < root->data)
  450.                 {
  451.                         pop = root;
  452.                         nastepnik(root->left, pop, x);
  453.                 }
  454.                 else {
  455.                         nastepnik(root->right, pop, x);
  456.                 }
  457.         }
  458.  
  459.         void poprzednik(BstNode* root, BstNode*& pop, int x)
  460.         {
  461.                 if (root == NULL)
  462.                 {
  463.                         pop = NULL;
  464.                         return;
  465.                 }
  466.                 if (root->data == x) {
  467.                         if (root->left)
  468.                                 pop = maxx(root->left);
  469.                 }
  470.                 else if (x < root->data)
  471.                         poprzednik(root->left, pop, x);
  472.                 else {
  473.                         pop = root;
  474.                         poprzednik(root->right, pop, x);
  475.                 }
  476.         }
  477.  
  478.  
  479.         // Rotacja w lewo
  480.         //---------------
  481.         void rot_L(BstNode*& root, BstNode* A)
  482.         {
  483.                 BstNode* B = A->right, * p = A->stary;
  484.  
  485.                 if (B)
  486.                 {
  487.                         A->right = B->left;
  488.                         if (A->right) A->right->stary = A;
  489.  
  490.                         B->left = A;
  491.                         B->stary = p;
  492.                         A->stary = B;
  493.  
  494.                         if (p)
  495.                         {
  496.                                 if (p->left == A) p->left = B; else p->right = B;
  497.                         }
  498.                         else root = B;
  499.                 }
  500.         }
  501.  
  502.         // Rotacja w prawo
  503.         //----------------
  504.         void rot_R(BstNode*& root, BstNode* A)
  505.         {
  506.                 BstNode* B = A->left, * p = A->stary;
  507.  
  508.                 if (B)
  509.                 {
  510.                         A->left = B->right;
  511.                         if (A->left) A->left->stary = A;
  512.  
  513.                         B->right = A;
  514.                         B->stary = p;
  515.                         A->stary = B;
  516.  
  517.                         if (p)
  518.                         {
  519.                                 if (p->left == A) p->left = B; else p->right = B;
  520.                         }
  521.                         else root = B;
  522.                 }
  523.         }
  524.  
  525.         BstNode* makeEmpty(BstNode* t) {
  526.                 if (t == NULL)
  527.                         return NULL;
  528.                 {
  529.                         makeEmpty(t->left);
  530.                         makeEmpty(t->right);
  531.                         delete t;
  532.                 }
  533.                 return NULL;
  534.         }
  535.  
  536.         public:
  537.                 BST() {
  538.                         root = NULL;
  539.                 }
  540.                 ~BST() {
  541.                         root = makeEmpty(root);
  542.  
  543.                 }
  544.                 void insert(int x) {
  545.                         root = Insertbst(root ,x);
  546.                 }
  547.  
  548.                 void zobacz() {
  549.                         Inorder(root);
  550.                 }
  551.  
  552. };
  553.  
  554. int main() {
  555.         BST t;
  556.         t.insert(20);
  557.         t.insert(25);
  558.         t.insert(15);
  559.         t.insert(10);
  560.         t.insert(30);
  561.         t.zobacz();
  562.  
  563.  
  564.         system("pause");
  565.         return 0;
  566.  
  567.  
  568. }
  569.