问个二叉排序树的问题

august

程序如下:

2. #include<stdio.h>
3. #include<stdlib.h>
4. #define MaxSize 100
5. #define MaxWidth 40
7. typedef struct node
8. {
9.     char data;
10.     struct node *left,*right;
11. }BTree;
13. BTree *creatree(char str[],int n)
14. {
15.     int i;
16.     BTree *BT=NULL,*p,*s;
17.     for(i=0;i<n;i++)
18.     {
19.         s=(BTree *)malloc(sizeof(BTree));
20.         s->data=str[i];s->left=s->right=NULL;
21.         p=BT;
22.         if(p==NULL)
23.             BT=s;
24.         else
25.         {
26.             while(p->left!=s && p->right!=s)
27.             {
28.                 if(s->data < p->data)
29.                 {
30.                     if(p->left!=NULL)
31.                         p=p->left;
32.                     else
33.                         p->left=s;
34.                 }
35.                 else
36.                 {
37.                     if(p->right!=NULL)
38.                         p=p->right;
39.                     else
40.                         p->right=s;
41.                 }
42.             }
43.         }
44.     }
45.     return(BT);
46. }
48. BTree *find(BTree *BT,int x) //寻找元素
49. {
50.     BTree *p=BT;
51.     while(p!=NULL && p->data!=x)
52.     {
53.         if(x<p->data)
54.             p=p->left;
55.         else
56.             p=p->right;
57.     }
58.     return p;
59. }
61. void del(BTree **BT,int x)
62. {
63.     BTree *p=*BT,*q,*r,*t;
64.     q=NULL;
65.     while(p!=NULL && p->data!=x)
66.         if(x < p->data)
67.         {
68.             q=p;
69.             p=p->left;
70.         }
71.         else
72.         {
73.             q=p;p=p->right;
74.         }
75.         if(p==NULL)
76.             printf("未发现数据为%d的结点\n",x);
77.         else if(p->left==NULL) //删除点无左子树
78.         {
79.             if(q==NULL)  //删除点是根结点
80.                 t=p->right;
81.             else if(q->left==p)
82.                 q->left=p->right;
83.             else
84.                 q->right=p->right;
85.         }
86.         else
87.         {
88.             r=p->left;
89.             while(r->right!=NULL)
90.                 r=r->right;
91.             r->right=p->right;
92.             if(q==NULL) t=p->left;    //删除点是根结点
93.             else if(q->left==p) q->left=p->left;
94.             else q->right=p->left;
95.         }
96. }
97. void disptree(BTree *BT)  //前序法显示二叉树
98. {
99.     BTree *stack[MaxSize],*p;
100.     int level[MaxSize][2],top,n,i,width=4;
101.     if(BT!=NULL)
102.     {
103.         printf("\n凹入表示法:\n");
104.         top=1;
105.         stack[top]=BT;
106.         level[top][0]=width;
107.         while(top>0)
108.         {
109.             p=stack[top];
110.             n=level[top][0];
111.             for(i=1;i<=n;i++)
112.                 printf(" ");
113.             printf("%c",p->data);
114.             for(i=n+1;i<=MaxWidth;i+=2)
115.                 printf("-");
116.             printf("\n");
117.             top--;
118.             if(p->right!=NULL)
119.             {
120.                 top++;
121.                 stack[top]=p->right;
122.                 level[top][0]=n+width;
123.                 level[top][1]=2;
124.             }
125.             if(p->left!=NULL)
126.             {
127.                 top++;
128.                 stack[top]=p->left;
129.                 level[top][0]=n+width;
130.                 level[top][1]=1;
131.             }
132.         }
133.     }
134. }
135. void main()
136. {
137.     BTree *B,*p;
138.     char str[]={'4','5','2','1','6','9','3','8'};
139.     printf("初始化二叉树：");
140.     B=creatree(str,8);
141.     disptree(B);
142.     p=find(B,'1');
143.     if(p==NULL) printf("值域为1的结点未找到！\n");
144.     else printf("值域为1的结点存在!\n");
145.     del(&B,'4');
146.     disptree(B);
147. }

复制代码

删除的过程是:先找到要删除的结点, 如果删除点没有左子树,则用右子树代替被删点,  如果删除点有左子树则在其左子树中找到最右结点来代替被删的结点.(即将那最右的结点的右指针置成删除点所指结点的右子树的根,然后用删除点的左子树的根结点代替被删除点所指的结点.)

在这一句del(&B,'4');  删除的是根结点(最顶那个结点)的时候,结果怎么那么奇怪呢?好像对,又好像不对,
还有它判断是否根结点的这一句 if(q==NULL) t=p->left;  t 好像只是接收p的left 但并没有改变 树原来的结构啊? 到底应该怎么去理解呢???