8.3樹表的查找

1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef int KeyType;//關鍵字
 5 typedef int DataType;//其他資料域
 6 
 7 struct node
 8 {
 9     KeyType key;//關鍵字
10     DataType other;//其他資料域
11     struct node *lchild, *rchild;//左右子樹指針
12 };
13 typedef struct node BSTNode;//結點類型
14 
15 BSTNode *Deletebst(BSTNode *T, KeyType x);//查找需要删除的結點
16 BSTNode *Delete(BSTNode *T);//删除結點
17 
18 void main()
19 {
20 
21 }
22 
23 BSTNode *Deletebst(BSTNode *T, KeyType x)//查找需要删除的結點
24 {
25     if (!T)//找不到
26     {
27         return NULL;
28     }
29     else
30     {
31         if (T->key == x)
32         {
33             return Delete(T);
34         }
35         else if (T->key > x)
36         {
37             return Deletebst(T->lchild, x);
38         }
39         else
40         {
41             return Deletebst(T->rchild, x);
42         }
43     }
44 }
45 
46 BSTNode *Delete(BSTNode *T)//删除結點
47 {
48     BSTNode *q, *s;
49 
50     if (T->rchild == NULL)
51     {
52         q = T;
53         T = T->lchild;
54         free(q);
55     }
56     else if (T->lchild == NULL)
57     {
58         {
59             q = T;
60             T = T->rchild;
61             free(q);
62         }
63     }
64     else
65     {
66         q = T;
67         s = T->lchild;
68         while (s->rchild)
69         {
70             q = s;
71             s = s->rchild;
72         }
73         T->key = s->key;
74 
75         if (q != T)
76         {
77             q->rchild = s->lchild;
78         }
79         else
80         {
81             q->lchild = s->lchild;
82         }
83 
84         free(s);
85     }
86 
87     return T;
88 }