网站加ico,实用又有创意的设计,建网站pc版,中国网站备案查询系统之前的博客中提到过#xff0c;我学习采用的参考书是《数据结构与算法分析——C语言描述》。这门书的组织安排与国内广泛实用的教材《数据结构——C语言版》比较不同。这本书描述了一些树和二叉树的概念#xff0c;举例讲解了什么是树的三种遍历之后#xff0c;就开始重点讲… 之前的博客中提到过我学习采用的参考书是《数据结构与算法分析——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这时54并且4的右孩子为空那么5就是4的右孩子。右边的图要想插入8沿着树找到9发现89且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(TNULL) { 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(index0; 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; } 转载于:https://blog.51cto.com/wawlian/722244
