学步园

/*
 * binarySearchTree.cpp
 *
 *  Created on: 2012-4-17
 *      Author: jiyiqin
 *	实现二叉查找树的构造，插入，删除，查找节点等基本操作。
 */
#include <iostream>
#include <string>
#include <stdio.h>

using namespace std;

class BinarySearchTree{
private:

	typedef struct treeNode{
		int value;
		struct treeNode *parent;
		struct treeNode *left;
		struct treeNode *right;
	}NODE;

	NODE *malloc_node(int value, NODE *left, NODE *right){
		NODE *newNode = (NODE *)malloc(sizeof(NODE));
		newNode->value = value;
		newNode->left = left;
		newNode->right = right;
		return newNode;
	}
public:
	NODE *root;

	BinarySearchTree(){
		root = NULL;
	}

	/**
	 * 从一个数组构造BST：
	 * 构造的方法就是从空树开始
	 * 不断插入新的节点
	 * */
	void buildTree(int node[], int length){
		int i;

		for(i=0;i<length;i++){
			cout<<"insert "<<node[i]<<endl;
			insertNode(node[i]);
		}
	}

	/**
	 * 插入节点:
	 * 首先要明白，新插入的节点一定是作为叶子(没有孩子)
	 *	所以说插入的顺序不同，BST的结构会不同
	 *
	 * 所以插入操作就变得很简单，不用分不同情况,两步即可：
	 * (1)找到插入位置(NULL)：使用两个指针，一个寻找插入位置，一个指向其父节点;
	 * (2)插入(作为其父节点的儿子);
	 * */
	void insertNode(int newValue){
		NODE *p,*q;

		//if this node have exist
		if(search(root, newValue) != NULL){
			cout<<newValue<<"have existed"<<endl;
			return;
		}

		//insert first node
		if(root == NULL){
			cout<<"root is null"<<endl;
			root = malloc_node(newValue, NULL, NULL);
			return;
		}

		//find insert location
		q = root;
		while(q != NULL){
			p = q;
			if(newValue < q->value)
				q = q->left;
			else
				q = q->right;
		}

		//insert
		NODE *newNode = malloc_node(newValue, NULL, NULL);
		newNode->parent = p;
		if(newNode->value < p->value)
			p->left = newNode;
		else
			p->right = newNode;
	}

	/**
	* 删除节点:分三种情况
	* (1) 待删除节点没有孩子
	*	直接删除，无需调整
	* (2) 待删除节点有一个孩子
	*	将待删除节点的父节点指向待删除节点的孩子
	* (3) 待删除节点有两个孩子
	*	找到待删除节点的后继，同样将其删除(递归)，
	*	然后用该后继把待删除节点覆盖掉。
	*	问：如果不是调整其后继，而是调整其前驱可以么？
	*		--- 我觉得是可以
	* */
	void deleteNode(int value){
		NODE *parent, *child, *successor;

		//返回节点指针
		cout<<"delete"<<value<<endl;
		NODE *dnode = search(root,value);		
		
		if(dnode->left == NULL && dnode->right == NULL){		//没有孩子
			
			//直接将叶子删掉
			parent = dnode->parent;
			if(parent->left != NULL && dnode->value == parent->left->value)
				parent->left = NULL;
			else
				parent->right = NULL;
		}
		else if(dnode->left == NULL || dnode->right == NULL){	//一个孩子
			
			//找到待删除节点的孩子(左/右)
			if(dnode->left != NULL){
				child = dnode->left;
			}
			else{
				child = dnode->right;
			}

			//将待删除节点的父节点指向其孩子
			parent = dnode->parent;
			if(parent->left != NULL && dnode->value == parent->left->value)
				parent->left = child;
			else
				parent->right = child;
		}
		else if(dnode->left != NULL && dnode->right != NULL){	//两个孩子

			//找到后继
			successor = searchSuccessor(dnode);

			//递归删除该后继
			deleteNode(successor->value);

			//将后继的卫星数据拷贝到"本来应该删除的节点"
			dnode->value = successor->value;
			
		}
		else{
			cout<<"delete error"<<endl;
		}
	}

	/**
	 * 从node为根的BST上查找value节点
	 * @return
	 * NULL: search fail
	 * not NULL: NODE*
	 * */
	NODE *search(NODE *node, int value){
		if(node == NULL || value == node->value)
			return node;
		if(value < node->value)
			return search(node->left, value);
		else
			return search(node->right, value);
	}

	/**
	 * 返回节点的后继
	 * */
	NODE *searchSuccessor(NODE *node){
		NODE *p,*q;

		//先转向右
		p = node;
		q = p->right;
		if(q == NULL) return NULL;

		//再向左走到头
		while(q != NULL){
			p = q;
			q = q->left;
		}
		return p;
	}

	/**
	 * 递归中序遍历
	 * */
	void printTreeByInOrder(NODE *node){
		if(node != NULL){
			printTreeByInOrder(node->left);
			cout<<node->value<<" ";
			printTreeByInOrder(node->right);
		}
	}

	/**
	 * 随机填充一个数组
	 * */
	void radomArray(int a[], int size){
		int i;
		for(i=0;i<size;i++){
			*a++ = rand() % 30;
		}
	}
};

int main(){
	int a[15];
	BinarySearchTree bst;

	//随机填充数组a
	bst.radomArray(a, 15);

	//用数组a来构造BST
	bst.buildTree(a, 15);

	//中序输出
	cout<<endl<<"In-Order-Out:";
	bst.printTreeByInOrder(bst.root);

	//删除一个节点并中序输出
	cout<<endl;
	bst.deleteNode(a[1]);
	cout<<endl<<"In-Order-Out:";
	bst.printTreeByInOrder(bst.root);

	//删除一个节点并中序输出
	cout<<endl;
	bst.deleteNode(a[2]);
	cout<<endl<<"In-Order-Out:";
	bst.printTreeByInOrder(bst.root);

	//删除一个节点并中序输出
	cout<<endl;
	bst.deleteNode(a[4]);
	cout<<endl<<"In-Order-Out:";
	bst.printTreeByInOrder(bst.root);
	return 0;
}