Advertisement
193030

Binary Search Tree (BST) Create, search, height, search path length

Nov 30th, 2020
596
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.21 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct Node {
  5.     struct Node* lchild;
  6.     int data;
  7.     struct Node* rchild;
  8. }*root = NULL;
  9. void Insert(int key) {
  10.     struct Node* t = root;
  11.     struct Node* r = NULL, * p;
  12.  
  13.     if (root == NULL) {
  14.         p = (struct Node*)malloc(sizeof(struct Node));
  15.         p->data = key;
  16.         p->lchild = p->rchild = NULL;
  17.         root = p;
  18.         return;
  19.     }
  20.     while (t != NULL) {
  21.         r = t;
  22.         if (key < t->data)
  23.             t = t->lchild;
  24.         else if (key > t->data)
  25.             t = t->rchild;
  26.         else
  27.             return;
  28.     }
  29.     p = (struct Node*)malloc(sizeof(struct Node));
  30.     p->data = key;
  31.     p->lchild = p->rchild = NULL;
  32.  
  33.     if (key < r->data) r->lchild = p;
  34.     else r->rchild = p;
  35. }
  36. void Inorder(struct Node* p) {
  37.     if (p) {
  38.         Inorder(p->lchild);
  39.         printf("%d ", p->data);
  40.         Inorder(p->rchild);
  41.     }
  42. }
  43. struct Node* Search(int key) {
  44.     struct Node* t = root;
  45.  
  46.     while (t != NULL) {
  47.         if (key == t->data)
  48.             return t;
  49.         else if (key < t->data)
  50.             t = t->lchild;
  51.         else
  52.             t = t->rchild;
  53.     }
  54.     return NULL;
  55. }
  56.  
  57. int SearchPathLength(int key) {
  58.     struct Node* t = root;
  59.     static int counter = 0;
  60.     while (t != NULL) {
  61.         if (key == t->data)
  62.             return counter;
  63.         else if (key < t->data)
  64.         {
  65.             counter++;
  66.             t = t->lchild;
  67.         }
  68.         else  
  69.         {
  70.             counter++;
  71.             t = t->rchild;
  72.         }
  73.     }
  74.     return 0;
  75. }
  76.  
  77. int Height(struct Node* p)
  78. {
  79.     int x, y;
  80.     if (p == NULL)return 0;
  81.     x = Height(p->lchild);
  82.     y = Height(p->rchild);
  83.     return x > y ? x +1 : y + 1;
  84. }
  85. int main() {
  86.     struct Node* temp;
  87.  
  88.     Insert(50);
  89.     Insert(10);
  90.     Insert(30);
  91.     Insert(40);
  92.     Insert(20);
  93.  
  94.     Inorder(root);
  95.     printf("\n");
  96.  
  97.     temp = Search(20);
  98.     if (temp != NULL)
  99.         printf("element %d is found\n", temp->data);
  100.     else
  101.         printf("element is not found\n");
  102.     int pathLevels = SearchPathLength(30);
  103.     printf("The length is %d \n", pathLevels);
  104.     printf("The height of the tree is %d \n", Height(root));
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement