数据结构—二叉查找树相关

科科都不挂

下面代码中有两个删除二叉查找树结点的函数，一个是用递归来找目标节点，一个是循环来找目标节点。本意都是找目标节点，但是当我使用循环删除结点时时，后面的中序（或换成前序遍历）就会显示溢出。劳烦各位鱼油帮我看看啦~~

1. /*
   
2. 二叉查找树 BST
   
3. 
   
4. 1.二叉查找树的结构体
   
5. 2.插入
   
6. 3.删除
   
7. */
   
8. #include <stdio.h>
   
9. #include <stdlib.h>
   
10. 
    
11. typedef int Elemtype;
    
12. typedef struct TNode{
    
13.         Elemtype data;
    
14.         struct TNode *lchild, *rchild;
    
15. }TNode, *Tree;
    
16. 
    
17. Tree SearchBST (Tree T, Elemtype K);
    
18. void Delete (Tree *T);
    
19. int DeleteBST (Tree *T, Elemtype key);
    
20. int In_orderTraversal(Tree T);
    
21. 
    
22. //(递归)数据的查找,返回目标结点或NULL
    
23. Tree SearchBST (Tree T, Elemtype K)
    
24. {
    
25.         if (T == NULL || T->data == K)
    
26.                 return T;
    
27.         else if (K > T->data)
    
28.                 return SearchBST (T->rchild, K);
    
29.         else
    
30.                 return SearchBST (T->lchild, K);
    
31. }
    
32. 
    
33. //标准数据的插入
    
34. void InsertBST (Tree *T, Elemtype K)
    
35. {
    
36.         if (*T == NULL)
    
37.         {
    
38.                 *T = (Tree)malloc(sizeof(TNode));
    
39.                 (*T)->data = K;
    
40.                 (*T)->lchild = NULL;
    
41.                 (*T)->rchild = NULL;
    
42.         }
    
43.         else if (K > (*T)->data)
    
44.                 InsertBST (&((*T)->rchild), K);
    
45.         else if (K < (*T)->data) //这步也重要，因为要过滤掉相等的元素
    
46.                 InsertBST (&((*T)->lchild), K);
    
47. }
    
48. 
    
49. ////标准数据的删除
    
50. //int DeleteBST (Tree *T, Elemtype key)
    
51. //{
    
52. //        if (*T == NULL)
    
53. //                return 0;
    
54. //       
    
55. //        //查找合适的结点
    
56. //        if (key > (*T)->data)
    
57. //                return DeleteBST (&(*T)->rchild, key);
    
58. //        else if (key < (*T)->data)
    
59. //                return DeleteBST (&(*T)->lchild, key);
    
60. //        else
    
61. //        {
    
62. //                printf ("(删除%d)", (*T)->data);
    
63. //                Delete (T);
    
64. //                return 1;
    
65. //        }
    
66. //}
    
67. 
    
68. ////标准数据的删除
    
69. //int DeleteBST (Tree *T, Elemtype key)
    
70. //{
    
71. //        Tree current;
    
72. //       
    
73. //        current = *T;
    
74. //        //查找合适的结点
    
75. //        while (current != NULL)
    
76. //        {
    
77. //                if (key > current->data)
    
78. //                        current = current->rchild;
    
79. //                else if (key < current->data)
    
80. //                        current = current->lchild;
    
81. //                else
    
82. //                {
    
83. //                        printf ("(删除%d)", current->data);
    
84. //                        Delete (&current);
    
85. //                        return 1;
    
86. //                }
    
87. //        }
    
88. //        return 0;
    
89. //}
    
90. 
    
91. void Delete (Tree *T)
    
92. {
    
93.         Tree temp;
    
94.         Tree cur; //当前的结点
    
95.        
    
96.         //ps:不需要特意去判断是否没有两个孩子
    
97.         if ((*T)->lchild == NULL) //结点没左孩子
    
98.         {
    
99.                 temp = *T;
    
100.                 *T = (*T)->rchild; //接上右孩子
     
101.                 free (temp);
     
102.         }
     
103.         else if ((*T)->rchild == NULL)//结点没右孩子
     
104.         {
     
105.                 temp = *T;
     
106.                 *T = (*T)->lchild; //接上左孩子
     
107.                 free (temp);
     
108.         }
     
109.         else //两个孩子都有
     
110.         {
     
111.                 cur = (*T)->lchild;
     
112.                 while (cur->rchild != NULL) //找左子树中最大的结点（左子树中最右边）
     
113.                         cur = cur->rchild;
     
114.                
     
115.                 (*T)->data = cur->data; //移动位置 (数据)
     
116.                 Delete (&cur); //删除左子树的最大结点（缓存）
     
117.         }
     
118. }
     
119. 
     
120. int In_orderTraversal(Tree T)
     
121. {
     
122.         if (T == NULL)
     
123.                 return 0;
     
124.        
     
125.         printf ("-%d-", T->data); //输出数据
     
126.         In_orderTraversal(T->lchild); //不断查找左子树
     
127.         In_orderTraversal(T->rchild); //如果存在右子树的话，就查右子树有无左子树
     
128. }
     
129. 
     
130. int main (void)
     
131. {
     
132.         Tree T = NULL;
     
133.         int num;
     
134.        
     
135.         scanf ("%d", &num);
     
136.         while (num != 0)
     
137.         {
     
138.                 InsertBST (&T, num);
     
139.                 scanf ("%d", &num);
     
140.         }
     
141.        
     
142.         In_orderTraversal (T); //中序遍历
     
143.        
     
144.         scanf ("%d", &num);
     
145.         while (num != 0)
     
146.         {
     
147.                 DeleteBST (&T, num);
     
148.                 In_orderTraversal (T); //中序遍历
     
149.                 scanf ("%d", &num);
     
150.         }
     
151.        
     
152.         return 0;
     
153. }

复制代码

xieglt

该了两个函数

1. int DeleteBST (Tree *T, Elemtype key)
   
2. {
   
3.         Tree current = *T;
   
4.         Tree father = *T;
   
5.         int flag = 0;
   
6.        
   
7.         //问题出在删除当点节点后，当前节点在其父节点中的链接并没有被改变。
   
8.         //因此，需要设置一个当前节点的父节点指针，删除当前节点后，重新设置
   
9.         //在父节点中的链接
   
10.         while(current != NULL)
    
11.         {
    
12.                 if(key > current->data)
    
13.                 {
    
14.                         father = current;
    
15.                         current = current->rchild;
    
16.                         flag = -1;
    
17.                 }
    
18.                 else if(key < current->data)
    
19.                 {
    
20.                         father = current;
    
21.                         current = current->lchild;
    
22.                         flag = 1;
    
23.                 }
    
24.                 else
    
25.                 {
    
26.                         printf("删除(%d)",key);
    
27.                         Delete(&current);
    
28.                         //根据 flag 重新链接树
    
29.                         //flag = 0 ，则删除的是根节点
    
30.                         if(flag == 0)
    
31.                         {
    
32.                                 *T = current;
    
33.                         }
    
34.                         //=-1 删除的是父节点的右节点
    
35.                         else if(flag == -1)
    
36.                         {
    
37.                                 father->rchild = current;
    
38.                         }
    
39.                         //=1 删除的是父节点的左节点
    
40.                         else
    
41.                         {
    
42.                                 father->lchild = current;
    
43.                         }
    
44.                         break;
    
45.                 }
    
46.         }
    
47.         return 0;
    
48. }
    
49. 
    
50. void Delete (Tree *T)
    
51. {
    
52.         Tree temp;
    
53.         Tree cur; //当前的结点
    
54.         
    
55.         //ps:不需要特意去判断是否没有两个孩子
    
56.         if ((*T)->lchild == NULL) //结点没左孩子
    
57.         {
    
58.                 temp = *T;
    
59.                 *T = (*T)->rchild; //接上右孩子
    
60.                 free (temp);
    
61.         }
    
62.         else if ((*T)->rchild == NULL)//结点没右孩子
    
63.         {
    
64.                 temp = *T;
    
65.                 *T = (*T)->lchild; //接上左孩子
    
66.                 free (temp);
    
67.         }
    
68.         else //两个孩子都有
    
69.         {
    
70.                         /*
    
71.                 cur = (*T)->lchild;
    
72.                 while (cur->rchild != NULL) //找左子树中最大的结点（左子树中最右边）
    
73.                         cur = cur->rchild;
    
74.                 (*T)->data = cur->data; //移动位置 (数据)
    
75.                 Delete (&cur); //删除左子树的最大结点（缓存）
    
76.                         */
    
77.                         /*
    
78.                         按照规则，左子节点小于父节点，右子节点大于父亲节点，比如
    
79.                                          10
    
80.                                          |
    
81.                                         / \
    
82.                                       5  20(删除20)
    
83.                                          /   \
    
84.                                         16    25
    
85.                                        /  \    / \
    
86.                                       15  18   24 26
    
87.                                           / \
    
88.                                        17  19
    
89.                         按规则删除20后，将该节点替换其子节点16，其右节点25应该作为19的右子节点
    
90.                         代码实现如下：
    
91.                         */
    
92.                         //取得当前节点
    
93.                         temp = * T;
    
94.                         //保存当前节点的右子节点
    
95.                         cur = (*T)->rchild;
    
96.                         //将当前节点替换为其左子节点
    
97.                         *T = (*T)->lchild;
    
98.                         //释放内存
    
99.                         free(temp);
    
100.                         //找左子节点中的最右子节点。
     
101.                         temp = *T;
     
102.                         while(temp->rchild != NULL)
     
103.                         {
     
104.                                 temp = temp->rchild;
     
105.                         }
     
106.                         //连接右子节点
     
107.                         temp->rchild = cur;
     
108.         }
     
109. }
     

复制代码