查找树ADT--二叉查找树
二叉树的一个重要应用是它们在查找中的使用。
二叉查找树的性质：对于树中的每个节点X，它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项。这意味着该树所有的元素可以用某种一致的方式排序。
二叉查找树的平均深度是O(logN)。二叉查找树要求所有的项都能够排序。树中的两项总可以使用Comparable接口中的compareTo方法比较。
ADT的声明：
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
SearchTree MakeEmpty(SearchTree T);
Position Find(ElementType X, SearchTree T);
Position FindMax(SearchTree T);
Position FindMin(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);
struct TreeNode{
ElementType Element;
SearchTree Left;
SearchTree Right;
};1、MakeEmpty的实现
SearchTree MakeEmpty(SearchTree T){
if(T != NULL){
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}2、Find的实现
Position Find(ElementType X, SearchTree T){
if(T == NULL)
return NULL;
else if(X < T->Element)
return Find(X, T->Left);
else if(X > T->Element)
return Find(X, T->Right);
else
return T;
}3、FindMax和FindMin的实现（一个递归 一个非递归）
Position FindMin(SearchTree T){
if(T == NULL)
return NULL;
else if(T->Left == NULL)
return T;
else
return FindMin(T->Left);
}
Position FindMax(SearchTree T){
if(T != NULL)
while(T->Right != NULL)
T = T->Right;
return T;
}4、Insert的实现
SearchTree Insert(ElementType X, SearchTree T){
if(T == NULL){
T = (SearchTree)malloc(sizeof(struct TreeNode));
T->Element = X;
T->Left = T->Right = NULL;
}
else if(X < T->Element)
T->Left = Insert(X, T->Left);
else if(X > T->Element)
T->Right = Insert(X, T->Right);
// Else X is in the tree already, we'll do nothing!
return T;
}5、Delete的实现
SearchTree Delete(ElementType X, SearchTree T){
Position TmpCell;
if(T == NULL)
printf("Element Not Found\n");
else if(X < T->Element)
T->Left = Delete(X, T->Left);
else if(X > T->Element)
T->Right = Delete(X, T->Right);
else if(T->Left && T->Right){
TmpCell = FindMin(T->Right);
T->Element = TmpCell->Element;
T->Right = Delete(TmpCell->Element, T->Right);
}
else{
TmpCell = T;
if(!(T->Left))
T = T->Right;
else if(!(T->Right))
T = T->Left;
free(TmpCell);
}
return T;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-08-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录