之前的博客中提到过,我学习采用的参考书是《数据结构与算法分析——C语言描述》。这门书的组织安排与国内广泛实用的教材《数据结构——C语言版》比较不同。这本书描述了一些树和二叉树的概念,举例讲解了什么是树的三种遍历之后,就开始重点讲解二叉查找树、平衡二叉树、AVL树、伸展树、B数了。这一篇博客,重点学习二叉查找树的概念和基本操作。
大家都知道,树的定义本身就带有递归性。因此,树的很多操作都涉及到了递归。
二叉查找树的定义如下:
1.二叉查找树首先是一棵二叉树;
2.二叉查找树除了是二叉树外,还具有以下性质:对于树中的任何一个节点X,其左子树中的所有节点的关键字均小于X的关键字的值;而其右子树中的所有关键字的值均大于X的关键字的值。下面两棵二叉树中,左边的二叉树是二叉查找树而右边的不是。
二叉查找树的数据结构定义如下:
typedef int ElementType;
typedef struct TreeNode *Position;
typedef Position BiSearchTree;
struct TreeNode
{
ElementType Element;
BiSearchTree Left,Right;
};
二叉查找树的常用操作如下:
BiSearchTree MakeEmpty(BiSearchTree Tree);
Position Find(ElementType X, BiSearchTree T);
Position FindMin(BiSearchTree T);
Position FindMax(BiSearchTree T);
BiSearchTree Insert(ElementType X,BiSearchTree T);
BiSearchTree Delete(ElementType X, BiSearchTree T);
二叉排序树的操作与之前学习的一些数据结构的操作相比,可能难理解一些。下面我们挑比较难的几个一一讲解。
1.二叉查找树中查找指定的元素Find
二叉排序树的性质是二叉排序树很多操作的基本依据。既然要查找指定元素X,先比较X与根节点元素的关系,如果刚好相等,直接返回啦;如果X小于根节点的元素值,那么去根节点的左子树中查找,也就是调用Find方法,只是传递的参数是X和根节点的左子树;如果X大于根节点的元素值,那么去根节点的右子树中查找,也就是调用Find函数,只是传递的参数是X和根节点的右子树。
2.查找最小元素FindMin和最大元素FindMax
这两个操作是类似的。采用迭代或者递归都可以实现,查找最小元素只需要沿着左子树访问下去,查找最大元素则相反。下面我们会分别采用递归和迭代实现这两个操作。
3.插入操作Insert
插入操作其实类似于查找操作,插入过过程其实就是先得找到一个合适的位置。插入其实有下面几个情况:
(1)如果函数传进来的是空树,那么创建一棵树,将其元素值设置为X。这种情况显而易见;
(2)如果不是空树,那就比较根节点元素值和X的大小,如果X的值小于根节点的元素值,而此时的根节点的左子树为空,那么根节点的左孩子就是X元素的归宿啦;同样的道理,如果X的值大于根节点的元素值,而此时根节点的右子树为空,那么根节点的右孩子就是X元素的归宿啦。把握住这一点其实基本上就能把握住这个操作了。文字描述可能比较抽象,下面看图:
左边的图,如果要插入5,沿着树一直找到节点4,这时5>4并且4的右孩子为空,那么5就是4的右孩子。右边的图,要想插入8,沿着树找到9,发现8<9且9的左孩子为空,那么8就是9的左孩子。
当然,在实现这样一个过程的时候可以使用递归。
4.删除操作Delete
删除操作是我认为最复杂最不好理解的一个操作。如果没有仔细想明白整个过程,上来就看代码的话可能会很晕。删除操作分两步:第一步是查找,找的过程就涉及元素值之间的比较。我们重点说找到之后的操作。假设我们找到了这个节点,现在要删除,涉及三种情况:
(1)该节点是叶子。这还有什么好说的,直接删了一了百了;
(2)该节点只有一个孩子节点。也不复杂,让该节点的父节点直接指向其子节点就行了。当然,也别忘了回收该节点;
(3)该节点有两个孩子:找到该节点右子树中最小的节点,将其元素值赋给该节点,然后删除那个最小节点。这种情况看图:
说了半天了,下面看看完整的代码:
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct TreeNode *Position;
typedef Position BiSearchTree;
struct TreeNode
{
ElementType Element;
BiSearchTree Left,Right;
};
//建立一颗空树
BiSearchTree MakeEmpty(BiSearchTree Tree)
{
if(!Tree)
{
MakeEmpty(Tree->Left);
MakeEmpty(Tree->Right);
free(Tree);
}
return NULL;
}
//二叉查找树的Find操作
Position Find(ElementType X, BiSearchTree 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;
}
}
}
//查找最小值:递归写法
Position FindMin(BiSearchTree T)
{
if(T == NULL)
{
return NULL;
}
else
{
if(T->Left == NULL)
{
return T;
}else
{
return FindMin(T->Left);
}
}
}
//查找最大值:非递归写法
Position FindMax(BiSearchTree T)
{
if(T->Right != NULL)
{
while(T->Right != NULL)
{
T = T->Right;
}
}
return T;
}
//插入元素X
BiSearchTree Insert(ElementType X,BiSearchTree T)
{
//当树为空树时
if(T == NULL)
{
T = malloc(sizeof(struct TreeNode));
if(T == NULL)
{
fprintf(stderr,"Out of Space!!!");
}
else
{
T->Element = X;
T->Left = NULL;
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
{
//do nothing!
}
}
return T;
}
//删除节点X
BiSearchTree Delete(ElementType X, BiSearchTree T)
{
Position TmpCell;
if(T==NULL)
{
fprintf(stderr,"Element does not exist!");
}
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)
{
BiSearchTree T;
int index;
int arr[10] = {10,9,8,7,6,1,2,3,4,5};
T = NULL;
for(index=0; index < 10; index++)
{
T = Insert(arr[index],T);
}
T = Insert(18,T);
T = Insert(15,T);
printf("The minimum element is %d\n",FindMin(T)->Element);
printf("The maxmium element is %d\n",FindMax(T)->Element);
return 0;
}
分享到:
相关推荐
数据结构——二叉查找树(BST)静态查找表,使用数据结构实现BST
实验内容:建立有n个元素的二叉排序树,并在其上进行查找。 实验说明:(1)建立n个元素的二叉树,以链式结构存储,数据元素为整型。(2)在该二叉树上查找某数据,若查找成功则输出成功信息,若查找失败,则插入该数据...
界面操作二叉树的查找,并可观察结果。是桌面程序
折半查找、二叉排序树的建立、查找与删除、链式哈希表的建立与查找: ...4————二叉排序树查找—— 5————二叉排序树删除—— 6————查找关键字(线性探测) 7————查找散列表(链式)
作者给出了一种新的二叉查找树———红黑树的定义和建树方法,并给出了它在最坏情况下的查找效率估计。
一、实验目的 1、掌握查找的不同方法,并能用高级语言实现查找算法。 2、熟练掌握顺序表的查找方法和有序顺序表的...3、掌握二叉排序树的生成、插入、删除、输出运算。 二、实验内容 1、有序顺序表的二分查找的递归算法
本代码是在windows平台下vs2008上编译通过,包含搜索二叉树的插入,查找和删除算法(采用递归和非递归两种方法)。包含全部在平台下的文件,解压可以直接运行。
c++实现:动态查找——二叉排序树及查找,哈夫曼树与哈夫曼编码,栈的应用——括号匹配检验,含数据结构课程设计报告和截图
2、 二叉查找树法:将每一个数插入到一棵树中,这棵树是二叉查找树。 用二叉查找树的方法对n个数进行排序,就是将这n个元素建立成一棵二叉查找树,再用中序遍历的函数遍历二叉树,就是对这些数的排序。建立一棵n个...
包括顺序查找、二分查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。
编写顺序查找、二分查找程序(二选一);编写建立二叉排序树的程序;编写在二叉排序树上的查找、插入、删除结点的程序;编写二叉排序树中序输出的程序
我们之前所学到的列表,栈等都是一种线性的数据结构,今天我们将学习计算机中经常用到的一种非线性的数据结构——树(Tree),由于其存储的所有元素之间具有明显的层次特性,因此常被用来存储具有层级关系的数据,...
关于二叉搜索树(也称为二叉查找树)可以参考:数据结构与算法——二叉查找树类的C++实现 AVL-tree是一个加上了额外平衡条件的二叉搜索树,其平衡条件的建立是为了确保整棵树的深度为O(logN)。要求任何节点的...
第一节、B树、B+树、B*树 1.前言: ...这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发,自然就想到平衡多路查找树结构,也就是这篇文章所要阐述的第一个主题B~tree(B树结构)。
当年我做的数据结构课内大实验——动态查找表,实现了 二叉排序树 平衡二叉树 B_树 2-3树 B+树
第12章为读者介绍另一种经典数据结构——二叉树。二叉查找树作为二叉树的特殊类型将是本章的主要内容。其他二叉树类型在第15章进行介绍。 第13章向读者说明在集合中存储数据的方法。这种方法在数据结构只存储唯一...
树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 平均情形分析...
如何描述一种新的抽象数据类型? 如何分析算法的优劣? 线性表的主要特征。 线性表的存储表示(顺序表示、单向链表、循环...静态查找表、二叉排序树、哈希函数的构造及冲突处理方法。 插入排序、快速排序、选择排序
第二天 平衡二叉树 6天通吃树结构—— 第一天 二叉查找树 算法速成系列(15)算法系列15天速成——第十五天 图【下】(大结局) 算法系列15天速成——第十四天 图【上】 算法系列15天速成——第十三天 树操作【下】 ...