二叉查找树的插入和删除详解

╰半橙微兮° 2022-06-12 07:38 180阅读 0赞

二叉查找树是如下定义的：

(1) 左子树不空，则左子树上的所有结点的值均小于根结点的值

(2) 右子树不空，则右子树上的所有结点的值均大于根结点的值

二叉查找树可以为空，二叉查找树是递归定义的，也就是说其左右子树也为二叉查找树。

二叉查找树是一种动态查找表，可以进行动态地插入和删除。前面的定义中我们假定二叉查找树不含有相同元素。

由定义可知二叉查找树的中序序列为一个递增序列

常见的二叉查找树操作有求最小元素findMin()，求最大元素findMax()，判断查找树是否非空isEmpty()，判断是否包含给定元素contains()，输出所有元素printTree()，置空查找树makeEmpty()，向查找树中插入给定元素x，insert(x)，在查找树中删除给定元素x，remove(x)。

下面先讨论最重要的插入和删除操作，接着给出完整的C风格实现**。**

**1、基本结构定义**

**\[cpp\]**  view plain  copy

print ?

1.  class Student
2.  \{
3.  public:
4.  int key;
5.  string major;
6.  Student(int k=int(),string s="") : key(k), major(s)\{\}
7.  void operator=(const Student& rhs);
8.  \};
9.  typedef Student ElementType;
10. typedef int KeyType;
11. 
12. typedef struct BSTNode
13. \{
14. ElementType data;
15. struct BSTNode\* lchild;
16. struct BSTNode\* rchild;
17. \}BSTNode, \*BST;

class Student
    {
    	public:
    		int key;
    		string major;
    		Student(int k=int(),string s="") : key(k), major(s){}
    		void operator=(const Student& rhs);
    };
    typedef Student ElementType;
    typedef int KeyType;
    
    typedef struct BSTNode
    {
    	ElementType data;
        struct BSTNode* lchild;
        struct BSTNode* rchild;
    }BSTNode, *BST;

详细信息请看后面完整程序

**2、插入**

(1) 不允许插入相同关键字，若二叉查找树中存在该关键字，则不插入

(2) 我们可以先检索二叉树，看查找树中是否含有该关键字，若不存在，再做一次扫描将结点插入到适当位置。使用这种方式，为插入一个该关键字，做了两次扫描。

(3) 注意到，插入的结点总是作为某一叶子节点的子结点，我们可以在第一次扫描过程中就确定待插入的位置，即把**查找是否存在该关键字**和**查找可能的插入点**在一次扫描中完成，提高插入效率。

(4) 查找递归实现

**\[cpp\]**  view plain  copy

print ?

1.  /\*
2.   description:在以t为根结点的二叉查找树中，查找关键字为key的结点
3.   若查找成功，指针p指向该结点，返回true,
4.   否则指向查找路径上的最后一个结点并返回false
5.   指针f指向根结点t的父节点 
6.  \*/
7.  bool searchBST\_recursion(BST t, KeyType key, BSTNode\* f, BSTNode\*& p)
8.  \{
9.  if(t == NULL)//查找失败 
10. \{
11. p = f;
12. return false;
13. \}
14. else if(key == t->data.key)//查找成功 
15. \{
16. p = t;
17. return true;
18. \}
19. else if(key < t->data.key)
20. return searchBST\_recursion(t->lchild,key,t,p);//左子树中继续查找 
21. else
22. return searchBST\_recursion(t->rchild,key,t,p);//右子树中继续查找 
23. \}

/*
      description:在以t为根结点的二叉查找树中，查找关键字为key的结点
      若查找成功，指针p指向该结点，返回true,
      否则指向查找路径上的最后一个结点并返回false
      指针f指向根结点t的父节点 
    */
    bool searchBST_recursion(BST t, KeyType key, BSTNode* f, BSTNode*& p)
    {
    	if(t == NULL)//查找失败 
    	{
    		p = f;
    		return false;
    	}
    	else if(key == t->data.key)//查找成功 
    	{
    		p = t;
    		return true;
    	}
    	else if(key < t->data.key)
    		return searchBST_recursion(t->lchild,key,t,p);//左子树中继续查找 
    	else 
    		return searchBST_recursion(t->rchild,key,t,p);//右子树中继续查找 
    }

(5) 查找非递归实现

**\[cpp\]**  view plain  copy

print ?

1.  bool searchBST(BST t, KeyType key, BSTNode\* f, BSTNode\* &p)
2.  \{
3.  while(t && key != t->data.key)
4.  \{
5.  f = t;
6.  if(key < t->data.key)
7.  \{
8.  t = t->lchild;
9.  \}
10. else
11. \{
12. t = t->rchild;
13. \}
14. \}
15. if(t)//查找成功 
16. \{
17. p = t;
18. return true;
19. \}
20. else
21. \{
22. p = f;
23. return false;
24. \}
25. \}

bool searchBST(BST t, KeyType key, BSTNode* f, BSTNode* &p)
    {
    	while(t && key != t->data.key)
    	{
    		f = t;
    		if(key < t->data.key)
    		{
    			t = t->lchild;
    		}
    		else
    		{
    			t = t->rchild;
    		}			
    	}
    	if(t)//查找成功 
    	{
    		p = t;
    		return true;
    	}
    	else
    	{
    		p = f;
    		return false;
    	}
    }

(6) 插入给定元素

**\[cpp\]**  view plain  copy

print ?

1.  void insertBST(BST& t,ElementType elem)
2.  \{
3.  BSTNode \* p = NULL;
4.  if(!searchBST(t, elem.key, NULL, p))//查找失败，不含该关键字，可以插入 
5.  \{
6.  BSTNode \* s = new BSTNode;
7.  s->data = elem;//可能需要重载= 
8.  s->lchild = NULL;
9.  s->rchild = NULL;
10. 
11. if(p == NULL)//查找树为空 
12. \{
13. t = s;//置s为根结点 
14. \}
15. else if(elem.key < p->data.key)
16. \{
17. p->lchild = s; //\*s为p左结点 
18. \}
19. else
20. \{
21. p->rchild = s; //\*s为p右结点 
22. \}
23. \}
24. \}

void insertBST(BST& t,ElementType elem)
    {
    	BSTNode * p = NULL;
    	if(!searchBST(t, elem.key, NULL, p))//查找失败，不含该关键字，可以插入 
    	{
    		BSTNode * s = new BSTNode;
    		s->data = elem;//可能需要重载= 
    		s->lchild = NULL;
    		s->rchild = NULL;
    		
    		if(p == NULL)//查找树为空 
    		{
    			t = s;//置s为根结点 
    		}
    		else if(elem.key < p->data.key)
    		{
    			p->lchild = s;	//*s为p左结点 
    		}
    		else
    		{
    			p->rchild = s;	//*s为p右结点 
    		}
    	}
    }

**3、删除**

在二叉查找树中删除一个给定的结点p有三种情况

(1) 结点p无左右子树，则直接删除该结点，修改父节点相应指针

(2) 结点p有左子树（右子树），则把p的左子树（右子树）接到p的父节点上

(3) 左右子树同时存在，则有三种处理方式

a. 找到结点p的中序直接前驱结点s，把结点s的数据转移到结点p，然后删除结点s，由于结点s为p的左子树中最右的结点，因而s无右子树，删除结点s可以归结到情况(2)。严蔚敏数据结构P230-231就是该处理方式。

b. 找到结点p的中序直接后继结点s，把结点s的数据转移到结点p，然后删除结点s，由于结点s为p的右子树总最左的结点，因而s无左子树，删除结点s可以归结到情况(2)。算法导论第2版P156-157该是该处理方式。

c. 找到p的中序直接前驱s，将p的左子树接到父节点上，将p的右子树接到s的右子树上，然后删除结点p。

使用处理方式a的代码如下：

**\[cpp\]**  view plain  copy

print ?

1.  //从二叉查找树中删除指针p所指向的结点 ,p非空,删除前驱方式 
2.  void removeNode1(BSTNode \*& p)
3.  \{
4.  BSTNode \*q = NULL;
5.  if(!p->rchild)//\*p的右子树为空 
6.  \{
7.  q = p;
8.  p = p->lchild;
9.  delete q;
10. \}
11. else if(!p->lchild)//\*p的左子树为空 
12. \{
13. q = p;
14. p = p->rchild;
15. delete q;
16. \}
17. else//左右子树均不空 
18. \{
19. BSTNode \*s = NULL;
20. q = p;
21. s = p->lchild; //左子树根结点
22. while(s->rchild) //寻找结点\*p的中序前驱结点， 
23. \{ //也就是以p->lchild为根结点的子树中最右的结点 
24. q = s; //\*s指向\*p的中序前驱 
25. s = s->rchild; //\*q指向\*s的父节点 
26. \}
27. p->data = s->data; //\*s结点中的数据转移到\*p结点，然后删除\*s
28. if(q != p) //p->lchild右子树非空 
29. \{
30. q->rchild = s->lchild;//把\*s的左子树接到\*q的右子树上 
31. \}
32. else //p->lchild右子树为空 ,此时q ==p 
33. \{
34. q->lchild = s->lchild;//把\*s的左子树接到\*q的左子树上 
35. \}
36. delete s; //删除结点\*s 
37. \}
38. \}

//从二叉查找树中删除指针p所指向的结点 ,p非空,删除前驱方式 
    void removeNode1(BSTNode *& p)
    {
    	BSTNode *q = NULL;
    	if(!p->rchild)//*p的右子树为空 
    	{
    		q = p;
    		p = p->lchild;
    		delete q;
    	}
    	else if(!p->lchild)//*p的左子树为空 
    	{
    		q = p;
    		p = p->rchild;
    		delete q;
    	}
    	else//左右子树均不空 
    	{
    		BSTNode *s = NULL;
    		q = p;
    		s = p->lchild;		//左子树根结点
    		while(s->rchild)	//寻找结点*p的中序前驱结点，					
    		{					//也就是以p->lchild为根结点的子树中最右的结点 
    			q = s;			//*s指向*p的中序前驱 
    			s = s->rchild;	//*q指向*s的父节点 
    		}
    		p->data = s->data;	//*s结点中的数据转移到*p结点，然后删除*s
    		if(q != p)			//p->lchild右子树非空 
    		{
    			q->rchild = s->lchild;//把*s的左子树接到*q的右子树上 
    		}
    		else				//p->lchild右子树为空 ,此时q ==p 
    		{
    			q->lchild = s->lchild;//把*s的左子树接到*q的左子树上 
    		}
    		delete s;			//删除结点*s 
    	}
    }

使用处理方式b的代码如下：

**\[cpp\]**  view plain  copy

print ?

1.  //从二叉查找树中删除指针p所指向的结点 ,p非空,删除后继方式 
2.  void removeNode2(BSTNode \*& p)
3.  \{
4.  BSTNode \*q = NULL;
5.  if(!p->rchild)//\*p的右子树为空 
6.  \{
7.  q = p;
8.  p = p->lchild;
9.  delete q;
10. \}
11. else if(!p->lchild)//\*p的左子树为空 
12. \{
13. q = p;
14. p = p->rchild;
15. delete q;
16. \}
17. else//左右子树均不空 
18. \{
19. BSTNode \*s = NULL;
20. q = p;
21. s = p->rchild; //右子树根结点
22. while(s->lchild) //寻找结点\*p的中序后继结点， 
23. \{ //也就是以p->rchild为根结点的子树中最左的结点 
24. q = s; //\*s指向\*p的中序后继 
25. s = s->lchild; //\*q指向\*s的父节点 
26. \}
27. p->data = s->data; //\*s结点中的数据转移到\*p结点，然后删除\*s
28. if(q != p) //p->rchild左子树非空 
29. \{
30. q->lchild = s->rchild;//把\*s的右子树接到\*q的左子树上 
31. \}
32. else //p->rchild左子树为空 ,此时q ==p 
33. \{
34. q->rchild = s->rchild;//把\*s的右子树接到\*q的右子树上 
35. \}
36. delete s; //删除结点\*s 
37. \}
38. \}

//从二叉查找树中删除指针p所指向的结点 ,p非空,删除后继方式 
    void removeNode2(BSTNode *& p)
    {
    	BSTNode *q = NULL;
    	if(!p->rchild)//*p的右子树为空 
    	{
    		q = p;
    		p = p->lchild;
    		delete q;
    	}
    	else if(!p->lchild)//*p的左子树为空 
    	{
    		q = p;
    		p = p->rchild;
    		delete q;
    	}
    	else//左右子树均不空 
    	{
    		BSTNode *s = NULL;
    		q = p;
    		s = p->rchild;		//右子树根结点
    		while(s->lchild)	//寻找结点*p的中序后继结点，					
    		{					//也就是以p->rchild为根结点的子树中最左的结点 
    			q = s;			//*s指向*p的中序后继 
    			s = s->lchild;	//*q指向*s的父节点 
    		}
    		p->data = s->data;	//*s结点中的数据转移到*p结点，然后删除*s
    		if(q != p)			//p->rchild左子树非空 
    		{
    			q->lchild = s->rchild;//把*s的右子树接到*q的左子树上 
    		}
    		else				//p->rchild左子树为空 ,此时q ==p 
    		{
    			q->rchild = s->rchild;//把*s的右子树接到*q的右子树上 
    		}
    		delete s;			//删除结点*s 
    	}
    }

使用处理方式c的代码如下：

**\[cpp\]**  view plain  copy

print ?

1.  //从二叉查找树中删除指针p所指向的结点 ,p非空,直接删除p的方式 
2.  void removeNode3(BSTNode \*& p)
3.  \{
4.  BSTNode \*q = NULL;
5.  if(!p->rchild)//\*p的右子树为空 
6.  \{
7.  q = p;
8.  p = p->lchild;
9.  delete q;
10. \}
11. else if(!p->lchild)//\*p的左子树为空 
12. \{
13. q = p;
14. p = p->rchild;
15. delete q;
16. \}
17. else//左右子树均不空 
18. \{
19. BSTNode \*s = NULL;
20. q = p;
21. s = p->lchild; //左子树根结点
22. while(s->rchild) //寻找结点\*p的中序前驱结点， 
23. \{ //也就是以\*s为根结点的子树中最右的结点 
24. s = s->rchild;
25. \}
26. s->rchild = p->rchild;//\*p的右子树接到\*s的右子树上 
27. p = p->lchild; //\*p的左子树接到父节点上 
28. delete q; //删除结点\*q 
29. \}
30. \}

//从二叉查找树中删除指针p所指向的结点 ,p非空,直接删除p的方式 
    void removeNode3(BSTNode *& p)
    {
    	BSTNode *q = NULL;
    	if(!p->rchild)//*p的右子树为空 
    	{
    		q = p;
    		p = p->lchild;
    		delete q;
    	}
    	else if(!p->lchild)//*p的左子树为空 
    	{
    		q = p;
    		p = p->rchild;
    		delete q;
    	}
    	else//左右子树均不空 
    	{
    		BSTNode *s = NULL;
    		q = p;
    		s = p->lchild;		//左子树根结点
    		while(s->rchild)	//寻找结点*p的中序前驱结点，					
    		{					//也就是以*s为根结点的子树中最右的结点 
    			s = s->rchild;	 
    		}
    		s->rchild = p->rchild;//*p的右子树接到*s的右子树上 
    		p = p->lchild;			//*p的左子树接到父节点上 
    		delete q;			//删除结点*q 
    	}
    }

在二叉查找树中删除含有给定关键字的元素结点的递归函数如下：

**\[cpp\]**  view plain  copy

print ?

1.  //删除关键字为key的元素结点 -递归 
2.  void removeBST\_recursion(BST& t, KeyType key)
3.  \{
4.  if(t)
5.  \{
6.  if(key < t->data.key)
7.  \{
8.  removeBST\_recursion(t->lchild,key);
9.  \}
10. else if(t->data.key < key)
11. \{
12. removeBST\_recursion(t->rchild,key);
13. \}
14. else//找到关键字为key的元素 
15. \{
16. // removeNode1(t);//删除结点\*t 
17. // removeNode2(t);
18. removeNode3(t);
19. \}
20. \}
21. \}

//删除关键字为key的元素结点 -递归 
    void removeBST_recursion(BST& t, KeyType key)
    {
    	if(t)
    	{
    		if(key < t->data.key)
    		{
    			removeBST_recursion(t->lchild,key);
    		}
    		else if(t->data.key < key)
    		{
    		 	removeBST_recursion(t->rchild,key);
    		}
    		else//找到关键字为key的元素 
    		{
    //			removeNode1(t);//删除结点*t 
    //			removeNode2(t);
    			removeNode3(t);
    		}
        }
    }

**注：**

(1)由于该函数是递归的，且用到了指针引用，我们在前面的删除给定结点p的函数中，修改p就相当于修改了父节点，这是和C中不同的地方，在C中要达到这种效果，可以使用指向指针的指针变量。

(2)只给出了该函数的递归实现，没有给出非递归实现，是为了避免把代码弄乱。要实现非递归，可以修改前面的删除结点p的函数，添加一个指向结点p的父节点的指针引用f。同时要修改查找是否存在关键字为key的非递归查找函数，使其在得到p的同时，可以得到其父节点。这样我们在实现非递归时，只需扫描一遍，即调用查找函数，如果有该关键字，我们就可以得到指向该结点的指针p和指向结点p的父节点f，然后调用删除给定结点p的函数即可。

**4、完整测试程序**

**\[cpp\]**  view plain  copy

print ?

1.  \#include <cstdlib>
2.  \#include <iostream>
3.  \#include <string>
4.  
5.  using namespace std;
6.  
7.  class Student
8.  \{
9.  public:
10. int key;
11. string major;
12. //other data
13. Student(int k=int(),string s="") : key(k), major(s)\{\}
14. //重载赋值运算符 
15. void operator=(const Student& rhs)
16. \{
17. if(this != &rhs)
18. \{
19. key = rhs.key;
20. major = rhs.major;
21. \}
22. \}
23. \};
24. //重载<<,便于输出自定义类对象 
25. ostream& operator<<(ostream &out, const Student& s)
26. \{
27. out<<"("<<s.key<<","<<s.major<<")";
28. \}
29. 
30. typedef Student ElementType;
31. typedef int KeyType;
32. 
33. typedef struct BSTNode
34. \{
35. ElementType data;
36. struct BSTNode\* lchild;
37. struct BSTNode\* rchild;
38. \}BSTNode, \*BST;
39. 
40. 
41. /\*
42.  description:在以t为根结点的二叉查找树中，查找关键字为key的结点
43.  若查找成功，指针p指向该结点，返回true,
44.  否则指向查找路径上的最后一个结点并返回false
45.  指针f指向根结点t的父节点 
46. \*/
47. //bool searchBST\_recursion(BST t, KeyType key, BSTNode\* f, BSTNode\*& p)
48. //\{ 
49. // if(t == NULL)//查找失败 
50. // \{ 
51. // p = f;
52. // return false;
53. // \}
54. // else if(key == t->data.key)//查找成功 
55. // \{ 
56. // p = t;
57. // return true;
58. // \}
59. // else if(key < t->data.key)
60. // return searchBST\_recursion(t->lchild,key,t,p);//左子树中继续查找 
61. // else 
62. // return searchBST\_recursion(t->rchild,key,t,p);//右子树中继续查找 
63. //\}
64. 
65. //非递归查找 
66. bool searchBST(BST t, KeyType key, BSTNode\* f, BSTNode\* &p)
67. \{
68. while(t && key != t->data.key)
69. \{
70. f = t;
71. if(key < t->data.key)
72. \{
73. t = t->lchild;
74. \}
75. else
76. \{
77. t = t->rchild;
78. \}
79. \}
80. if(t)//查找成功 
81. \{
82. p = t;
83. return true;
84. \}
85. else
86. \{
87. p = f;
88. return false;
89. \}
90. \}
91. 
92. //插入给定元素 
93. void insertBST(BST& t,ElementType elem)
94. \{
95. BSTNode \* p = NULL;
96. 
97. if(!searchBST(t, elem.key, NULL, p))//查找失败，不含该关键字，可以插入 
98. \{
99. BSTNode \* s = new BSTNode;
100. s->data = elem;//可能需要重载= 
101. s->lchild = NULL;
102. s->rchild = NULL;
103. 
104. if(p == NULL)//查找树为空 
105. \{
106. t = s;//置s为根结点 
107. \}
108. else if(elem.key < p->data.key)
109. \{
110. p->lchild = s; //\*s为p左结点 
111. \}
112. else
113. \{
114. p->rchild = s; //\*s为p右结点 
115. \}
116. \}
117. \}
118. 
119. //从二叉查找树中删除指针p所指向的结点 ,p非空,删除前驱方式 
120. void removeNode1(BSTNode \*& p)
121. \{
122. BSTNode \*q = NULL;
123. if(!p->rchild)//\*p的右子树为空 
124. \{
125. q = p;
126. p = p->lchild;
127. delete q;
128. \}
129. else if(!p->lchild)//\*p的左子树为空 
130. \{
131. q = p;
132. p = p->rchild;
133. delete q;
134. \}
135. else//左右子树均不空 
136. \{
137. BSTNode \*s = NULL;
138. q = p;
139. s = p->lchild; //左子树根结点
140. while(s->rchild) //寻找结点\*p的中序前驱结点， 
141. \{ //也就是以p->lchild为根结点的子树中最右的结点 
142. q = s; //\*s指向\*p的中序前驱 
143. s = s->rchild; //\*q指向\*s的父节点 
144. \}
145. p->data = s->data; //\*s结点中的数据转移到\*p结点，然后删除\*s
146. if(q != p) //p->lchild右子树非空 
147. \{
148. q->rchild = s->lchild;//把\*s的左子树接到\*q的右子树上 
149. \}
150. else //p->lchild右子树为空 ,此时q ==p 
151. \{
152. q->lchild = s->lchild;//把\*s的左子树接到\*q的左子树上 
153. \}
154. delete s; //删除结点\*s 
155. \}
156. \}
157. 
158. //从二叉查找树中删除指针p所指向的结点 ,p非空,删除后继方式 
159. void removeNode2(BSTNode \*& p)
160. \{
161. BSTNode \*q = NULL;
162. if(!p->rchild)//\*p的右子树为空 
163. \{
164. q = p;
165. p = p->lchild;
166. delete q;
167. \}
168. else if(!p->lchild)//\*p的左子树为空 
169. \{
170. q = p;
171. p = p->rchild;
172. delete q;
173. \}
174. else//左右子树均不空 
175. \{
176. BSTNode \*s = NULL;
177. q = p;
178. s = p->rchild; //右子树根结点
179. while(s->lchild) //寻找结点\*p的中序后继结点， 
180. \{ //也就是以p->rchild为根结点的子树中最左的结点 
181. q = s; //\*s指向\*p的中序后继 
182. s = s->lchild; //\*q指向\*s的父节点 
183. \}
184. p->data = s->data; //\*s结点中的数据转移到\*p结点，然后删除\*s
185. if(q != p) //p->rchild左子树非空 
186. \{
187. q->lchild = s->rchild;//把\*s的右子树接到\*q的左子树上 
188. \}
189. else //p->rchild左子树为空 ,此时q ==p 
190. \{
191. q->rchild = s->rchild;//把\*s的右子树接到\*q的右子树上 
192. \}
193. delete s; //删除结点\*s 
194. \}
195. \}
196. 
197. //从二叉查找树中删除指针p所指向的结点 ,p非空,直接删除p的方式 
198. void removeNode3(BSTNode \*& p)
199. \{
200. BSTNode \*q = NULL;
201. if(!p->rchild)//\*p的右子树为空 
202. \{
203. q = p;
204. p = p->lchild;
205. delete q;
206. \}
207. else if(!p->lchild)//\*p的左子树为空 
208. \{
209. q = p;
210. p = p->rchild;
211. delete q;
212. \}
213. else//左右子树均不空 
214. \{
215. BSTNode \*s = NULL;
216. q = p;
217. s = p->lchild; //左子树根结点
218. while(s->rchild) //寻找结点\*p的中序前驱结点， 
219. \{ //也就是以\*s为根结点的子树中最右的结点 
220. s = s->rchild;
221. \}
222. s->rchild = p->rchild;//\*p的右子树接到\*s的右子树上 
223. p = p->lchild; //\*p的左子树接到父节点上 
224. delete q; //删除结点\*q 
225. \}
226. \}
227. 
228. //删除关键字为key的元素结点 -递归 
229. void removeBST\_recursion(BST& t, KeyType key)
230. \{
231. if(t)
232. \{
233. if(key < t->data.key)
234. \{
235. removeBST\_recursion(t->lchild,key);
236. \}
237. else if(t->data.key < key)
238. \{
239. removeBST\_recursion(t->rchild,key);
240. \}
241. else//找到关键字为key的元素 
242. \{
243. // removeNode1(t);//删除结点\*t 
244. // removeNode2(t);
245. removeNode3(t);
246. \}
247. \}
248. \}
249. 
250. 
251. //输出二叉查找树，中序递归 
252. void printTree(const BST & t)
253. \{
254. if(t)
255. \{
256. printTree(t->lchild);
257. cout<<t->data<<" ";
258. printTree(t->rchild);
259. \}
260. \}
261. 
262. int main(int argc, char \*argv\[\])
263. \{
264. const int N = 10;
265. BST root = NULL;
266. 
267. for(int i=1; i<=N; i++)
268. \{
269. Student s(i,"cs");//关键字为1-10 
270. insertBST(root,s);
271. \}
272. cout<<"after insert: "<<endl;
273. printTree(root);
274. cout<<endl<<endl;
275. 
276. for(int i=1;i<=N;i+=2)
277. \{
278. removeBST\_recursion(root,i);//删除关键字为1-3-5-7-9的结点 
279. \}
280. cout<<"after delete: "<<endl;
281. printTree(root);
282. cout<<endl<<endl;
283. 
284. system("PAUSE");
285. return EXIT\_SUCCESS;
286. \}

#include <cstdlib>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    class Student
    {
    	public:
    		int key;
    		string major;
    		//other data
    		Student(int k=int(),string s="") : key(k), major(s){}
    		//重载赋值运算符 
    		void operator=(const Student& rhs)
    	    {
    			if(this != &rhs)
    			{
    				key = rhs.key;
    				major = rhs.major;
    			}
    		}	
    };
    //重载<<,便于输出自定义类对象 
    ostream& operator<<(ostream &out, const Student& s)
    {
    	out<<"("<<s.key<<","<<s.major<<")";
    }
    
    typedef Student ElementType;
    typedef int KeyType;
    
    typedef struct BSTNode
    {
    	ElementType data;
        struct BSTNode* lchild;
        struct BSTNode* rchild;
    }BSTNode, *BST;
    
    	
    /*
      description:在以t为根结点的二叉查找树中，查找关键字为key的结点
      若查找成功，指针p指向该结点，返回true,
      否则指向查找路径上的最后一个结点并返回false
      指针f指向根结点t的父节点 
    */
    //bool searchBST_recursion(BST t, KeyType key, BSTNode* f, BSTNode*& p)
    //{
    //	if(t == NULL)//查找失败 
    //	{
    //		p = f;
    //		return false;
    //	}
    //	else if(key == t->data.key)//查找成功 
    //	{
    //		p = t;
    //		return true;
    //	}
    //	else if(key < t->data.key)
    //		return searchBST_recursion(t->lchild,key,t,p);//左子树中继续查找 
    //	else 
    //		return searchBST_recursion(t->rchild,key,t,p);//右子树中继续查找 
    //}
    
    //非递归查找 
    bool searchBST(BST t, KeyType key, BSTNode* f, BSTNode* &p)
    {
    	while(t && key != t->data.key)
    	{
    		f = t;
    		if(key < t->data.key)
    		{
    			t = t->lchild;
    		}
    		else
    		{
    			t = t->rchild;
    		}			
    	}
    	if(t)//查找成功 
    	{
    		p = t;
    		return true;
    	}
    	else
    	{
    		p = f;
    		return false;
    	}
    }
    
    //插入给定元素 
    void insertBST(BST& t,ElementType elem)
    {
    	BSTNode * p = NULL;
    
    	if(!searchBST(t, elem.key, NULL, p))//查找失败，不含该关键字，可以插入 
    	{
    		BSTNode * s = new BSTNode;
    		s->data = elem;//可能需要重载= 
    		s->lchild = NULL;
    		s->rchild = NULL;
    		
    		if(p == NULL)//查找树为空 
    		{
    			t = s;//置s为根结点 
    		}
    		else if(elem.key < p->data.key)
    		{
    			p->lchild = s;	//*s为p左结点 
    		}
    		else
    		{
    			p->rchild = s;	//*s为p右结点 
    		}
    	}
    }
    
    //从二叉查找树中删除指针p所指向的结点 ,p非空,删除前驱方式 
    void removeNode1(BSTNode *& p)
    {
    	BSTNode *q = NULL;
    	if(!p->rchild)//*p的右子树为空 
    	{
    		q = p;
    		p = p->lchild;
    		delete q;
    	}
    	else if(!p->lchild)//*p的左子树为空 
    	{
    		q = p;
    		p = p->rchild;
    		delete q;
    	}
    	else//左右子树均不空 
    	{
    		BSTNode *s = NULL;
    		q = p;
    		s = p->lchild;		//左子树根结点
    		while(s->rchild)	//寻找结点*p的中序前驱结点，					
    		{					//也就是以p->lchild为根结点的子树中最右的结点 
    			q = s;			//*s指向*p的中序前驱 
    			s = s->rchild;	//*q指向*s的父节点 
    		}
    		p->data = s->data;	//*s结点中的数据转移到*p结点，然后删除*s
    		if(q != p)			//p->lchild右子树非空 
    		{
    			q->rchild = s->lchild;//把*s的左子树接到*q的右子树上 
    		}
    		else				//p->lchild右子树为空 ,此时q ==p 
    		{
    			q->lchild = s->lchild;//把*s的左子树接到*q的左子树上 
    		}
    		delete s;			//删除结点*s 
    	}
    }
    
    //从二叉查找树中删除指针p所指向的结点 ,p非空,删除后继方式 
    void removeNode2(BSTNode *& p)
    {
    	BSTNode *q = NULL;
    	if(!p->rchild)//*p的右子树为空 
    	{
    		q = p;
    		p = p->lchild;
    		delete q;
    	}
    	else if(!p->lchild)//*p的左子树为空 
    	{
    		q = p;
    		p = p->rchild;
    		delete q;
    	}
    	else//左右子树均不空 
    	{
    		BSTNode *s = NULL;
    		q = p;
    		s = p->rchild;		//右子树根结点
    		while(s->lchild)	//寻找结点*p的中序后继结点，					
    		{					//也就是以p->rchild为根结点的子树中最左的结点 
    			q = s;			//*s指向*p的中序后继 
    			s = s->lchild;	//*q指向*s的父节点 
    		}
    		p->data = s->data;	//*s结点中的数据转移到*p结点，然后删除*s
    		if(q != p)			//p->rchild左子树非空 
    		{
    			q->lchild = s->rchild;//把*s的右子树接到*q的左子树上 
    		}
    		else				//p->rchild左子树为空 ,此时q ==p 
    		{
    			q->rchild = s->rchild;//把*s的右子树接到*q的右子树上 
    		}
    		delete s;			//删除结点*s 
    	}
    }
    
    //从二叉查找树中删除指针p所指向的结点 ,p非空,直接删除p的方式 
    void removeNode3(BSTNode *& p)
    {
    	BSTNode *q = NULL;
    	if(!p->rchild)//*p的右子树为空 
    	{
    		q = p;
    		p = p->lchild;
    		delete q;
    	}
    	else if(!p->lchild)//*p的左子树为空 
    	{
    		q = p;
    		p = p->rchild;
    		delete q;
    	}
    	else//左右子树均不空 
    	{
    		BSTNode *s = NULL;
    		q = p;
    		s = p->lchild;		//左子树根结点
    		while(s->rchild)	//寻找结点*p的中序前驱结点，					
    		{					//也就是以*s为根结点的子树中最右的结点 
    			s = s->rchild;	 
    		}
    		s->rchild = p->rchild;//*p的右子树接到*s的右子树上 
    		p = p->lchild;			//*p的左子树接到父节点上 
    		delete q;			//删除结点*q 
    	}
    }
    
    //删除关键字为key的元素结点 -递归 
    void removeBST_recursion(BST& t, KeyType key)
    {
    	if(t)
    	{
    		if(key < t->data.key)
    		{
    			removeBST_recursion(t->lchild,key);
    		}
    		else if(t->data.key < key)
    		{
    		 	removeBST_recursion(t->rchild,key);
    		}
    		else//找到关键字为key的元素 
    		{
    //			removeNode1(t);//删除结点*t 
    //			removeNode2(t);
    			removeNode3(t);
    		}
        }
    }
    
    
    //输出二叉查找树，中序递归 
    void printTree(const BST & t)
    {
    	if(t)
    	{
    		printTree(t->lchild);
    		cout<<t->data<<" ";
    		printTree(t->rchild);
    	}
    }
    
    int main(int argc, char *argv[])
    {
    	const int N = 10;
    	BST root = NULL;
    	
    	for(int i=1; i<=N; i++)
    	{
    		Student s(i,"cs");//关键字为1-10 
    		insertBST(root,s);
    	}
    	cout<<"after insert: "<<endl;
    	printTree(root);
    	cout<<endl<<endl;
    	
    	for(int i=1;i<=N;i+=2)
    	{
    		removeBST_recursion(root,i);//删除关键字为1-3-5-7-9的结点 
    	}
    	cout<<"after delete: "<<endl;
    	printTree(root);
    	cout<<endl<<endl;
    	
        system("PAUSE");
        return EXIT_SUCCESS;
    }

**5、二叉查找树类的完整C++实现请看**：[http://blog.csdn.net/sysu\_arui/article/details/7892593][http_blog.csdn.net_sysu_arui_article_details_7892593]

**参考资料：**

\[1\]严蔚敏《数据结构(C语言版)》

\[2\]算法导论（第2版）

[http_blog.csdn.net_sysu_arui_article_details_7892593]: http://blog.csdn.net/sysu_arui/article/details/7892593