首页 > 代码库 > 二叉查找树

二叉查找树

2024-07-11 17:33:58   225人阅读

引言：


        使二叉树成为二叉查找树的性质是：对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。


二叉查找树声明

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

struct TreeNode{
	ElementType Element;
	SearchTree  Left;
	SearchTree  Right;
};

建立一棵空树的例程

SearchTree MakeEmpty(SearchTree T)
{
	if(T != NULL){
		MakeEmpty(T->Left);	
		MakeEmpty(T->Right);	
		free(T);
	}

	return NULL;
}

二叉查找树的Find操作

Position Find(ElementType X, SearchTree T)
{
	if(T == NULL)
		return NULL;
	if(X < T->Element)
		return Find(X, T->Left);
	else if(X > T->Element)
		return Find(X, T->Right);
	return T;
}

二叉查找树的FindMin递归与非递归实现

Position FindMin(SearchTree T)
{
	if(T == NULL)
		return NULL;	
	else if(T->Left == NULL)
		return T;
	else 
		return FindMin(T->Left);
}

Position FindMin(SearchTree T)
{
	if(T != NULL)
		while(T->Left != NULL)
			T = T->Left;	
	return T;
}

二叉查找树的FindMax递归与非递归实现

Position FindMax(SearchTree T)
{
	if(T == NULL)
		return NULL;
	else if(T->Right == NULL)
		return T;
	else 
		return FindMax(T->Right);
}

Position FindMax(SearchTree T)
{
	if(T != NULL)
		while(T->Right != NULL)		
			T = T->Right;	
	return T;
}

插入元素到二叉查找树的例程

SearchTree Insert(ElementType X, SearchTree T)
{
	if(T == NULL){
		T = (SearchTree)malloc(sizeof(struct TreeNode));	
		if(T == NULL){
			printf("Out of space.\n");
			return NULL;
		}
	}else if(X < T->Element){
		T->Left = Insert(X, T->Left);	
	}else (X > T->Element){
		T->Right = Insert(X, T->Right);	
	}

	return T;
}

二叉查找树的删除例程

SearchTree Delete(ElementType X, SearchTree T)
{
	Position TmpCell;

	if(T == NULL){
		fprintf(stderr,"Element not found.\n");	
		return NULL;
	}else if(X < T->Element)
		T->Left = Delete(X, T->Left);
	else if(X > T->Element)
		T->Right = Dlelte(X, T->Right);
	else if(T->Left && T->Right){
		TmpCell = FindMin(T->Right);	
		T->Element = TmpCell->Element;
		T->Right = Delete(T->Element, T->Right);
	}else{
		TmpCell = T;
		if(T->Left == NULL)	
			T = T->Right;
		else if(T->Right == NULL)
			T = T->Left;
		free(TmpCell);
	}

	return T;
}



联系
我们