BST 二叉查找树

自己实现的 二叉查找树，受益于人，回馈于人

#include <stdio.h>
#include <stdlib.h>
typedef struct node* pNode;
struct node {
	int data;
	pNode left;
	pNode right;
	pNode parent;
};

pNode root;

void traverse(pNode);
pNode search(pNode, int);
pNode getMin(pNode);
pNode getMax(pNode);
pNode getSuccessor(pNode, int);
void insert(pNode* root, pNode element); //////// insert new element
pNode delete(pNode* root, int);

#include "BSTree.h"

/*************************
 * Binary search tree
 * 
 * By Jia Pengcheng
 *************************/

void traverse(pNode root){
	
	pNode st = root;
	if(st){
		traverse(st->left);
		printf("%d, ", st->data);
		traverse(st->right);
	}
}

void insert(pNode* root, pNode element){
	
	//<1> first, need to know whether this element has been in the tree
	
	pNode start = *root;
	
	// if the tree is empty
	if(!start){
		*root = element;
		return;
	}
	
	pNode backup_start = NULL;
	while(start){
		backup_start = start; // save the position for insertion
		if(element->data > start->data){
			start = start->right;
		}else if(element->data <= start->data){
			start = start->left;
		}
	}
	
	// if not existed
	element->parent = backup_start;
	if(element->data > backup_start->data){
		backup_start->right = element;
	}else{
		backup_start->left = element;
	}
}

pNode search(pNode root, int val){
	
	pNode st = root;
	
	while(st && (st->data != val)){
		if(st->data > val){
			st = st->left;
		}else if(st->data < val){
			st = st->right;
		}
	}
	
	return st;
}

pNode getMax(pNode root){
	pNode st = root;
	while(st->right){
		st = st->right;
	}
	
	return st;
}

pNode getMin(pNode root){
	pNode st = root;
	while(st->left){
		st = st->left;
	}
	return st;
}

pNode getSuccessor(pNode root, int val){
	
	pNode elem = NULL;
	if(!(elem = search(root, val))) return NULL;
	
	// if elem has right child, successor is the minimum element
	if(elem->right){
		return getMin(elem->right);
	}else{ //////////// if has no right child, find the node which is its parent's left child, ruturn the parent
 		pNode tmp = elem->parent;
 		while(tmp && elem == tmp->right){
			elem = tmp;
			tmp = tmp->parent;
		}
		return tmp;
		
		//pNode tmp = NULL;
		//do{
			//tmp = elem;
			//elem = elem->parent;
		//}while(elem && (tmp == elem->right));
		
		//return tmp;
	}
}

/// one child, two childs, 0 child
pNode delete(pNode* root, int val){
	/// empty tree
	if(!*root) return;
	
	// this elem is not in the tree
	pNode elem = search(*root, val);
	if(!elem){
		printf("%d is not in the tree\n", val);
		return NULL;
	}
	
	pNode tmp = NULL;
	if(!elem->left || !elem->right){
		tmp = elem;  /// if elem has one child or zero child
	}else{
		tmp = getSuccessor(*root,val);  /// id elem has two childs, delete successor of elem, and then replace elem with successor
		/// we need to know that successor of elem has one right child at most, it does not have left child
		///printf("Successor is %d\n", tmp->data);
	}
	
	///========================= has at most one child ============================
	pNode child = NULL;
	if(tmp->left)   /// why left first? cos successor of elem has no left child 
		child = tmp->left;
	else
		child = tmp->right;
		
	if(child)
		child->parent = tmp->parent; /// set parent pointer of elem's child, when tmp has one child
	
	/// if tmp has parent, it means that it is not the root node
	if(tmp->parent){
		if(tmp == tmp->parent->left){
			tmp->parent->left = child;
		}else{
			tmp->parent->right = child;
		}
	}else{
		*root = child; /// tmp has no parent, it is root, when tmp is deleted, child should become the root
	}
	/// ===========================================================
	
	///if tmp has two childs, tmp is the successor of tmp, so tmp != elem
	if(tmp != elem){
		elem->data = tmp->data;  /// replace date of elem with data of tmp which is the successor of elem
	}
	
	return tmp;
}