二叉搜索树BST_c++二叉树求最大下标

1. 基础概念

• 度: 节点的子节点数目

• 叶子(终端节点): 没有孩子的节点

• 根(非终端节点): 存在孩子的节点

• 祖先: 当前节点之前的所有节点

• 子孙: 当前节点派生的所有节点

• 有序树: 节点顺序不能随便换的树

• 无序树: 节点顺序可以随便换无影响的树

• 节点深度: 节点所在树的层
  

• 树的深度: 一棵树中最大的层数

• 森林: 森林是m(m≥0)棵互不相交树的集合, 任何一棵树，删除根结点就成森林。

• 二叉树: 所有节点的度<=2且该树为有序树

• 满二叉树: 所有父节点都有2个子节点
  

• 完全二叉树: 二叉树深度为h, 除了第h层外, 其它各层(1~h-1)的节点数都到达最大个数, 第h层所有节点都集中在最左边, 这就是完全二叉树。
  

2. 二叉树的遍历

前序遍历: 根左右

中序遍历: 左根右

后序遍历: 左右根

3. 完全二叉树的性质

a. 在完全二叉树的第i层上最多有2^i-1个节点(i>=1)

b. 深度为k的完全二叉树最多有2^k-1个节点(k>=1)
c. 如果终端节点数为n, 度为2的节点数为m, 则n=m+1

d. 深度为k且具有n个节点的二叉树的深度为[log₂n]+1 (2^k-1-1<n<2^k-1)
e. n个节点的完全二叉树(深度: [log₂n]+1)的节点按层序排列, 对任一节点i(1<=i<=n)有:

1. i=1则节点i是二叉树的根, 无双亲。如果i>1则其双亲是节点的[i/2]
2. 2i>n则节点i无左孩子(节点i为叶子节点), 否则其做孩子是节点2i
3. 2i+1>n则节点i无右孩子, 否则右孩子是节点2i+1

4. 数组二叉树的例子

一般情况下二叉树都是链表形式, 这里给出数组二叉树的例子。

// 二叉树
// 规律: 父节点下标 * 2 + 1 = 左孩子下标
//     父节点下标 * 2 + 2 = 右孩子下标

class Tree
{
public:
	Tree();
	~Tree();
	bool BuildTree(size_t iNodeNums);
	bool InsertNode(int iVal);
	bool DeleteNode(int iDelVal);
	int FindNode(int iVal);

	void PreOrdereTraverse(int iIdx = 0);
	void InOrderTraverse(int iIdx = 0);
	void PostOrderTraverse(int iIdx = 0);
	int GetNum(int iIdx) const { if (!m_pTree) return(-1); return(m_pTree[iIdx]); }
private:
	int *m_pTree;
	int m_iSize;
	int m_iCapacity;
};

Tree::Tree() : 
	m_pTree(nullptr), m_iSize(0), m_iCapacity(0)
{
	srand((unsigned)time(NULL));
}

Tree::~Tree()
{
	if (m_pTree)
	{
		delete m_pTree;
		m_pTree = nullptr;
	}
	m_iSize = m_iCapacity = 0;
}

bool Tree::BuildTree(size_t iNodeNums)
{
	int *piNodes = nullptr;

	piNodes = new int[iNodeNums];
	if (!piNodes)
	{
		return(false);
	}
	// 如果存在则清除原来的堆空间
	if (m_pTree)
	{
		delete[] m_pTree;
		m_pTree = nullptr;
	}
	m_pTree = piNodes;
	for (size_t nIdx = 0; nIdx < iNodeNums; ++nIdx)
	{
		m_pTree[nIdx] = rand() % 100 + 1;
	}
	m_iSize = m_iCapacity = iNodeNums;

	return(true);
}

bool Tree::InsertNode(int iVal)
{
	int *piBuf = nullptr;

	// 如果容量满了, 则重新分配空间
	if (m_iCapacity <= m_iSize)
	{
		m_iCapacity = m_iCapacity + (m_iCapacity / 2);
		piBuf = new int[m_iCapacity]{0};
		if (!piBuf)
		{
			return(false);
		}
		memcpy(piBuf, m_pTree, m_iSize * sizeof(int));
		if (m_pTree)
		{
			delete[] m_pTree;
			m_pTree = nullptr;
		}
		m_pTree = piBuf;
	}
	m_pTree[m_iSize++] = iVal;

	return(true);
}

bool Tree::DeleteNode(int iDelVal)
{
	int iIndex = 0;

	if (!m_pTree || !m_iSize || !m_iCapacity)
	{
		return(false);
	}
	// 找到对应要删除节点的索引
	iIndex = FindNode(iDelVal);
	if (-1 == iIndex)
	{
		return(false);
	}
	if (iIndex == m_iSize - 1)
	{
		m_pTree[iIndex] = 0;
	}
	else
	{
		memcpy(&m_pTree[iIndex], &m_pTree[iIndex + 1], 
			sizeof(int) * (m_iSize - iIndex - 1));
	}
	--m_iSize;

	return(true);
}

int Tree::FindNode(int iVal)
{
	if (!m_pTree || !m_iSize || !m_iCapacity)
	{
		return(-1);
	}
	for (size_t nIdx = 0; nIdx < m_iSize; ++nIdx)
	{
		if (m_pTree[nIdx] == iVal)
		{
			return(nIdx);
		}
	}
	return(-1);
}

void Tree::PreOrdereTraverse(int iIdx)
{
	if (iIdx > (m_iSize - 1))
	{
		return;
	}
	cout << m_pTree[iIdx] << " ";
	PreOrdereTraverse(iIdx * 2 + 1);
	PreOrdereTraverse(iIdx * 2 + 2);
}

void Tree::InOrderTraverse(int iIdx /*= 0*/)
{
	stack<int> st;

	while (!st.empty() || iIdx < m_iSize)
	{
		if (iIdx < m_iSize)
		{
			st.push(iIdx);
			iIdx = iIdx * 2 + 1;
		}
		else
		{
			// 把左结点出栈
			iIdx = st.top();
			st.pop();
			cout << m_pTree[iIdx] << " ";
			iIdx = iIdx * 2 + 2;
		}
	}
}

void Tree::PostOrderTraverse(int iIdx /*= 0*/)
{
	if (iIdx > (m_iSize - 1))
	{
		return;
	}
	PostOrderTraverse(iIdx * 2 + 1);
	PostOrderTraverse(iIdx * 2 + 2);
	cout << m_pTree[iIdx] << " ";
}

int main()
{
	Tree t;

	t.BuildTree(10);

	t.DeleteNode(t.GetNum(0));
	t.InsertNode(15);
	t.InsertNode(22);
	t.InOrderTraverse();

	cout << endl;
	t.PreOrdereTraverse();
	cout << endl;
	t.PostOrderTraverse();
	cout << endl;

	system("pause");

	return(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200

5. 二叉搜索树(BST)

定义: 是一颗带值结点的二叉树, 可以为空树或者具有如下特点

1. 如果左子树不为空, 则左子树上的所有节点的值都小于根节点值
2. 如果右子树不为空, 则右子树上的所有节点的值都小于根节点值
3. 它的左右子树也都是二叉搜索树

BST有三种操作, 分别是插入, 查询和删除。
首先来解释一下最难的部分, 删除操作:
删除一个结点可能会有以下几种情况:
4. 被删除结点是子叶结点没有孩子, 这种情况最简单直接删除

5. 被删除结点有左子树或者右子树, 下图是右子树存在的例子, 可以删除该结点后, 将其子树挪上补位。

下图是左子树存在的例子

最后是最复杂的一种情况, 左右子树都存在
由于BST都是结点左孩子比父节点小, 右孩子比父节点大。所以往首先往左孩子挪动一个位置确保该结点比要删除的结点小。
接着要找到最右的那个结点，原因是该结点是比被删结点小, 但是在右子树中是最大的那个值。该结点的值可以替换掉被删除结点

接下来把那个左子树中的最大值(简称该结点为A结点)也就是5赋值给要被删除的结点, 并释放自己, 这里A结点有可能还有左子树(由于其是最右孩子所以不可能有右子树存在),

接下来把A结点删除后，要确认A结点是否有左子树, 如果有就将其挪动到A结点父节点的右边。为何是父节点的右边，原因是父节点的右子树肯定都会比父节点大, 所以不管A结点右子树上结点的值多大都肯定比A结点的父节点大。

这样就完成了删除的操作。有一种情况是被删结点的左孩子没有右结点的时候。这种情况下只要删除左孩子，如果左孩子还有左结点存在就进行补位即可。

接下来把左孩子的左子树补位上来即可

这样也完成了删除操作

最难的删除部分理解后来看看插入结点。插入比较简单直接看代码:

bool InsertBST(PBSTNode *ppRoot, int iData)
{
	PBSTNode pCur = *ppRoot;
	PBSTNode pParent = nullptr;
	
	// 如果说传入结点是空的, 说明是一颗空树, 直接生成一个结点后返回
	if (!pCur)
	{
		*ppRoot = new BSTNode(iData);
		return(true);
	}
	//
	// 由于BST树父节点的值比左孩子值小, 比右孩子值大
	// 根据要插入结点的值的大小决定往左边还有右边走
	// 走到最底也就是空的时候将其插入
	// 注意BST树不能有重复结点, 所以如果结点值一样
	// 直接返回false代表失败。
	while (pCur)
	{
		pParent = pCur;

		if (pCur->iData > iData)
		{
			pCur = pCur->leftChild;
		}
		else if (pCur->iData < iData)
		{
			pCur = pCur->rightChild;
		}
		else
		{
			return(false);
		}
	}
	// 由于遍历到的当前结点是nullptr值
	// 所以要利用其父节点插入
	// 要重新判断其值大小以切丁插入左边还是右边
	PBSTNode pNewNode = new BSTNode(iData);
	if (pNewNode->iData > pParent->iData)
	{
		pParent->rightChild = pNewNode;
	}
	else
	{
		pParent->leftChild = pNewNode;
	}

	return(true);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

查找的代码比插入更简单，这里就不在解释了。

下面是迭代方式进行的代码:

#include <iostream>

using namespace std;

typedef struct BSTNode
{
	BSTNode() : iData(0), leftChild(nullptr), rightChild(nullptr) {}
	BSTNode(int iNum) : iData(iNum), leftChild(nullptr), rightChild(nullptr) {}

	int iData;
	BSTNode *leftChild;
	BSTNode *rightChild;
} BSTNode, *PBSTNode;

void InOrderTraverse(PBSTNode pNode)
{
	if (!pNode)
	{
		return;
	}
	InOrderTraverse(pNode->leftChild);
	cout << pNode->iData << " ";
	InOrderTraverse(pNode->rightChild);
}

PBSTNode SearchBST(PBSTNode pNode, int iData)
{
	PBSTNode pCur = pNode;

	while (pCur)
	{
		if (pCur->iData > iData)
		{
			pCur = pCur->leftChild;
		}
		else if (pCur->iData < iData)
		{
			pCur = pCur->rightChild;
		}
		else
		{
			return(pCur);
		}
	}

	return(nullptr);
}

PBSTNode InsertBSTRec(PBSTNode *ppRoot, int iData)
{
	PBSTNode pRoot = *ppRoot;

	if (!pRoot)
	{
		return(new BSTNode(iData));
	}
	else if (iData < pRoot->iData)
	{
		pRoot->leftChild = InsertBSTRec(&pRoot->leftChild, iData);
	}
	else if (iData > pRoot->iData)
	{
		pRoot->rightChild = InsertBSTRec(&pRoot->rightChild, iData);
	}

	return(pRoot);
}

bool InsertBST(PBSTNode *ppRoot, int iData)
{
	PBSTNode pCur = *ppRoot;
	PBSTNode pParent = nullptr;

	if (!pCur)
	{
		*ppRoot = new BSTNode(iData);
		return(true);
	}

	while (pCur)
	{
		pParent = pCur;

		if (pCur->iData > iData)
		{
			pCur = pCur->leftChild;
		}
		else if (pCur->iData < iData)
		{
			pCur = pCur->rightChild;
		}
		else
		{
			return(false);
		}
	}
	PBSTNode pNewNode = new BSTNode(iData);
	if (pNewNode->iData > pParent->iData)
	{
		pParent->rightChild = pNewNode;
	}
	else
	{
		pParent->leftChild = pNewNode;
	}

	return(true);
}

bool erase(PBSTNode *ppRoot, int iKey)
{
	PBSTNode pParent = nullptr;
	PBSTNode pCur = *ppRoot;

	while (pCur)
	{
		if (pCur->iData < iKey)
		{
			pParent = pCur;
			pCur = pCur->rightChild;
		}
		else if (pCur->iData > iKey)
		{
			pParent = pCur;
			pCur = pCur->leftChild;
		}
		else
		{
			// 被删除的结点是子叶结点
			if (!pCur->leftChild && !pCur->rightChild)
			{
				if (pParent->leftChild == pCur)
				{
					pParent->leftChild = nullptr;
				}
				else
				{
					pParent->rightChild = nullptr;
				}
			}
			// 被删除的结点只存在右子树
			else if (!pCur->leftChild)
			{
				if (pCur == *ppRoot)
				{
					*ppRoot = pCur->rightChild;
				}
				else
				{
					if (pCur == pParent->leftChild)
					{
						pParent->leftChild = pCur->rightChild;
					}
					else
					{
						pParent->rightChild = pCur->rightChild;
					}
				}
			}
			// 被删除的结点只存在左子树
			else if (!pCur->rightChild)
			{
				if (pCur == *ppRoot)
				{
					*ppRoot = pCur->leftChild;
				}
				else
				{
					if (pParent->leftChild == pCur)
					{
						pParent->leftChild = pCur->leftChild;
					}
					else
					{
						pParent->rightChild = pCur->leftChild;
					}
				}
			}
			else
			{
				// 被删除节点的左孩子
				PBSTNode pCurLeft = pCur->leftChild;
				PBSTNode pCurLeftMostRightParent = nullptr;
				// 被删除节点的左孩子的最右边的子树
				while (pCurLeft->rightChild)
				{
					pCurLeftMostRightParent = pCurLeft;
					pCurLeft = pCurLeft->rightChild;
				}
				PBSTNode pCurLeftMostRright = pCurLeft;
				pCur->iData = pCurLeft->iData;

				if (!pCurLeftMostRightParent)
				{
					// 说明要删除节点的左孩子不存在右子树
					// 把左孩子的左子树接上来
					pCur->leftChild = pCurLeft->leftChild;
					delete[] pCurLeft;
					pCurLeft = nullptr;
					return(true);
				}
				else
				{
					// 说明要删除节点的左孩子的右子树至少有一个结点
					// 要删除结点的左孩子的最右子结点存在左子树
					if (pCurLeftMostRright->leftChild)
					{
						// 把要删除结点的左孩子的最右子结点的值赋给要删除的元素
						// 删除要被删除结点的左孩子的最右子结点(这里相当于删除了要删除结点)
						// 把删除结点的左孩子的最右子结点的左子树给当前最右子节点
						PBSTNode pTmp = pCurLeftMostRright->leftChild;
						delete pCurLeftMostRright;
						pCurLeftMostRright = nullptr;
						pCurLeftMostRightParent->rightChild = pTmp;
					}
					else
					{
						delete pCurLeftMostRright;
						pCurLeftMostRright = nullptr;
					}
					return(true);
				}
			}
			delete pCur;
			pCur = nullptr;

			return(true);
		}
	}

	return(false);
}

int main()
{
	PBSTNode pRoot = nullptr;
	int iArr[] = {15, 7, 30, 1, 10, 23, 37, 0, 2, 9, 11, 3, 5, 4};
	for (int i = 0; i < sizeof(iArr) / sizeof(iArr[0]); ++i)
	{
		InsertBST(&pRoot, iArr[i]);
	}
	
	InOrderTraverse(pRoot);
	erase(&pRoot, 7);
	cout << endl;
	InOrderTraverse(pRoot);

	system("pause");

	return(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251

下面是递归方式进行的代码:

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <unordered_map>
#include <stack>
#include <map>
#include <unordered_map>
#include <functional>
#include <algorithm>

using namespace std;

typedef struct BSTNode
{
	BSTNode() : iData(0), leftChild(nullptr), rightChild(nullptr) {}
	BSTNode(int iNum) : iData(iNum), leftChild(nullptr), rightChild(nullptr) {}

	int iData;
	BSTNode *leftChild;
	BSTNode *rightChild;
} BSTNode, *PBSTNode;

bool BSTInsert(PBSTNode *pNode, int elem)
{	
	PBSTNode p = *pNode;

	if (!pNode)
	{
		return(false);
	}
	
	if (!p)
	{
		p = new BSTNode(elem);
		*pNode = p;
		return(true);
	}
	if (elem == p->iData)
	{
		return(false);
	}
	if (elem < p->iData)
	{
		return(BSTInsert(&p->leftChild, elem));
	}

	return(BSTInsert(&p->rightChild, elem));
}

void CreateBST(PBSTNode *pNode, int *iArr, int iSize)
{
	if (!pNode || *pNode)
	{
		return;
	}
	for (int i = 0; i < iSize; ++i)
	{
		BSTInsert(pNode, iArr[i]);
	}
}

PBSTNode BSTSearch(PBSTNode pNode, int iKey)
{
	if (!pNode)
	{
		return(NULL);
	}
	if (iKey == pNode->iData)
	{
		return(pNode);
	}
	if (iKey < pNode->iData)
	{
		return(BSTSearch(pNode->leftChild, iKey));
	}
	return(BSTSearch(pNode->rightChild, iKey));
}

bool Delete(PBSTNode *pTree)
{
	PBSTNode q, s;

	// 清空节点右子树
	if (!((*pTree)->rightChild))
	{
		q = *pTree;
		*pTree = (*pTree)->rightChild;
		delete q;
		q = nullptr;
	}
	else if (!((*pTree)->leftChild))
	{
		q = *pTree;
		*pTree = (*pTree)->leftChild;
		delete q;
		q = nullptr;
	}
	else
	{
		q = *pTree;
		s = (*pTree)->leftChild;
		while (s->rightChild)
		{
			q = s;
			s = s->rightChild;
		}
		(*pTree)->iData = s->iData;
		if (q != *pTree)
		{
			q->rightChild = s->leftChild;
		}
		else
		{
			q->leftChild = s->leftChild;
		}
		delete s;
		s = nullptr;
	}
	
	return(true);
}

bool DeleteBST(PBSTNode *pTree, int iKey)
{
	if (!pTree || !*pTree)
	{
		return(false);
	}
	else
	{
		if (iKey == (*pTree)->iData)
		{
			return(Delete(pTree));
		}
		else if (iKey < (*pTree)->iData)
		{
			return(DeleteBST(&(*pTree)->leftChild, iKey));
		}
		else
		{
			return(DeleteBST(&(*pTree)->rightChild, iKey));
		}
	}
}

void InOrderTraverse(PBSTNode pNode)
{
	if (!pNode)
	{
		return;
	}
	InOrderTraverse(pNode->leftChild);
	cout << pNode->iData << " ";
	InOrderTraverse(pNode->rightChild);
}

int main()
{
	PBSTNode pRoot = nullptr;
	int iArr[] = {15, 7, 30, 1, 10, 23, 37, 0, 2, 9, 11, 3, 5, 4};

	CreateBST(&pRoot, iArr, sizeof(iArr) / sizeof(iArr[0]));
	InOrderTraverse(pRoot);
	PBSTNode pNode = BSTSearch(pRoot, 37);
	cout << endl;
	cout << pNode->iData << endl;
	DeleteBST(&pRoot, 7);
	InOrderTraverse(pRoot);

	system("pause");

	return(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

下面用一个类封装了实现:

#include <iostream>

using namespace std;

struct Node
{
	Node(int val) { m_val = val; }
	int m_val;
	Node *m_pParent = nullptr;
	Node *m_pLeft = nullptr;
	Node *m_pRight = nullptr;
};

class CBinarySearchTree
{
public:
	CBinarySearchTree() : m_pRoot(nullptr) { }
	CBinarySearchTree(int val) : m_pRoot(new Node(val)) { }

	bool               Insert(int val);
	bool               Delete(int val);
	bool               Update(int oldval, int newval);
	Node			  *Find(int val);

	bool IsEmpty();

	void Clear();
	void ClearImpl(Node *pNode);

	void PreOrderTraverse() const;

private:
	bool NodeDelete(Node *pCurNode);
	void PreOrderTraverse(const Node *pNode) const;
private:
	Node *m_pRoot = nullptr;
};

bool CBinarySearchTree::Insert(int val)
{
	if (IsEmpty())
	{
		m_pRoot = new Node(val);
		return(true);
	}
	Node *pNode = m_pRoot;
	Node *pNewNode = nullptr;

	while (pNode)
	{
		if (val < pNode->m_val)
		{
			if (!pNode->m_pLeft)
			{
				pNewNode = new Node(val);
				pNode->m_pLeft = pNewNode;
				pNewNode->m_pParent = pNode;

				break;
			}
			pNode = pNode->m_pLeft;
		}
		else if (val > pNode->m_val)
		{
			if (!pNode->m_pRight)
			{
				pNewNode = new Node(val);
				pNode->m_pRight = pNewNode;
				pNewNode->m_pParent = pNode;

				break;
			}
			pNode = pNode->m_pRight;
		}
		else
		{
			break;
		}
	}

	return(true);
}


bool CBinarySearchTree::Update(int oldval, int newval)
{
	Node *pCurNode = nullptr;

	if (IsEmpty())
	{
		return(false);
	}
	Delete(oldval);
	Insert(newval);

	return(true);
}

Node *CBinarySearchTree::Find(int val)
{
	Node *pCurNode = nullptr;

	if (IsEmpty())
	{
		return(nullptr);
	}
	pCurNode = m_pRoot;
	while (pCurNode)
	{
		if (pCurNode->m_val > val)
		{
			pCurNode = pCurNode->m_pLeft;
		}
		else if (pCurNode->m_val < val)
		{
			pCurNode = pCurNode->m_pRight;
		}
		else
		{
			return(pCurNode);
		}
	}

	return(nullptr);
}

bool CBinarySearchTree::IsEmpty()
{
	return(!m_pRoot);
}


void CBinarySearchTree::ClearImpl(Node *pNode)
{
	if (!pNode)
	{
		return;
	}
	ClearImpl(pNode->m_pLeft);
	ClearImpl(pNode->m_pRight);
	NodeDelete(pNode);
}

void CBinarySearchTree::Clear()
{
	Node *pCurNode = m_pRoot;

	ClearImpl(pCurNode);
	
	return;
}


void CBinarySearchTree::PreOrderTraverse() const
{
	PreOrderTraverse(m_pRoot);
	cout << endl;
}

void CBinarySearchTree::PreOrderTraverse(const Node *pNode) const
{
	if (!pNode)
	{
		return;
	}
	cout << pNode->m_val << " ";
	PreOrderTraverse(pNode->m_pLeft);
	PreOrderTraverse(pNode->m_pRight);
}


bool CBinarySearchTree::Delete(int val)
{
	Node *pNode = Find(val);
	if (!pNode)
	{
		return(false);
	}

	return(NodeDelete(pNode));
}

bool CBinarySearchTree::NodeDelete(Node *pCurNode)
{
	Node *pParentNode = nullptr;
	Node *pNextNode = nullptr;
	Node *pDelNode = nullptr;

	if (IsEmpty())
	{
		return(false);
	}

	if (!pCurNode->m_pRight)
	{
		pParentNode = pCurNode->m_pParent;
		pDelNode = pCurNode;
		if (pParentNode)
		{
			if (pParentNode->m_pLeft == pCurNode)
			{
				pParentNode->m_pLeft = pCurNode->m_pLeft;
			}
			else
			{
				pParentNode->m_pRight = pCurNode->m_pLeft;
			}
		}
		delete pDelNode;
		pDelNode = nullptr;
	}
	else if (!pCurNode->m_pLeft)
	{
		pParentNode = pCurNode->m_pParent;
		pDelNode = pCurNode;
		if (pParentNode)
		{
			if (pParentNode->m_pLeft == pCurNode)
			{
				pParentNode->m_pLeft = pCurNode->m_pRight;
			}
			else
			{
				pParentNode->m_pRight = pCurNode->m_pRight;
			}
		}
		delete pDelNode;
		pDelNode = nullptr;
	}
	else
	{
		pParentNode = pCurNode;
		pNextNode = pCurNode->m_pLeft;
		while (pNextNode->m_pRight)
		{
			pParentNode = pNextNode;
			pNextNode = pNextNode->m_pRight;
		}
		pCurNode->m_val = pNextNode->m_val;
		if (pParentNode != pCurNode)
		{
			pParentNode->m_pRight = pNextNode->m_pLeft;
		}
		else
		{
			pParentNode->m_pLeft = pNextNode->m_pLeft;
		}
		delete pNextNode;
		pNextNode = nullptr;
	}

	return(true);
}

int main()
{
	int iArr[] = { 50, 25, 75, 13, 42, 60, 88, 5, 18, 35, 48, 55, 80, 90 };
	CBinarySearchTree bin;

	for (int i = 0; i < sizeof(iArr) / sizeof(iArr[0]); ++i)
	{
		bin.Insert(iArr[i]);
	}
	bin.PreOrderTraverse();
	bin.Update(60, 199);
	bin.PreOrderTraverse();
	bin.Update(5, 299);
	bin.PreOrderTraverse();
	bin.Clear();

	system("pause");

	return(0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274

(完)