ツリー実装

8513 ワード

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <stack>
#include <queue>

using namespace std;

template <typename T>
struct node {
	struct node *ln; 
	struct node *rn; 
	struct node *pn; 
	T val;
};

template <typename T>
class MyBST {
private:
	struct node<T> *root;

private:
	void pre_walk_recv(struct node<T> *root);
	void in_walk_recv(struct node<T> *root);
	void post_walk_recv(struct node<T> *root);
	struct node<T>* minimum_internal(struct node<T> *root);
	struct node<T>* maximum_internal(struct node<T> *root);

public:
	MyBST();
	void pre_walk();
	void in_walk();
	void post_walk();
	void pre_walk_iter();
	void in_walk_iter();
	void post_walk_iter();
	void dfs_walk();
	void dfs_order_walk();
	void insert(T val);
	int minimum();
	int maximum();
	struct node<T>* search(int val);
	struct node<T>* predecessor(struct node<T> *n);
	struct node<T>* successor(struct node<T> *n);
	void remove(struct node<T> *n);
};

template <typename T>
void MyBST<T>::pre_walk_recv(struct node<T> *root)
{
	if(root == NULL)
		return;
	printf("%d ", root->val);
	pre_walk_recv(root->ln);
	pre_walk_recv(root->rn);
}

template <typename T>
void MyBST<T>::in_walk_recv(struct node<T> *root)
{
	if(root == NULL)
		return;
	in_walk_recv(root->ln);
	printf("%d ", root->val);
	in_walk_recv(root->rn);
}
	
template <typename T>
void MyBST<T>::post_walk_recv(struct node<T> *root)
{
	if(root == NULL)
		return;
	post_walk_recv(root->ln);
	post_walk_recv(root->rn);
	printf("%d ", root->val);
}

template <typename T>
MyBST<T>::MyBST()
{
	root = NULL;
}

template <typename T>
void MyBST<T>::pre_walk()
{
	pre_walk_recv(root);
	printf("
"); } template <typename T> void MyBST<T>::in_walk() { in_walk_recv(root); printf("
"); } template <typename T> void MyBST<T>::post_walk() { post_walk_recv(root); printf("
"); } template <typename T> void MyBST<T>::insert(T val) { struct node<T> *n = (struct node<T> *)malloc(sizeof(struct node<T>)); n->ln = NULL; n->rn = NULL; n->pn = NULL; n->val = val; if(root == NULL) { root = n; return; } struct node<T> *tmp = root; while(tmp != NULL) { if(n->val <= tmp->val) { if(tmp->ln == NULL) { tmp->ln = n; n->pn = tmp; return; } else { tmp = tmp->ln; } } else { if(tmp->rn == NULL) { tmp->rn = n; n->pn = tmp; return; } else { tmp = tmp->rn; } } } } template <typename T> struct node<T>* MyBST<T>::minimum_internal(struct node<T> *root) { struct node<T> *tmp = root; while(tmp->ln != NULL) tmp = tmp->ln; return tmp; } template <typename T> struct node<T>* MyBST<T>::maximum_internal(struct node<T> *root) { struct node<T> *tmp = root; while(tmp->rn != NULL) tmp = tmp->rn; return tmp; } template <typename T> int MyBST<T>::minimum() { return minimum_internal(root)->val; } template <typename T> int MyBST<T>::maximum() { return maximum_internal(root)->val; } template <typename T> struct node<T>* MyBST<T>::search(int val) { struct node<T> *tmp = root; while(tmp != NULL) { if(tmp->val == val) break; if(val < tmp->val) tmp = tmp->ln; else tmp = tmp->rn; } return tmp; } template <typename T> struct node<T>* MyBST<T>::predecessor(struct node<T> *n) { if(n->ln != NULL) return maximum_internal(n->ln);  struct node<T> *pred = n->pn; while(pred!=NULL && pred->ln==n) { n = pred; pred = pred->pn; } return pred; } template <typename T> struct node<T>* MyBST<T>::successor(struct node<T> *n) { if(n->rn != NULL) return minimum_internal(n->rn); struct node<T> *pred = n->pn; while(pred!=NULL && pred->rn==n) { n  = pred; pred = pred->pn; } return pred; } template <typename T> void MyBST<T>::remove(struct node<T> *n) { struct node<T> *tmp; // if one of children is NULL if(n->ln==NULL || n->rn==NULL) { if(n->ln == NULL) tmp = n->rn; else tmp = n->ln; if(n != root) { struct node<T> *pn = n->pn; if(pn->ln == n) pn->ln = tmp; else pn->rn = tmp; if(tmp != NULL) tmp->pn = pn; } else { root = tmp; if(tmp != NULL) root->pn = NULL; } free(n); return; } // if both children are not NULL tmp = minimum_internal(n->rn); n->val = tmp->val; if(tmp == tmp->pn->ln) tmp->pn->ln = tmp->rn; else tmp->pn->rn = tmp->rn; if(tmp->rn != NULL) tmp->rn->pn = tmp->pn; free(tmp); return; } template <typename T> void MyBST<T>::pre_walk_iter() { struct node<T> *tmp = root; stack< struct node<T>* > stk; while(1) { while(tmp != NULL) { printf("%d ", tmp->val); if(tmp->rn != NULL) stk.push(tmp); tmp = tmp->ln; } if(!stk.empty()) { tmp = stk.top()->rn; stk.pop(); } else { break; } } printf("
"); } template <typename T> void MyBST<T>::in_walk_iter() { struct node<T>* tmp = root; stack< struct node<T>* > stk; while(1) { while(tmp != NULL) { stk.push(tmp); tmp = tmp->ln; } if(!stk.empty()) { printf("%d ", stk.top()->val); tmp = stk.top()->rn; stk.pop(); } else { break; } } printf("
"); } template <typename T> void MyBST<T>::post_walk_iter() { struct node<T> *tmp = root; stack< struct node<T>* > stk; stack<T> ot; while(1) { while(tmp != NULL) { ot.push(tmp->val); stk.push(tmp); tmp = tmp->rn; } if(!stk.empty()) { tmp = stk.top()->ln; stk.pop(); } else { break; } } while(!ot.empty()) { printf("%d ", ot.top()); ot.pop(); } printf("
"); } template <typename T> void MyBST<T>::dfs_walk() { struct node<T> *tmp = root; queue< struct node<T>* > q; q.push(tmp); while(!q.empty()) { tmp = q.front(); q.pop(); printf("%d ", tmp->val); if(tmp->ln != NULL) q.push(tmp->ln); if(tmp->rn != NULL) q.push(tmp->rn); } printf("
"); } template <typename T> void MyBST<T>::dfs_order_walk() { struct node<T> *tmp = root; queue< struct node<T>* > q1; queue<int> q2; q1.push(tmp); q2.push(0); int cd = 0; while(!q1.empty()) { tmp = q1.front(); if(q2.front() > cd) { printf("
"); cd++; } q1.pop(); q2.pop(); printf("%d ", tmp->val); if(tmp->ln != NULL) { q1.push(tmp->ln); q2.push(cd+1); } if(tmp->rn != NULL) { q1.push(tmp->rn); q2.push(cd+1); } } printf("
"); } int main(int argc, char **argv) { MyBST<int> mb; mb.insert(10); mb.insert(5); mb.insert(17); mb.insert(4); mb.insert(8); mb.insert(22); mb.insert(6); mb.insert(9); mb.insert(20); mb.insert(7); mb.insert(15); mb.insert(16); printf("RECV:
"); mb.pre_walk(); mb.in_walk(); mb.post_walk(); printf("ITER:
"); mb.pre_walk_iter(); mb.in_walk_iter(); mb.post_walk_iter(); printf("DFS:
"); mb.dfs_walk(); printf("ORDER:
"); mb.dfs_order_walk(); printf("minimum: %d
", mb.minimum()); printf("maximum: %d
", mb.maximum()); int target = 4; struct node<int> *tmp = mb.search(target); printf("search for %d is %d
", target, tmp->val); struct node<int> *pred = mb.predecessor(tmp); struct node<int> *succ = mb.successor(tmp); printf("pred: %d
", pred==NULL?-999:pred->val); printf("succ: %d
", succ==NULL?-999:succ->val); mb.remove(tmp); //target = 16; //tmp = mb.search(target); //printf("search for %d is %d
", target, tmp->val); // //mb.remove(tmp); mb.pre_walk(); mb.in_walk(); mb.post_walk(); return 0; }