TEXT   39
UU
Guest on 23rd November 2022 07:17:56 AM


  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. struct node
  4. {
  5. int data;
  6. struct node *lchild,*rchild;
  7. };
  8. struct node *insert(struct node *root,int data)
  9. {
  10. struct node *t1,*t2,*t;
  11. t1=root;
  12. t2=(struct node *)0;
  13. while(t1!=(struct node *)0 && t1->data!=data)
  14. {
  15. t2=t1;
  16. if(data<t1->data)
  17. t1=t1->lchild;
  18. else
  19. t1=t1->rchild;
  20. }
  21. if(t1!=(struct node *)0)
  22. printf("duplicate:/n");
  23. else
  24. {
  25. t1=(struct node *) malloc (sizeof(struct node));
  26. t1->data=data;
  27. t1->lchild=t1->rchild=(struct node *)0;
  28. if(root==(struct node *)0)
  29. root=t1;
  30. else
  31. {
  32. if(data<t2->data)
  33. t2->lchild=t;
  34. else
  35. t2->rchild=t;
  36. }
  37. }
  38. return root;
  39. }
  40. struct node *search(struct node *root,int item)
  41. {
  42. struct node *t=root;
  43. while(t!=(struct node *)0 && t->data!=item)
  44. if(item<t->data)
  45. t=t->lchild;
  46. else
  47. t=t->rchild;
  48. return t;
  49. }
  50. struct node *delete(struct node *root,int item)
  51. {
  52. struct node *t1,*t,*par;
  53. t1=root;
  54. par=(struct node *)0;
  55. while(t1!=(struct node *)0 && t->data!=item)
  56. {
  57. par=t;
  58. if(item<t->data)
  59. t=t->lchild;
  60. else t=t->rchild;
  61. }
  62. if(t==(struct node *)0)
  63. printf("%d not found \n",item);
  64. else
  65. {
  66. if(t->lchild==(struct node *)0 && t->rchild==(struct node *)0)
  67. {
  68. if(par==(struct node *)0)
  69. root=(struct node *)0;
  70. else
  71. if(t->data>par->data)
  72. par->rchild==(struct node *)0;
  73. else
  74. par->lchild==(struct node *)0;
  75. }
  76. else if(t->lchild==(struct node *)0 || t->rchild==(struct node *)0)
  77. {
  78. if(par==(struct node *)0)
  79. root=root->lchild==(struct node *)0 ? t->rchild:t->lchild;
  80. else
  81. par->lchild=t->lchild==(struct node *)0 ? t->rchild:t->lchild;
  82. else
  83. {
  84. supar=t;
  85. suc=t->rchild;
  86. while(suc->lchild!=0)
  87. {
  88. supar=suc;
  89. suc=suc->lchild;
  90. }
  91. t->data=suc->data;
  92. if(suc->data<suc par->data)
  93. sucpar->lchild=suc->rchild;
  94. else
  95. sucpar->rchild=suc->rchild;
  96. t=suc;
  97. }
  98. free(t);
  99. return root;
  100. }
  101. int main()
  102. {
  103. struct node *t=(struct node *)0;
  104. int data,opt;
  105. for(; ;)
  106. {
  107. printf("1.insert\n");
  108.  
  109. printf("2.search\n");
  110. printf("3.delete\n");
  111. printf("4.exit\n");
  112. printf("option\n");
  113. scanf("%d",&opt);
  114. switch(opt)
  115. {
  116. case 1:
  117.       printf("data:");
  118.       scanf("%d",&data);
  119.       t=insert(t,data);
  120.       break;
  121. case 2:printf("item to search:");
  122.     scanf("%d",&data);
  123.     t1=search(t,data);
  124.     if(t!=(struct node *)0)
  125.     printf("not found");
  126.     else
  127.     printf("found");
  128.     break;
  129. case 3:printf("item to delete:");
  130.     scanf("%d",&data);
  131.     t=search(t,data);
  132.     printf("item deleted %d",data);
  133.     break;
  134. case 4:exit(0);
  135.     }
  136.     }
  137. }
Raw Paste

Login or Register to edit or fork this paste. It's free.