二叉查找树ADT--C语言描述
2024-08-28 19:21:32
首先给出此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;
}
最新文章
- JQuery ajax 异步传一个数组到 .net后台
- [原] JsTree.js
- 图论 公约数 找环和链 BZOJ [NOI2008 假面舞会]
- 【云计算】Docker云平台—Docker基础
- hadoop的kerberos认证
- IOS开发: 为UIImageView添加点击事件
- stringgird中使用TClientDataSet排序的问题
- Gradle学习目录总结
- maya和Unity中的坐标系旋转
- 简单CSS定位瀑布流实现方法
- [Python]How to handle the exception in Python?
- UVa 481 - What Goes Up
- wc 命令详解
- 《程序设计入门——C语言》翁恺老师 第一周编程练习记录
- mybatis 映射生成mapper和pojo ---逆向工程的使用过程
- PHP与Excel 笔记
- node.js之十大Web框架
- NowCoder Wannafly 27E 黄魔法师 构造
- js判断字符串是否在数组中
- 基于区域的OSPF的MD5认证