이 진 트 리 구조 - 기초

template 
class BSTNode :public BinNode {
private:
	Key key;
	E item;
	BSTNode* lc;
	BSTNode* rc;
public:
	BSTNode() { lc = rc = NULL; }
	BSTNode(Key k, E it, BSTNode* lc=NULL, BSTNode* rc=NULL) {
		key = k; item = it; 
		this.lc = 

1. 기본 개념: 나 무 는 간단 한 연결 그림 이 고 이 진 트 리 는 2 원 나무 이 며 하나의 결점 은 최대 두 개의 결점 만 있 을 수 있다.
결점: 하나의 데이터 요소 와 몇 개의 하위 트 리 를 가리 키 는 가 지 를 포함 합 니 다.
자 결점: 결점 의 자나무 뿌리 를 이 결점 의 아이 라 고 부른다
아버지 결점: B 결점 은 A 결점 의 아이 이 고 A 결점 은 B 결점 의 부모 이다.
조상: 뿌리 에서 이 결점 까지 의 모든 결점
후대: 어떤 결점 을 뿌리 로 하 는 나무 중 어떤 결점 도 이 결점 의 자손 이 라 고 부른다.
결점 의 도: 결점 나무의 개수
잎 결점: 단말기 결점 이 라 고도 하 는데 0 의 결점 이다.
내부 결점: 도 0 이 아 닌 결점
결점 층: 뿌리 결점 의 층 은 0 (외국 교재) 으로 정의 되 고 중국어 교 재 는 1 로 정의 된다.
깊이: 나무 에서 가장 큰 결점 층
높이: 1 부터
2. 특수 이 진 트 리 분류:
(1) 만 이 진 트 리 (full binary tree): 잎 결 점 을 제외 하고 모든 결 점 은 좌우 자엽 이 있 고 잎 결 점 은 모두 최 하층 에 있 는 이 진 트 리 이다.
두 가지 정리: a. 잎 결점 의 수 는 내부 결점 보다 1 이 많다 (수학 귀납법)
                  b. 빈 나무의 수 는 잎 결산 점 의 수 보다 많다.
(2) 완전 이 진 트 리 (complete bianary tree): 만약 에 이 진 트 리 의 높이 가 h 라면 h 층 을 제외 하고 다른 각 층 (1 ～ h - 1) 의 결 점 수 는 모두 최대 개수 에 달 하고 h 층 에는 잎 결점 이 있 으 며 잎 결점 은 모두 왼쪽 에서 오른쪽으로 순서대로 배열 된다.
3. 비 나 루 트 리 노드 ADT

class BinNode {
public:
	virtual ~BinNode() {}
	virtual E& element() = 0;
	virtual void setElement(const E&) = 0;
	virtual BinNode* left() const = 0;
	virtual void setLeft(BinNode*) = 0;
	virtual BinNode* right()const = 0;
	virtual void setRight(BinNode*) = 0;
	virtual bool isLeaf() = 0;
};

(1) 순서 저장 구조
N 개의 결점 이 있 는 완전 이 진 트 리 의 각 결점 을 순서대로 저장 하면 결점 간 에는 다음 과 같은 관계 가 있다.
만약 에 I 가 결점 번호 라면 I > 1 이면 그 아버지 결점 의 번 호 는 I / 2 이다.
2 * I < = N 이면 왼쪽 아들 (즉 왼쪽 나무의 뿌리 결산 점) 의 번 호 는 2 * I 이 고 2 * I > N 이면 왼쪽 아들 이 없다.
2 * I + 1 & lt; = N 이면 오른쪽 아들 의 결점 번 호 는 2 * I + 1 이 고, 2 * I + 1 & gt; N 이면 오른쪽 아들 이 없다.
(2) 체인 식 저장 구조

template 
class BSTNode :public BinNode {
private:
	Key key;
	E item;
	BSTNode* lc;
	BSTNode* rc;
public:
	BSTNode() { lc = rc = NULL; }
	BSTNode(Key k, E it, BSTNode* lc=NULL, BSTNode* rc=NULL) {
		key = k; item = it; 
		this.lc = lc;  this.rc = rc;
	}
	~BSTNode() {}

	E& element() {
		return item;
	}
	void setElement(const E& it) { item = it; }
	Key& getkey() {
		return key;
	}
	void setKey(Key& k) { key = k;}
	BSTNode* left()const { return lc; }
	void setLeft(BinNode* l) { lc = (BSTNode*)l; }
	BSTNode* right()const { return rc; }
	void setRight(BinNode* r) { rc = (BSTNode*)r; }

	bool isLeaf() {
		return (lc == NULL) && (rc == NULL);
	}
	
};

4. 이 진 트 리 옮 겨 다 니 기 (traversal)
L, D, R 을 설정 하면 왼쪽 하위 트 리 를 옮 겨 다 니 고 뿌리 노드 에 접근 하 며 오른쪽 하위 트 리 를 옮 겨 다 니 는 것 을 나타 내 며 이 진 트 리 한 그루 를 옮 겨 다 니 는 데 세 가지 상황 이 있 습 니 다. DLR (선 근 순서 로 옮 겨 다 니 는 것 이 라 고 함), LDR (중 근 순서 로 옮 겨 다 니 는 것 이 라 고 함), LRD (후 근 순서 로 옮 겨 다 니 는 것 이 라 고 함).
옮 겨 다 니 면서 재 귀 를 계속 사용 하 다.
다음 순서 로 옮 겨 다 니 기:

template
void preorder(BinNode* root) {
	if (root == 0) return;
	cout << root->element() << " ";
	if(root->left()!=NULL)  preorder(root->left());
	if(root->right()!=NULL) preorder(root->right());
}

다섯. 이 진 트 리 로 이 진 트 리 구현 (Binary Search Tree)

//Binary Search Tree
template 
class BST {
private:
	BSTNode* root;
	int nodecount;
	//            ，  
	BSTNode* inserthelp(BSTNode* root, const K& key, const E& elem) {
		if (root == NULL) return new BSTNode(key, elem);
		else if (root->getkey() > key)  root->setLeft(inserthelp(root->left(), key, elem));
		else root->setRight(inserthelp(root->right(), key, elem));
		return root;
	}
	//  
	E findhelp(BSTNode* root, const K& key) {
		if (root == NULL) return;
		else if (root->getkey() > key) return findhelp(root->left(), key);
		else if (root->getkey() < key) return findhelp(root->right(), key);
		else return root->element;
	}
	//     ，         ，                   
	BSTNode* deletemin(BSTNode*rt) {
		if (rt->left() == NULL) {
			BSTNode* rightnode = rt->right();
			delete rt;
			return rightnode;
		}
		else {
			rt->setLeft(deletemin(rt->left()));
			return rt;
		}
	}
	BSTNode getmin(BSTNode* rt) {
		if (rt->left() == NULL)
			return rt;
		else return getmin(rt->left());
	}
	//  key     
	BSTNode removehelp(BSTNode* root, const K& key) {
		if (root == NULL) return NULL;
		else if (key < root->getkey()) removehelp(root->left(), key);
		else if (key > root->getkey()) removehelp(root->right(), key);
		else {
			BSTNode* temp = root;
			if (root->left() == NULL) {//     
				root=root->right();
				delete temp;
			}
			else if (root->right() == NULL) {//     
				root = root->left();
				delete temp;
			}
			else {//        
				temp = getmin(root->right());
				root->setElement(temp->element);
				root->setKey(temp->key());
				root->setRight(deletemin(root->right()));
				delete temp;
			}
			
		}
		return root;
	}
public:
	BST() {
		root = NULL;
		nodecount = 0;
	}
	void insert(const K& key, const E& elem) {
		root = inserthelp(root, key, elem);
		nodecount++;
	}
	E find(const K& key) {
		return findhelp(root, key);
	}
	int size() { return nodecount; }
	E removeAny() {
		if (root == NULL) return NULL;
		else {
			E temp = root->element;
			root = removehelp(root, root->getkey());
			nodecount--;
			return temp;
		}
	}
};

6. 이 진 트 리 로 이 진 트 리 구현 (Binary Heap)
완전 이 진 더 미 는 쌓 인 성질 을 가지 기 때문에 보통 이 진 트 리 의 순서 저장 구조 로 이 진 더 미 를 실현 한다.

//    

class Heap {
private:
	int* heap;
	int maxSize;
	int n;
	void shiftdown(int pos) {
		//        
		while (!isLeaf(pos)) {
			int lc = leftchild(pos);
			if ((lc + 1 < n) && (heap[lc] < heap[lc + 1]))  lc + 1;
			if (heap[pos] > heap[lc]) break;
			swap(heap[pos], heap[lc]);
			pos = lc;
		}
	}
public:
	Heap(int n=100) {
		maxSize = n;
		heap = new int[maxSize];
		n = 0;
	}
	Heap(int* h, int num, int ms) {
		heap = h;
		n = num;
		maxSize = ms;
		buildHeap();
	}
	int size() { return n; }
	bool isLeaf(int pos) {
		if ((pos >= n / 2) && (pos < n))
			return true;
		else
			return false;
	}
	int leftchild(int pos) {
		assert(pos < n / 2);
		return pos * 2+1;
	}
	int rightchild(int pos) {
		assert(pos < n / 2);
		return pos * 2 + 2;
	}
	int parent(int pos) {
		assert(pos > 0);
		return (pos - 1) / 2;
	}
	void buildHeap() {
		//             ，     shiftdown  
		for (int i = (n / 2 - 1); i >= 0; i--) {
			shiftdown(i);
		}
	}
	void insert(const int& it) {
		assert(n <= maxSize);
		heap[n] = it;
		int curr=n++;
		while (curr > 0 && (heap[curr] > heap[parent(curr)])){
			swap(heap[curr], heap[parent(curr)]);
			curr = parent(curr);
		}

	}
	int removefirst() {
		assert(n > 0);
		int max = heap[0];
		swap(heap[0], heap[--n]);
		if (n != 0) shiftdown(0);
		return max;
	}
	int remove(int pos) {
		assert((pos < n) && (pos >= 0));
		if (pos == (n - 1)) { return heap[--n]; }
		else {
			swap(heap[pos], heap[--n]);
			while ((pos != 0) && (heap[pos] > heap[parent(pos)])) {
				swap(heap[pos], heap[parent(pos)]);
				pos = parent(pos);
			}
		}
		if (pos != 0) shiftdown(pos);
		return heap[n];
	}
};