二叉查找树

这是我现在写的版本,我觉得应该算是最凝练的了. 哈哈,容我臭美一下.(我是指那个删除的函数,感觉比<数据结构与算法分析.C语言描述>那个书上的要好. 主要是我喜欢用二级指针, 而那本书上用的是一级指针加返回一个指针来重建链.)

#include <iostream>

using namespace std;

struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int x_) : val(x_), left(NULL), right(NULL){}
};

void Insert(Node** root, int x);
void Delete(Node** root, int x);
Node* Find(Node *root, int x);
Node* FindMin(Node* root);
Node* FindMax(Node* root);
int Height(Node* root);
void PreOrder(Node *root);

void Insert(Node** root, int x)
{
	if (*root == NULL)
		*root = new Node(x);
	else {
		if ((*root)->val == x)
			return;
		else if ((*root)->val < x)
			Insert(&((*root)->right), x);
		else 
			Insert(&((*root)->left), x);
	}
}

void Delete(Node** root, int x)
{
	if (*root == NULL) return;

	if ((*root)->val > x)
		Delete(&((*root)->left), x);
	else if ((*root)->val < x)
		Delete(&((*root)->right), x);
	else{
		if ((*root)->left && (*root)->right){
			Node* p = FindMin((*root)->right);
			(*root)->val = p->val;
			Delete(&((*root)->right), (*root)->val);
		}else if ((*root)->left){
			Node* p = (*root);
			(*root) = (*root)->left;
			delete p;
		}else if ((*root)->right){
			Node* p = (*root);
			(*root) = (*root)->right;
			delete p;
		}else {
			delete (*root);
			*root = NULL;
		}
	}
}
			
Node* Find(Node *root, int x)
{
	if (root == NULL) return NULL;

	if (root->val == x)
		return root;
	else if (root->val > x)
		if (root->left)	return Find(root->left, x);
		else return NULL;
	if (root->val < x)
		if (root->right) return Find(root->right, x);
		else return NULL;

	return NULL;
}

Node* FindMin(Node* root)
{
	if (root == NULL) return NULL;

	while (root->left)
		root = root->left;	

	return root;
}

Node* FindMax(Node* root)
{
	if (root->right)
		return FindMax(root->right);
	else 
		return root;
}

int Height(Node* root)
{
	if (root == NULL) return 0;
	else {
		int i, j;
		i = Height(root->left);
		j = Height(root->right);
		return i > j ? i+1 : j+1;
	}
}


void PreOrder(Node *root)
{
	cout << root->val << " ";
	if (root->left)
		PreOrder(root->left);
	if (root->right)
		PreOrder(root->right);
}

int main()
{
	Node *bst = NULL;
	Insert(&bst, 9);
	Insert(&bst, 6);
	Insert(&bst, 3);
	Insert(&bst, 7);
	Insert(&bst, 15);
	Insert(&bst, 10);
	Insert(&bst, 17);

	cout << ((Node*)Find(bst, 10))->val << endl;
	cout << ((Node*)FindMin(bst))->val << endl;
	cout << ((Node*)FindMax(bst))->val << endl;
	Delete(&bst, 10);
	cout << "Height: " << Height(bst) << endl;
	PreOrder(bst);
	return 0;
}