11장 탐색(Search) 1 – 이진탐색트리(Binary Search Tree)

Posted on: 2019년 04월 07일 2019년 04월 07일
Categories: 강의자료, 자료구조

순차 탐색(Linear Search)
이진 탐색(Binary Search)
1. 이진 탐색의 변형으로 보간 탐색을 들 수 있음

보간 탐색(Interpolation Search) : S011_InterpolSearch.c

#include <stdio.h>

int ISearch(int ar[], int first, int last, int target){
	int mid;

//	if(first > last)
//		return -1;    // -1의 반환은 탐색의 실패를 의미
	if(ar[first] > target || ar[last] < target)
		return -1;

	// 이진 탐색과의 차이점을 반영한 문장
	mid = ((double)(target-ar[first]) / (ar[last]-ar[first]) *
			(last-first)) + first;

	if(ar[mid] == target)
		return mid;    // 탐색된 타겟의 인덱스 값 반환
	else if(target < ar[mid])
		return ISearch(ar, first, mid-1, target);
	else
		return ISearch(ar, mid+1, last, target);
}

int main(void){
	int arr[] = {1, 3, 5, 7, 9};
	int idx;

	idx = ISearch(arr, 0, sizeof(arr)/sizeof(int)-1, 7);  // 7 -> 2로 변경
	if(idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

#include <stdio.h>

int ISearch(int ar[], int first, int last, int target){

int mid;

// if(first > last)

// return -1; // -1의 반환은 탐색의 실패를 의미

if(ar[first] > target || ar[last] < target)

return -1;

// 이진 탐색과의 차이점을 반영한 문장

mid = ((double)(target-ar[first]) / (ar[last]-ar[first]) *

(last-first)) + first;

if(ar[mid] == target)

return mid; // 탐색된 타겟의 인덱스 값 반환

else if(target < ar[mid])

return ISearch(ar, first, mid-1, target);

else

return ISearch(ar, mid+1, last, target);

}

int main(void){

int arr[] = {1, 3, 5, 7, 9};

int idx;

idx = ISearch(arr, 0, sizeof(arr)/sizeof(int)-1, 7); // 7 -> 2로 변경

if(idx == -1)

printf("탐색 실패 \n");

else

printf("타겟 저장 인덱스: %d \n", idx);

return 0;

}

이진 탐색 트리(Binary Search Tree)
1. 특징
  1. 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다
  2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다
  3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다
  4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리다
2. 이진 탐색 트리 연습
  1. 이진 탐색 트리 생성 : 12, 6, 17, 9, 21, 4, 13, 8, 2, 10
  2. 이진 탐색 트리에서 다음 노드를 제거한 결과의 이진탐색 트리
    1. 단말노드 2 제거
    2. 자식이 1인 17제거
    3. 자식이 2인 6제거
      1. 왼쪽 서브 트리중 가장 큰값으로 대체
      2. 오른쪽 서브 트리중 가장 작은 값으로 대체

이진 탐색 트리(Binary Search Tree) : S011_BinarySearchTree.c

#include <stdio.h>
#include <stdlib.h>

typedef struct _bTreeNode{
	int data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

////////////////////////// 이진트리 시작
BTreeNode * MakeBTreeNode(void){
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

	nd->left = NULL;
	nd->right = NULL;
	return nd;
}

int GetData(BTreeNode * bt){
	return bt->data;
}

void SetData(BTreeNode * bt, int data){
	bt->data = data;
}

BTreeNode * GetLeftSubTree(BTreeNode * bt){
	return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt){
	return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub){
	if(main->left != NULL)
		free(main->left);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub){
	if(main->right != NULL)
		free(main->right);

	main->right = sub;
}

void PreorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	printf("%d ", bt->data);
	PreorderTraverse(bt->left);
	PreorderTraverse(bt->right);
}

void InorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	InorderTraverse(bt->left);
	printf("%d ", bt->data);
	InorderTraverse(bt->right);
}

void PostorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	PostorderTraverse(bt->left);
	PostorderTraverse(bt->right);
	printf("%d ", bt->data);
}
////////////////////////// 이진트리 끝

////////////////////////// 이진 탐색 트리 시작
void BSTMakeAndInit(BTreeNode ** pRoot){
	*pRoot = NULL;
}

int BSTGetNodeData(BTreeNode * bst){
	return GetData(bst);
}

void BSTInsert(BTreeNode ** pRoot, int data){
	BTreeNode * pNode = NULL;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * nNode = NULL;    // new node

	// 새로운 노드가 추가될 위치를 찾는다.
	while(cNode != NULL){
		if(data == GetData(cNode))
			return;    // 키의 중복을 허용하지 않음

		pNode = cNode;

		if(GetData(cNode) > data)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	// pNode의 서브 노드에 추가할 새 노드의 생성
	nNode = MakeBTreeNode();    // 새 노드의 생성
	SetData(nNode, data);    // 새 노드에 데이터 저장

	// pNode의 서브 노드에 새 노드를 추가
	if(pNode != NULL){    // 새 노드가 루트 노드가 아니라면,
		if(data < GetData(pNode))
			MakeLeftSubTree(pNode, nNode);
		else
			MakeRightSubTree(pNode, nNode);
	}
	else{    // 새 노드가 루트 노드라면,
		*pRoot = nNode;
	}
}

BTreeNode * BSTSearch(BTreeNode * bst, int target){
	BTreeNode * cNode = bst;    // current node
	int cd;    // current data

	while(cNode != NULL){
		cd = GetData(cNode);

		if(target == cd)
			return cNode;
		else if(target < cd)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	return NULL;
}
////////////////////////// 이진 탐색 트리 끝

///////////////////////// 메인 함수 시작
int main(void){
	BTreeNode * bstRoot;
	BTreeNode * sNode;    // search node

	BSTMakeAndInit(&bstRoot);

	BSTInsert(&bstRoot, 9);
	BSTInsert(&bstRoot, 1);
	BSTInsert(&bstRoot, 6);
	BSTInsert(&bstRoot, 2);
	BSTInsert(&bstRoot, 8);
//	BSTInsert(&bstRoot, 4);
	BSTInsert(&bstRoot, 3);
	BSTInsert(&bstRoot, 5);
//	BSTInsert(&bstRoot, 7);

	sNode = BSTSearch(bstRoot, 1);
	if(sNode == NULL)
		printf("탐색 실패 \n");
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

	sNode = BSTSearch(bstRoot, 4);
	if(sNode == NULL)
		printf("탐색 실패 \n");
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

	sNode = BSTSearch(bstRoot, 6);
	if(sNode == NULL)
		printf("탐색 실패 \n");
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

	sNode = BSTSearch(bstRoot, 7);
	if(sNode == NULL)
		printf("탐색 실패 \n");
	else
		printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

	return 0;
}

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

#include <stdio.h>

#include <stdlib.h>

typedef struct _bTreeNode{

int data;

struct _bTreeNode * left;

struct _bTreeNode * right;

} BTreeNode;

////////////////////////// 이진트리 시작

BTreeNode * MakeBTreeNode(void){

BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

nd->left = NULL;

nd->right = NULL;

return nd;

}

int GetData(BTreeNode * bt){

return bt->data;

}

void SetData(BTreeNode * bt, int data){

bt->data = data;

}

BTreeNode * GetLeftSubTree(BTreeNode * bt){

return bt->left;

}

BTreeNode * GetRightSubTree(BTreeNode * bt){

return bt->right;

}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub){

if(main->left != NULL)

free(main->left);

main->left = sub;

}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub){

if(main->right != NULL)

free(main->right);

main->right = sub;

}

void PreorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

printf("%d ", bt->data);

PreorderTraverse(bt->left);

PreorderTraverse(bt->right);

}

void InorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

InorderTraverse(bt->left);

printf("%d ", bt->data);

InorderTraverse(bt->right);

}

void PostorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

PostorderTraverse(bt->left);

PostorderTraverse(bt->right);

printf("%d ", bt->data);

}

////////////////////////// 이진트리 끝

////////////////////////// 이진 탐색 트리 시작

void BSTMakeAndInit(BTreeNode ** pRoot){

*pRoot = NULL;

}

int BSTGetNodeData(BTreeNode * bst){

return GetData(bst);

}

void BSTInsert(BTreeNode ** pRoot, int data){

BTreeNode * pNode = NULL; // parent node

BTreeNode * cNode = *pRoot; // current node

BTreeNode * nNode = NULL; // new node

// 새로운 노드가 추가될 위치를 찾는다.

while(cNode != NULL){

if(data == GetData(cNode))

return; // 키의 중복을 허용하지 않음

pNode = cNode;

if(GetData(cNode) > data)

cNode = GetLeftSubTree(cNode);

else

cNode = GetRightSubTree(cNode);

}

// pNode의 서브 노드에 추가할 새 노드의 생성

nNode = MakeBTreeNode(); // 새 노드의 생성

SetData(nNode, data); // 새 노드에 데이터 저장

// pNode의 서브 노드에 새 노드를 추가

if(pNode != NULL){ // 새 노드가 루트 노드가 아니라면,

if(data < GetData(pNode))

MakeLeftSubTree(pNode, nNode);

else

MakeRightSubTree(pNode, nNode);

}

else{ // 새 노드가 루트 노드라면,

*pRoot = nNode;

}

BTreeNode * BSTSearch(BTreeNode * bst, int target){

BTreeNode * cNode = bst; // current node

int cd; // current data

while(cNode != NULL){

cd = GetData(cNode);

if(target == cd)

return cNode;

else if(target < cd)

cNode = GetLeftSubTree(cNode);

else

cNode = GetRightSubTree(cNode);

}

return NULL;

}

////////////////////////// 이진 탐색 트리 끝

///////////////////////// 메인 함수 시작

int main(void){

BTreeNode * bstRoot;

BTreeNode * sNode; // search node

BSTMakeAndInit(&bstRoot);

BSTInsert(&bstRoot, 9);

BSTInsert(&bstRoot, 1);

BSTInsert(&bstRoot, 6);

BSTInsert(&bstRoot, 2);

BSTInsert(&bstRoot, 8);

// BSTInsert(&bstRoot, 4);

BSTInsert(&bstRoot, 3);

BSTInsert(&bstRoot, 5);

// BSTInsert(&bstRoot, 7);

sNode = BSTSearch(bstRoot, 1);

if(sNode == NULL)

printf("탐색 실패 \n");

else

printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

sNode = BSTSearch(bstRoot, 4);

if(sNode == NULL)

printf("탐색 실패 \n");

else

printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

sNode = BSTSearch(bstRoot, 6);

if(sNode == NULL)

printf("탐색 실패 \n");

else

printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

sNode = BSTSearch(bstRoot, 7);

if(sNode == NULL)

printf("탐색 실패 \n");

else

printf("탐색에 성공한 키의 값: %d \n", BSTGetNodeData(sNode));

return 0;

}

이진 탐색 트리(삭제 추가) : S011_BinarySearchTreeRemoveAdd.c

#include <stdio.h>
#include <stdlib.h>

typedef struct _bTreeNode{
	int data;
	struct _bTreeNode * left;
	struct _bTreeNode * right;
} BTreeNode;

////////////////////////// 이진트리 시작
BTreeNode * MakeBTreeNode(void){
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

	nd->left = NULL;
	nd->right = NULL;
	return nd;
}

int GetData(BTreeNode * bt){
	return bt->data;
}

void SetData(BTreeNode * bt, int data){
	bt->data = data;
}

BTreeNode * GetLeftSubTree(BTreeNode * bt){
	return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt){
	return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub){
	if(main->left != NULL)
		free(main->left);

	main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub){
	if(main->right != NULL)
		free(main->right);

	main->right = sub;
}

void PreorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	printf("%d ", bt->data);
	PreorderTraverse(bt->left);
	PreorderTraverse(bt->right);
}

void InorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	InorderTraverse(bt->left);
	printf("%d ", bt->data);
	InorderTraverse(bt->right);
}

void PostorderTraverse(BTreeNode * bt){
	if(bt == NULL)
		return;

	PostorderTraverse(bt->left);
	PostorderTraverse(bt->right);
	printf("%d ", bt->data);
}


BTreeNode * RemoveLeftSubTree(BTreeNode * bt)
{
	BTreeNode * delNode;

	if(bt != NULL) {
		delNode = bt->left;
		bt->left = NULL;
	}
	return delNode;
}

BTreeNode * RemoveRightSubTree(BTreeNode * bt)
{
	BTreeNode * delNode;

	if(bt != NULL) {
		delNode = bt->right;
		bt->right = NULL;
	}
	return delNode;
}

void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
	main->left = sub;
}

void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	main->right = sub;
}
////////////////////////// 이진트리 끝

////////////////////////// 이진 탐색 트리 시작
void BSTMakeAndInit(BTreeNode ** pRoot){
	*pRoot = NULL;
}

int BSTGetNodeData(BTreeNode * bst){
	return GetData(bst);
}

void BSTInsert(BTreeNode ** pRoot, int data){
	BTreeNode * pNode = NULL;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * nNode = NULL;    // new node

	// 새로운 노드가 추가될 위치를 찾는다.
	while(cNode != NULL){
		if(data == GetData(cNode))
			return;    // 키의 중복을 허용하지 않음

		pNode = cNode;

		if(GetData(cNode) > data)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	// pNode의 서브 노드에 추가할 새 노드의 생성
	nNode = MakeBTreeNode();    // 새 노드의 생성
	SetData(nNode, data);    // 새 노드에 데이터 저장

	// pNode의 서브 노드에 새 노드를 추가
	if(pNode != NULL){    // 새 노드가 루트 노드가 아니라면,
		if(data < GetData(pNode))
			MakeLeftSubTree(pNode, nNode);
		else
			MakeRightSubTree(pNode, nNode);
	}
	else{    // 새 노드가 루트 노드라면,
		*pRoot = nNode;
	}
}

BTreeNode * BSTSearch(BTreeNode * bst, int target){
	BTreeNode * cNode = bst;    // current node
	int cd;    // current data

	while(cNode != NULL){
		cd = GetData(cNode);

		if(target == cd)
			return cNode;
		else if(target < cd)
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	return NULL;
}

BTreeNode * BSTRemove(BTreeNode ** pRoot, int target){
	// 삭제 대상이 루트 노드인 경우를 별도로 고려해야 한다.

	BTreeNode * pVRoot = MakeBTreeNode();    // 가상 루트 노드;

	BTreeNode * pNode = pVRoot;    // parent node
	BTreeNode * cNode = *pRoot;    // current node
	BTreeNode * dNode;    // delete node

	// 루트 노드를 pVRoot가 가리키는 노드의 오른쪽 서브 노드가 되게 한다.
	ChangeRightSubTree(pVRoot, *pRoot);

	// 삭제 대상을 저장한 노드 탐색
	while(cNode != NULL && GetData(cNode) != target){
		pNode = cNode;

		if(target < GetData(cNode))
			cNode = GetLeftSubTree(cNode);
		else
			cNode = GetRightSubTree(cNode);
	}

	if(cNode == NULL)    // 삭제 대상이 존재하지 않는다면,
		return NULL;

	dNode = cNode;    // 삭제 대상을 dNode가 가리키게 한다.

	// 첫 번째 경우: 삭제할 노드가 단말 노드인 경우
	if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL){
		if(GetLeftSubTree(pNode) == dNode)
			RemoveLeftSubTree(pNode);
		else
			RemoveRightSubTree(pNode);
	}

	// 두 번째 경우: 하나의 자식 노드를 갖는 경우
	else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL){
		BTreeNode * dcNode;    // delete node의 자식 노드

		if(GetLeftSubTree(dNode) != NULL)
			dcNode = GetLeftSubTree(dNode);
		else
			dcNode = GetRightSubTree(dNode);

		if(GetLeftSubTree(pNode) == dNode)
			ChangeLeftSubTree(pNode, dcNode);
		else
			ChangeRightSubTree(pNode, dcNode);
	}

	// 세 번째 경우: 두 개의 자식 노드를 모두 갖는 경우
	else{
		BTreeNode * mNode = GetRightSubTree(dNode);    // mininum node
		BTreeNode * mpNode = dNode;    // mininum node의 부모 노드
		int delData;

		// 삭제할 노드를 대체할 노드를 찾는다.
		while(GetLeftSubTree(mNode) != NULL)
		{
			mpNode = mNode;
			mNode = GetLeftSubTree(mNode);
		}

		// 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
		delData = GetData(dNode);    // 대입 전 데이터 백업
		SetData(dNode, GetData(mNode));

		// 대체할 노드의 부모 노드와 자식 노드를 연결한다.
		if(GetLeftSubTree(mpNode) == mNode)
			ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
		else
			ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

		dNode = mNode;
		SetData(dNode, delData);    // 백업 데이터 복원
	}

	// 삭제된 노드가 루트 노드인 경우에 대한 처리
	if(GetRightSubTree(pVRoot) != *pRoot)
		*pRoot = GetRightSubTree(pVRoot);

	free(pVRoot);
	return dNode;
}

void ShowIntData(int data){
	printf("%d ", data);
}

void BSTShowAll(BTreeNode * bst){
	InorderTraverse(bst);
}
////////////////////////// 이진 탐색 트리 끝

///////////////////////// 메인 함수 시작
int main(void){
	BTreeNode * bstRoot;
	BTreeNode * sNode;    // search node

	BSTMakeAndInit(&bstRoot);

	BSTInsert(&bstRoot, 5);
	BSTInsert(&bstRoot, 8);
	BSTInsert(&bstRoot, 1);
	BSTInsert(&bstRoot, 6);
	BSTInsert(&bstRoot, 4);
	BSTInsert(&bstRoot, 9);
	BSTInsert(&bstRoot, 3);
	BSTInsert(&bstRoot, 2);
	BSTInsert(&bstRoot, 7);

	BSTShowAll(bstRoot); printf("\n");
	sNode = BSTRemove(&bstRoot, 3);
	free(sNode);

	BSTShowAll(bstRoot); printf("\n");
	sNode = BSTRemove(&bstRoot, 8);
	free(sNode);

	BSTShowAll(bstRoot); printf("\n");
	sNode = BSTRemove(&bstRoot, 1);
	free(sNode);

	BSTShowAll(bstRoot); printf("\n");
	sNode = BSTRemove(&bstRoot, 6);
	free(sNode);

	BSTShowAll(bstRoot); printf("\n");
	return 0;
}

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

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

#include <stdio.h>

#include <stdlib.h>

typedef struct _bTreeNode{

int data;

struct _bTreeNode * left;

struct _bTreeNode * right;

} BTreeNode;

////////////////////////// 이진트리 시작

BTreeNode * MakeBTreeNode(void){

BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

nd->left = NULL;

nd->right = NULL;

return nd;

}

int GetData(BTreeNode * bt){

return bt->data;

}

void SetData(BTreeNode * bt, int data){

bt->data = data;

}

BTreeNode * GetLeftSubTree(BTreeNode * bt){

return bt->left;

}

BTreeNode * GetRightSubTree(BTreeNode * bt){

return bt->right;

}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub){

if(main->left != NULL)

free(main->left);

main->left = sub;

}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub){

if(main->right != NULL)

free(main->right);

main->right = sub;

}

void PreorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

printf("%d ", bt->data);

PreorderTraverse(bt->left);

PreorderTraverse(bt->right);

}

void InorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

InorderTraverse(bt->left);

printf("%d ", bt->data);

InorderTraverse(bt->right);

}

void PostorderTraverse(BTreeNode * bt){

if(bt == NULL)

return;

PostorderTraverse(bt->left);

PostorderTraverse(bt->right);

printf("%d ", bt->data);

}

BTreeNode * RemoveLeftSubTree(BTreeNode * bt)

{

BTreeNode * delNode;

if(bt != NULL) {

delNode = bt->left;

bt->left = NULL;

}

return delNode;

}

BTreeNode * RemoveRightSubTree(BTreeNode * bt)

{

BTreeNode * delNode;

if(bt != NULL) {

delNode = bt->right;

bt->right = NULL;

}

return delNode;

}

void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub)

{

main->left = sub;

}

void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub)

{

main->right = sub;

}

////////////////////////// 이진트리 끝

////////////////////////// 이진 탐색 트리 시작

void BSTMakeAndInit(BTreeNode ** pRoot){

*pRoot = NULL;

}

int BSTGetNodeData(BTreeNode * bst){

return GetData(bst);

}

void BSTInsert(BTreeNode ** pRoot, int data){

BTreeNode * pNode = NULL; // parent node

BTreeNode * cNode = *pRoot; // current node

BTreeNode * nNode = NULL; // new node

// 새로운 노드가 추가될 위치를 찾는다.

while(cNode != NULL){

if(data == GetData(cNode))

return; // 키의 중복을 허용하지 않음

pNode = cNode;

if(GetData(cNode) > data)

cNode = GetLeftSubTree(cNode);

else

cNode = GetRightSubTree(cNode);

}

// pNode의 서브 노드에 추가할 새 노드의 생성

nNode = MakeBTreeNode(); // 새 노드의 생성

SetData(nNode, data); // 새 노드에 데이터 저장

// pNode의 서브 노드에 새 노드를 추가

if(pNode != NULL){ // 새 노드가 루트 노드가 아니라면,

if(data < GetData(pNode))

MakeLeftSubTree(pNode, nNode);

else

MakeRightSubTree(pNode, nNode);

}

else{ // 새 노드가 루트 노드라면,

*pRoot = nNode;

}

BTreeNode * BSTSearch(BTreeNode * bst, int target){

BTreeNode * cNode = bst; // current node

int cd; // current data

while(cNode != NULL){

cd = GetData(cNode);

if(target == cd)

return cNode;

else if(target < cd)

cNode = GetLeftSubTree(cNode);

else

cNode = GetRightSubTree(cNode);

}

return NULL;

}

BTreeNode * BSTRemove(BTreeNode ** pRoot, int target){

// 삭제 대상이 루트 노드인 경우를 별도로 고려해야 한다.

BTreeNode * pVRoot = MakeBTreeNode(); // 가상 루트 노드;

BTreeNode * pNode = pVRoot; // parent node

BTreeNode * cNode = *pRoot; // current node

BTreeNode * dNode; // delete node

// 루트 노드를 pVRoot가 가리키는 노드의 오른쪽 서브 노드가 되게 한다.

ChangeRightSubTree(pVRoot, *pRoot);

// 삭제 대상을 저장한 노드 탐색

while(cNode != NULL && GetData(cNode) != target){

pNode = cNode;

if(target < GetData(cNode))

cNode = GetLeftSubTree(cNode);

else

cNode = GetRightSubTree(cNode);

}

if(cNode == NULL) // 삭제 대상이 존재하지 않는다면,

return NULL;

dNode = cNode; // 삭제 대상을 dNode가 가리키게 한다.

// 첫 번째 경우: 삭제할 노드가 단말 노드인 경우

if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL){

if(GetLeftSubTree(pNode) == dNode)

RemoveLeftSubTree(pNode);

else

RemoveRightSubTree(pNode);

}

// 두 번째 경우: 하나의 자식 노드를 갖는 경우

else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL){

BTreeNode * dcNode; // delete node의 자식 노드

if(GetLeftSubTree(dNode) != NULL)

dcNode = GetLeftSubTree(dNode);

else

dcNode = GetRightSubTree(dNode);

if(GetLeftSubTree(pNode) == dNode)

ChangeLeftSubTree(pNode, dcNode);

else

ChangeRightSubTree(pNode, dcNode);

}

// 세 번째 경우: 두 개의 자식 노드를 모두 갖는 경우

else{

BTreeNode * mNode = GetRightSubTree(dNode); // mininum node

BTreeNode * mpNode = dNode; // mininum node의 부모 노드

int delData;

// 삭제할 노드를 대체할 노드를 찾는다.

while(GetLeftSubTree(mNode) != NULL)

{

mpNode = mNode;

mNode = GetLeftSubTree(mNode);

}

// 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.

delData = GetData(dNode); // 대입 전 데이터 백업

SetData(dNode, GetData(mNode));

// 대체할 노드의 부모 노드와 자식 노드를 연결한다.

if(GetLeftSubTree(mpNode) == mNode)

ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));

else

ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

dNode = mNode;

SetData(dNode, delData); // 백업 데이터 복원

}

// 삭제된 노드가 루트 노드인 경우에 대한 처리

if(GetRightSubTree(pVRoot) != *pRoot)

*pRoot = GetRightSubTree(pVRoot);

free(pVRoot);

return dNode;

}

void ShowIntData(int data){

printf("%d ", data);

}

void BSTShowAll(BTreeNode * bst){

InorderTraverse(bst);

}

////////////////////////// 이진 탐색 트리 끝

///////////////////////// 메인 함수 시작

int main(void){

BTreeNode * bstRoot;

BTreeNode * sNode; // search node

BSTMakeAndInit(&bstRoot);

BSTInsert(&bstRoot, 5);

BSTInsert(&bstRoot, 8);

BSTInsert(&bstRoot, 1);

BSTInsert(&bstRoot, 6);

BSTInsert(&bstRoot, 4);

BSTInsert(&bstRoot, 9);

BSTInsert(&bstRoot, 3);

BSTInsert(&bstRoot, 2);

BSTInsert(&bstRoot, 7);