本文共 2684 字，大约阅读时间需要 8 分钟。
这个学期本是想着好好把数据结构过一遍，以为看完了就基本可以刷LeetCode，唉，后来发现自己的进度太慢了，现在学的一知半解，在树和图那两节的基本数据结构和算法都没有亲自实现，虽然大体内容都看懂了，但是自己实际写代码确实头疼，暂时就先把后面比较容易实现的算法先写完。
这次实现的数据结构是二叉排序树，是非常常用的数据结构了。查找这一章比较重要的就是二分查找了，二分查找的算法函数替我也写过，如下：
#include#include /*二分查找算法*/int binarySearch(int *array,int arraySize,int val){ int low=0,high=arraySize,mid; if(arraySize<=0) return -1; while(low<=high){ mid=(low+high)/2; if(val==array[mid]) return mid; if(val>array[mid]) low=mid+1; if(val
其实二分查找理解起来不难，和我们日常猜数游戏过程很像，这种算法的时间复杂度是O(log2N)，但是基于线性数据结构的二分查找实现简单，进行删除和插入操作却很难，而且输入的数据必须按顺序，不然无法查找，所以就引入了二叉排序树，这种非常有用的数据结构。
/*C语言实现二叉排序树的基本操作*/#include#include #include #define TRUE 1#define FALSE 0/*二叉树的结构*/typedef struct BiTNode{ int data;struct BiTNode *lchird,*rchild;}BiTNode,*BiTree;/*递归查找二叉排序树T否存在值key*/int SearchBST(BiTree T,int key,BiTree f,BiTree *p){ if(!T){ *p=f; return FALSE;//查找不成功的情况 } else if(key==T->data){ *p=T; return TRUE;//查找成功的情况 } else if(key data){ return SearchBST(T->lchird,key,T,p);//在左子树里继续寻找 } else return SearchBST(T->rchild,key,T,p);//在右子树里继续寻找}/*二叉排序树的插入操作*/void InsertBST(BiTree *T,int key){ BiTree p,s;if(!SearchBST(*T,key,NULL,&p)){ //二叉排序树里没有key这个元素s=(BiTree)malloc(sizeof(BiTNode));s->data=key;s->lchird=s->rchild=NULL;if(!p) *T=s;//插入s为根节点else if(key data) p->lchird=s;//插入s为左孩子else p->rchild=s;//插入s为右孩子}}void Delete(BiTree *p){ BiTree q,s; if((*p)->rchild==NULL){ //右子树为空只需重新连接它的左子树 q=*p; *p=(*p)->lchird; free(q); } else if((*p)->lchird==NULL){ //左子树为空连接它的右子树 q=*p; *p=(*p)->rchild; free(q); } else{ /* 左右子树均不为空，有两种解决方案 1、 以待删节点的前趋值(左子树中最大的节点)替换之，然后再删除前趋节点 2、 以待删节点的后继值(右子树中最小的节点)替换之，然后再删除后继节点 */ q=*p; s=(*p)->lchird; while(s->rchild){ //找到右子树最大的节点值 q=s; s=s->rchild; } (*p)->data=s->data;//值替换 if(q!=*p) q->rchild=s->lchird;//重接q的右子树 else q->lchird=s->lchird;//重接q的左子树 free(s); }}void DeleteBST(BiTree *T,int key){ if(!*T) return; else{ if(key==(*T)->data) Delete(T); else if(key<(*T)->data) DeleteBST(&(*T)->lchird,key); else DeleteBST(&(*T)->rchild,key); }}/*二叉树的中序遍历*/void InorderTraverse(BiTree T){ if(NULL==T) return ; InorderTraverse(T->lchird); printf("%d ",T->data); InorderTraverse(T->rchild);}int main(){ BiTree T=NULL; int array[10]={ 62,88,58,47,35,73,51,99,37,93}; printf("二叉排序树的序列为： "); for(int i=0;i<10;i++) InsertBST(&T,array[i]); InorderTraverse(T); printf("\n"); printf("\n"); DeleteBST(&T,99); printf("删除元素99后的二叉排序树的序列为: "); InorderTraverse(T); system("pause"); return 0;}
仔细看这一节，就二叉排序树的删除操作有点细节，它的查找插入和删除操作都是递归实现的，看起来简单，但实际自己写就有点绕。总体来说难度不大，hhh，还是想对自己说：持之以恒
转载地址：http://dstki.baihongyu.com/