# 二叉排序树查找，插入，删除

1. typedef struct BiTNode
2. {
3.     int data;
4.     struct BiTNode *lchild, *rchild;
5. }BiTNode, *BiTree;

6. //递归查找二叉排序树T中是否存在key
7. //指针f指向T的双亲，其初始化调用值为NULL
8. //若查找成功，则指针p指向该数据元素节点，并返回TURE
9. //否则指针p指向查找路径上访问的最后一个节点并返回FALSE
10. bool SearchBST(BiTree T, int key, BiTree f, BiTree *p)
11. {
12.     if(!T)
13.     {
14.         *p=f;
15.         return FALSE;
16.     }
17.     else if(key==T->data)
18.     {
19.      *p=T;
20.         return TRUE;
21.     }
22.     else if(key<T->data)
23.     {
24.         return SearchBST(T->lchild, key, T, p);
25.     }
26.     else
27.     {
28.         return SearchBST(T->rchild, key, T, p);
29.     }
30. }

31. //当二叉树排序树T中不存在关键字等于key的数据元素时
32. //插入key并返回TRUE, 否则返回FALSE

33. bool InsertBST(BiTree *T, int key)
34. {
35.     BiTree p,s;
36.     if(!SearchBST(*T, key, NULL, &p))
37.     {
38.         s=(BiTree)malloc(sizeof(BiTNode));
39.         s->data=key;
40.         s->lchild=s->rchild=NULL;
41.         if(!p)
42.         {
43.             *T=s;
44.         }
45.         else if(key<p->data)
46.         {
47.             p->lchild=s;
48.         }
49.         else
50.         {
51.             p->rchild=s;
52.         }
53.         return true;
54.     }
55.     else
56.     {
57.         return false;
58.     }
59. }

60. bool Delete(BiTree *p)
61. {
62.     BiTree q,s;
63.     if( (*p)->rchild==NULL )
64.     {
65.         q=*p; *p=(*p)->lchild; free(q);
66.     }
67.     else if( (*p)->lchild==NULL )
68.     {
69.         q=*p; *p=(*p)->rchild; free(q);
70.     }
71.     else
72.     {
73.         q=*p; s=(*p)->lchild;
74.         while(s->rchild)
75.         {
76.             q=s; s=s->rchild;
77.         }
78.         (*p)->data=s->data;
79.         if(q!=*p)
80.             q->rchild=s->lchild;
81.         else
82.             q->lchild=s->rchild;
83.     }
84.     return true;
85. }

86. bool DeleteBST(BiTree *T, int key)
87. {
88.     if(!*T)
89.     {
90.         return false;
91.     }
92.     else
93.     {
94.         if(key==(*T)->data)
95.         {
96.             return Delete(T);
97.         }
98.         else if (key<(*T)->data)
99.         {
100.             return DeleteBST(&(*T)->lchild, key);
101.         }
102.         else
103.         {
104.             return DeleteBST(&(*T)->rchild, key);
105.         }
106.     }
107. }

• 博文量
263
• 访问量
209120