Introduction-To-Algorithms-Cpp-code/docs/ch12/Tree.h at master · EeeUnS/Introduction-To-Algorithms-Cpp-code · GitHub

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
#ifndef __TREE_H__
#define __TREE_H__

#include<iostream>
//using namespace std;

struct Node
{
	Node* right_large; // key >=
	int key;
	Node* left_small; // key <
	Node* parent;
};


//트리 노드의 캡슐화가 보장되지않는다.
class BST //binary search tree
{
public:
	BST();
	BST(int n);
	~BST();
	void insert(int n);

	void preorder();//12.1-4
	void Inorder();//12.1-3
	void postorder(); //12.1-4

	Node* TREE_MINIMUM(Node* x);
	Node* TREE_MAXIMUM(Node* x);

	Node* TREE_SUCCESSOR(Node* x);
	Node* TREE_PREDECESSOR(Node* x);

	void TREE_INSERT(Node* z);
	void TREE_DELETE(Node* z);

	void INORDER_TREE_WALK(Node* x);
	Node* TREE_SEARCH(Node* x, int k);
	Node* ITERATIVE_TREE_SEARCH(Node* x, int k);

	Node* getter_ROOT() const;
private:
	Node* ROOT;
	Node* NIL;

	void inorder_procedure(Node* _node);
	void preorder_procedure(Node* _node);
	void postorder_procedure(Node* _node);
	void delete_node(Node* _node);
	void TRANSPLANT(Node* u, Node* v);

};


#endif