`
hojor
  • 浏览: 109196 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

查找树ADT-二叉查找树

 
阅读更多
/////////////////////////////// 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;
}

 

分享到:
评论

相关推荐

    数据结构实验报告-二叉排序树.pdf

    在给定的实验报告中,提到了二叉排序树的抽象数据类型(ADT)定义,包括以下几个基本操作: 1. `InitBST(&T)`:初始化一个空的二叉排序树。这个操作通常用于创建一个新的二叉排序树,使其根节点为空。 2. `...

    浙江大学《数据结构》课程学习笔记与练习题

    Lecture 3.3 - 查找树 ADT(二叉查找树) Lecture 3.4 - AVL树 第四章:优先队列(堆) Lecture 4.1 - 堆 Lecture 4.2 - 哈夫曼树与哈夫曼编码 Lecture 4.3 - 不相交集 ADT 第五章:图论算法 第六章:排序

    查找树 ADT

    在这个实验报告中,我们关注的是抽象数据类型(ADT)的查找树,特别是二叉排序树(Binary Search Tree,BST)。二叉排序树是一种特殊的二叉树,其中每个节点的值大于其左子树中的所有节点值,小于其右子树中的所有...

    数据结构与算法分析_Java_语言描述

    表达式树 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 一个简单的想法...

    数据结构与算法第5章.ppt

    本资源摘要信息涵盖了数据结构与算法的第五章的主要内容,涵盖了集合及其实现、静态查找、哈希表、二叉查找树、平衡二叉查找树(AVL树)、B树与B+树等知识点。 1. 集合及其实现 集合是数据结构和算法设计中用到的...

    数据结构JAVA

    - 二叉查找树的插入与删除 - 二叉查找树的平衡问题 - **AVL树** - AVL 树的概念 - AVL 树的旋转操作 - AVL 树的插入与删除 - **B-树** - B-树的概念 - B-树的结构特点 - B-树的插入与删除 **8.4 哈希** ...

    最终报告4-201708020305-杨兰馨1

    《二叉查找树在静态查找表中的应用》 二叉查找树(Binary Search Tree,BST),作为一种特殊的数据结构,广泛应用于计算机科学中的数据管理。它是一种二叉树,其中每个节点包含一个键(key)、一个关联的值、一个...

    清华大学出版社《数据结构(C语言版)》部分结构与算法C语言实现源码

    API接口定义与使用方法请参考书中每一章的ADT List,源码可以使用DEVC++直接编译运行。 实现内容: ...第九章 - 哈希表、折半查找、B-树、二叉平衡树 第十章 - 堆排序、归并排序、排序(书中所有排序)

    山东大学《数据结构》实验指导06查找或检索.docx

    数据结构是计算机科学中的...总之,这份实验指导书涵盖了数据结构中的基本概念,包括表的管理和不同的查找算法,以及二叉搜索树的相关操作。通过实际操作这些内容,学生可以深入理解数据结构的原理,并提升编程技能。

    数据结构动态查找表

    2. 树结构:例如二叉查找树(Binary Search Tree)、平衡树(AVL树、红黑树等),它们通过特定的规则保证了查找效率,通常可以在O(log n)的时间复杂度内完成查找。 3. 散列表(Hash Table):散列表通过哈希函数将...

    基于AVL树表示的集合ADT实现与应用1

    AVL树是一种特殊的二叉搜索树,其特点是每个节点的左右子树高度差不超过1,从而保证了树的平衡,提高了查找效率。 1. AVL树的基本概念 AVL树是由G.M. Adelson-Velsky和E.M. Landis于1962年提出的,名字取自他们的...

    数据结构练习题.doc

    - 二叉排序树的形态取决于插入元素的顺序,有多种可能。 - 先序和中序遍历相同,可能表明树只有一个根节点,但不是必然的。 - 二叉链表中的空指针域总数等于节点数加一。 - 哈夫曼树的节点总数与叶子节点的权值有关...

    C++数据抽象和问题求解(第6版).[美]Frank M. Carrano(带详细书签).pdf

    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 ...

    数据结构与算法知识点总结(5)查找树.doc

    查找树是一种自平衡的二叉搜索树,允许在对数时间内执行查找、插入和删除操作。本文将主要讨论基础查找方法以及基于二分查找的有序符号表的实现。 首先,符号表(Symbol Table)是一个抽象数据类型(ADT),它存储...

    数据结构与算法(java版)

    - B-树是一种平衡多路搜索树。 - **哈希** - 哈希表是一种高效的数据结构,用于根据键快速查找数据。 - 哈希函数用于将键映射到哈希表的位置。 - 解决冲突的方法包括开放寻址法和链地址法。 #### 排序 - **...

    数据结构复习重点

    - 二叉查找树、平衡树(AVL、红黑树)等高级话题。 7. 图: - 图的基本概念,如顶点、边、邻接矩阵、邻接表。 - 图的遍历(深度优先搜索DFS和广度优先搜索BFS),最短路径算法(Dijkstra、Floyd-Warshall)。 8...

    数据结构课程设计AVL树实现及其分析实验报告.pdf

    AVL树是一种自平衡二叉查找树,由G. M. Adelson-Velsky和E. M. Landis于1962年提出,因此得名AVL树。它的主要特性是任何节点的两个子树的高度差不超过1,这使得AVL树在插入和删除操作后能够快速恢复平衡,从而保证了...

    《数据结构与算法》教学大纲.pdf

    - 二叉排序树提供动态查找,B-树适合大型数据存储。 - 哈希冲突解决策略如线性探测和链地址法有助于提高查找效率。 课程考核结合平时成绩、实践成绩和期末考试,强调理论与实践相结合,鼓励学生运用合适的数据...

    chc52232024-coursework2v11.pdf

    - 必须实现 `IMemberDB` 接口作为一个二叉查找树。 - 不得修改接口。 #### 基本规则 - 完成所有任务后创建一个可执行项目。 - 每个 Java 类应该定义在一个 `.java` 文件中。 - 在报告中展示每个类的源代码。 ### ...

Global site tag (gtag.js) - Google Analytics