树（二）二叉查找树

SearchTree每个节点被指定一个Key，这里假设Key是不同的（这一假设是合理的，在实际应用中，按照Key来存储不同的软件信息，若有相同Key可以增加一个引用计数字段）。

SearchTree具有结构性和堆序性：

结构性：二叉树

堆序性：所有节点的左子树上所有节点的Key值比自身小，右子树上所有节点Key值比自身大

头文件searchtree.h

#ifndef _SEARCHTREE_H_
#define _SEARCHTREE_H_

struct TreeNode;
typedef struct TreeNode * Position;
typedef struct TreeNode * SearchTree;

SearchTree MakeEmpty(SearchTree);
Position Find(element_t, SearchTree);
Position FindMin(SearchTree);
Position FindMax(SearchTree);
SearchTree Insert(element_t, SearchTree);
SearchTree Delete(element_t, SearchTree);

#endif

C文件searchtree.c

#ifdef _cplusplus
extern "C" {
#endif

typedef unsigned int element_t;

#include <stdlib.h>
#include <assert.h>
#include "searchtree.h"

struct TreeNode
{
	element_t element;
	SearchTree Left;		//ptr to left child
	SearchTree Right;		//ptr to right child
};

/* destroy a searchtree, return nullptr */
SearchTree MakeEmpty(T)
	SearchTree T;
{
	if (T)
	{
		MakeEmpty(T->Left);
		MakeEmpty(T->Right);
		free(T);
	}
	return (SearchTree)0;
}

/* O(logN)时间，N是节点数 */
Position Find(element, T)
	element_t element;
	SearchTree T;
{
	if (!T)
	{
		return (Position)0;
	}
	if (element < T->element)
	{
		return Find(element, T->Left);
	}
	else if (element > T->element)
	{
		return Find(element, T->Right);
	}
	
	return T;
}

/* recursive implementation */
Position FindMin(T)
	SearchTree T;
{
	if (!T)
	{
		return (Position)0;
	}
	/* 若没有左儿子，这个节点就是最小的 */
	else if (!T->Left)
	{
		return T;
	}

	return FindMin(T->Left);
}

/* 非递归 */
Position FindMax(T)
	SearchTree T;
{
	if (T)
	{
		while (T->Right)
		{
			T = T->Right;
		}
	}

	return T;
}
/* O(logN)时间 */
SearchTree Insert(element, T)
	element_t element;
	SearchTree T;
{
	if (!T)
	{
		T = malloc(sizeof(struct TreeNode));
		assert(T != NULL);
		T->Left = T->Right = (SearchTree)0;
		T->element = element;
	}
	else if (element < T->element)
	{
		T->Left = Insert(element, T->Left);
	}
	else if (element > T->element)
	{
		T->Right = Insert(element, T->Right);
	}
	else
	{
		//todo
	}

	return T;
}
/* O(logN)时间 */
SearchTree Delete(element, T)
	element_t element;
	SearchTree T;
{
	Position Tmp;

	if (!T)
	{
		//todo
	}
	/* 寻找这个节点，不能用find，因为递归过程要挂接内存 */
	else if (element < T->element)
	{
		T->Left = Delete(element, T->Left);
	}
	else if (element > T->element)
	{
		T->Right = Delete(element, T->Right);
	}
	/* 若要删除的节点有两个儿子，用左子树最大的节点代替本节点，并删除左子树上的这个节点 */
	else if (T->Left && T->Right)
	{
		Tmp = FindMax(T->Left);
		T->element = Tmp->element;
		T->Left = Delete(Tmp->element, T->Left);
	}
	else
	{
		/* 若该节点是树叶或者只有一个儿子，很好处理 */
		Tmp = T;
		if (!T->Left)
		{
			T = T->Right;
		}
		else
		{
			T = T->Left;
		}
		free(Tmp);
	}
	
	return T;
}



#ifdef _cplusplus
}
#endif