/////////////////////////////// tree.h /////////////////////////////////
#ifndef _TREE_H_
#define _TREE_H_
#define ElementType int
struct TreeNode;
typedef struct TreeNode * Position;
typedef struct TreeNode * SearchTree;
SearchTree MakeEmpty(SearchTree t);
Position Find(ElementType x,SearchTree t);
Position FindMin(SearchTree t);
Position FindMax(SearchTree t);
Position Insert(ElementType x,SearchTree t);
Position Delete(ElementType x,SearchTree t);
ElementType Retrieve(Position p);
#endif
struct TreeNode {
ElementType Element;
SearchTree Left;
SearchTree Right;
};
//////////////////////////////////////////////////////////////////////////
#include "tree.h"
#include <stdio.h>
#include <stdlib.h>
//建立一棵空树的例程
SearchTree MakeEmpty(SearchTree t)
{
if (t != NULL)
{
MakeEmpty(t->Left);
MakeEmpty(t->Right);
free(t);
}
return NULL;
}
//先序遍历
void Preorder_TreePrint(SearchTree t)
{
if(t!=NULL)
{
printf("%d ",t->Element);
Preorder_TreePrint(t->Left);
Preorder_TreePrint(t->Right);
}
}
//中序遍历
void Inorder_TreePrint(SearchTree t)
{
if(t!=NULL)
{
Inorder_TreePrint(t->Left);
printf("%d ",t->Element);
Inorder_TreePrint(t->Right);
}
}
//后续遍历
void Postorder_TreePrint(SearchTree t)
{
if(t!=NULL)
{
Postorder_TreePrint(t->Left);
Postorder_TreePrint(t->Right);
printf("%d ",t->Element);
}
}
//查找元素
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);
}
else
return t;
}
//查找最小值
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;
}
//插入元素
SearchTree Insert(ElementType x,SearchTree t)
{
if (t == NULL)
{
t = (SearchTree)malloc(sizeof(struct TreeNode));
if (t == NULL)
{
printf("Out of space!!\n");
}
else
{
t->Element = x;
t->Left = t->Right = NULL;
}
}
else if (x < t->Element)
{
t->Left = Insert(x,t->Left);
}
else
{
t->Right = Insert(x,t->Right);
}
return t;
}
//删除元素
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(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;
}
//////////////////////////////////////////////////////////////////////////
int main(void)
{
int i = 0;
SearchTree st = NULL;
Position min = NULL;
Position max = NULL;
for(i=0;i<20;i++)
{
st = Insert(i,st);
}
Inorder_TreePrint(st);
min = FindMin(st);
max = FindMax(st);
printf("min=%d max=%d\n",min->Element,max->Element);
return 0;
}
分享到:
相关推荐
表达式树 4.3 查找树ADT-二叉查找树 4.3.1 find 4.3.2 findMin和findMax 4.3.3 insert 4.3.4 remove 4.3.5 平均情形分析 4.4 AVL树 4.4.1 单旋转 4.4.2 双旋转 4.5 伸展树 4.5.1 一个简单的想法...
API接口定义与使用方法请参考书中每一章的ADT List,源码可以使用DEVC++直接编译运行。 实现内容: ...第九章 - 哈希表、折半查找、B-树、二叉平衡树 第十章 - 堆排序、归并排序、排序(书中所有排序)
16.3 ADT二叉查找树基于链表的实现 458 16.3.1 ADT二叉查找树操作的算法 458 16.3.2 BinarySearchTree类 469 16.4 在文件中保存二叉查找树 471 16.5 树排序 474 16.6 一般树 474 C++片段6 迭代器 479 C6.1 ...
二叉搜索树操作: 插入 插入列表 寻找 删除 遍历BFS 遍历DFS前序 遍历DFSinorder 遍历DFS后序 复制树 找最小值 查找最大值 类型: 迭代(使用 Queue(head ptr) 和 Stack 进行遍历) 递归(继承自迭代方法,重新实现 ...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 表达式树4.3 查找树ADT——二叉查找树4.3.1 MakeEmpty4.3.2 Find4.3.3 FindMin和FindMax4.3.4 Insert4.3.5 Delete4.3.6 平均情形分析...
我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈希表。在这一节中,我们将要学习二叉搜索树,这是另一种键指向值的Map集合,在这种情况下我们不用考虑元素在树中的实际位置,但要知道使用二叉树来搜索更有效...
32_二叉查找树 33_AVL树的python实现 34_python实现ADT Graph 35_词梯WordLadder问题 36_BFS和DFS实现 37_图的应用-骑士周游问题 38_图的应用-拓扑排序 39_图的应用-强连通分支Kosaraju 40_图的应用-最短路径问题 41...
表达式树 4.3 查找树adt——二叉查找树 4.3.1 contains方法 4.3.2 findmin方法和findmax方法 4.3.3 insert方法 4.3.4 remove方法 4.3.5 平均情况分析 4.4 avl树 4.4.1 单旋转 4.4.2 双旋转 4.5...
表达式树 4.3 查找树adt——二叉查找树 4.3.1 contains方法 4.3.2 findmin方法和findmax方法 4.3.3 insert方法 4.3.4 remove方法 4.3.5 平均情况分析 4.4 avl树 4.4.1 单旋转 4.4.2 双旋转 4.5...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
4.3 查找树ADT——二叉查找树 4.3.1 contains 4.3.2 findMin和findMax 4.3.3 insert 4.3.4 remove 4.3.5 析构函数和复制赋值操作符 4.3.6 平均情况分析 4.4 AVL树 4.4.1...
4.3 查找树ADT——二叉查找树 4.3.1 contains 4.3.2 findMin和findMax 4.3.3 insert 4.3.4 remove 4.3.5 析构函数和复制赋值操作符 4.3.6 平均情况分析 4.4 AVL树 ...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
4.3 查找树ADT——二叉查找树 4.3.1 contains方法 4.3.2 findMin方法和findMax方法 4.3.3 insert方法 4.3.4 remove方法 4.3.5 平均情况分析 4.4 AVL树 4.4.1 单旋转 4.4.2 双旋转 4.5 伸展树 4.5.1 一个简单的想法...
华中科技大学数据结构课设,内容为设计基于AVL树表示的集合ADT实现与应用(1)以二叉链表为存储结构,设计与实现AVL树-动态查找表及其6种基本运算;(2)以AVL树表示集合,实现集合抽象数据类型及其10种基本运算;...
课程的目录结构如下,每一章都有配套的文字讲义(markdown),示例代码,视频讲解,...二叉查找树 图与图的遍历 python 内置常用数据结构和算法的使用。list, dict, set, collections 模块,heapq 模块 面试笔试常考算法
8.3.2 B-树和B+树 8.4 哈希表及其查找 8.4.1 哈希表与哈希函数 8.4.2 构造哈希函数的常用方法 8.4.3 解决冲突的主要方法 8.5 哈希表算法实现C语言源程序 习题八 第9章 排序 9.1 排序基本概念 9.2 插入排序 ...