以下为算法详细流程及其实现。由于算法都用伪代码给出，就免了一些文字描述。
/*================JJ日记=====================
作者: JJDiaries(阿呆)
邮箱：JJDiaries@gmail.com
日期: 2013-11-13
============================================*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDLEN 16
//定义一个节点，除了存放key值外，还包含了一个data字符数组用于存放一个单词
struct node{
int key;
char data[WORDLEN];
struct node *parent;
struct node *left;
struct node *right;
};
typedef struct node * tree;
/*============================================
树的中序遍历
INORDER_TREE_WALK(x)
if x!=NIL
then INORDER_TREE_WALK(left[x])
print key[x]
INORDER_TREE_WALK(left[x])
============================================*/
void inorder_tree_walk(tree T)
{
if(T!=NULL){
inorder_tree_walk(T->left);
printf("key:%d words:%s\n",T->key,T->data);
inorder_tree_walk(T->right);
}
}
/*============================================
树的搜索，返回含有关键字k的结点
TREE_SEARCH(x,k) //递归版本
if x=NIL or k =key[x]
then return x
if k<key[x]
then return TREE_SEARCH(left[x],k)
else return TREE_SEARCH(right[x],k)
TREE_SEARCH(x,k) //非递归版本
while x!=NIL and k!= key[x]
do if k<key[x]
then x <—— left[x]
else x <—— right[x]
return x
============================================*/
//递归版本
struct node* tree_search(tree T,int k)
{
if(T==NULL || k == T->key)
return T;
if(k < T->key)
return tree_search(T->left,k);
else
return tree_search(T->right,k);
}
//非递归版本
struct node* tree_search1(tree T,int k)
{
while(T!=NULL && T->key!=k)
if(k < T->key)
T=T->left;
else
T=T->right;
return T;
}
/*============================================
返回key值最小的结点
TREE_MINIMUM(x)
while left[x]!=NIL
do x <—— left[x]
return x
============================================*/
struct node* tree_minimum(tree T)
{
while(T->left != NULL)
T=T->left;
return T;
}
/*============================================
返回key值最大的结点
TREE_MAXMUM(x)
while right[x]!=NIL
do x <—— right[x]
return x
============================================*/
struct node* tree_maxmum(tree T)
{
while(T->right != NULL)
T=T->right;
return T;
}
/*============================================
中序遍历下，返回某一结点的后继结点
1）如果结点x有右子结点，则其后继结点为右子树中最小结点。
2）如果结点x没有右子树，且x有一个后继y，则y是x的最低祖先结点
且y的左儿子也是x的祖先。
TREE_SUCCESSOR(x)
if right[x] != NIL
return TREE_MINIMUM(right[x])
y=p[x]
while y!=NIL and x=right[y] //如果x=left[y]，那么x的后继就是y，跳出while循环，直接返回y即可
do x <—— y
y <—— p[y]
return y
============================================*/
struct node * tree_successor(struct node *T)
{
if(T->right!=NULL)
return tree_minimum(T->right);
struct node *y=T->parent;
while(y!=NULL && T == y->right){
T=y;
y=y->parent;
}
return y;
}
/*===========================================
插入操作
思路：从根节点一路往下寻找插入位置，用指针x跟踪这条寻找路径，并用指针y指向x的父结点
TREE_INSERT(T,z)
y=NIL
x=root[T]
while x!= NIL //直到x为空，这个空位置即为需要插入的位置
do y<—— x
if key[z]<key[x]
then x <—— left[x]
else x <—— right[x]
p[z]=y
if y=NIL
then root[T]=z //树T为空时的情况
else if key[z] < key[y]
then left[y]=z //小于y的插在左边，大于的插在右边
else right[y]=z
============================================*/
void tree_insert(tree *PT,struct node *z)
{
if(*PT==NULL){//树为空，则将z作为根结点返回
*PT=z;
return;
}
struct node *y=NULL;
struct node *x=*PT;
while(x!=NULL){
y=x;
if(z->key < x->key)
x=x->left;
else
&n