二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。该树属于一种输入数据就默认产生一种顺序的数据结构,这不像本章前面的内容所描述的静态的在某一个数据段内进行查找,动态查找是一种输入时就会自动对其进行排序的数据结构,前文学过的STL中的set集合其底层就是一个类似的树形结构红黑树。
二叉排序树有以下性值:
a) 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
b) 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
c) 左、右子树也分别为二叉排序树;
即对于每一个根结点,其左孩子永远小于根,右孩子永远大于根。
考虑如果树是空的,则查找结束,无匹配。如果被查找的值和根结点的值相等,查找成功。否则就在子树中继续查找。如果被查找的值小于根结点的值就选择左子树,大于根结点的值就选择右子树。
参考代码如下:
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ /* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode /* 结点结构 */ { int data; /* 结点数据 */ struct BiTNode *lchild, *rchild; /* 左右孩子指针 */ } BiTNode, *BiTree; /* 递归查找二叉排序树T中是否存在key, */ /* 指针f指向T的双亲,其初始调用值为NULL */ /* 若查找成功,则指针p指向该数据元素结点,并返回TRUE */ /* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */ Status 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 < t->data) return SearchBST(t->lchild, key, t, p); /* 在左子树中继续查找 */ else return SearchBST(t->rchild, key, t, p); /* 在右子树中继续查找 */ }
二叉排序的插入是建立在二叉排序的查找之上的,插入一个结点,就是通过查找发现该结点合适插入位置,把结点直接放进去。 其实在2.2节中一步步构造二叉排序树的过程中就是结点插入过程,并考虑查找的关键字已经有在树中,则指向该数据结点,若查找的关键字没有在树中,则指向查找路径上最后一个结点。
参考代码
struct BiTree { int data; BiTree *lchild; BiTree *rchild; }; //在二叉排序树中插入查找关键字key BiTree* InsertBST(BiTree *t,int key) { if (t == NULL) { t = new BiTree(); t->lchild = t->rchild = NULL; t->data = key; return t; } if (key < t->data) t->lchild = InsertBST(t->lchild, key); else t->rchild = InsertBST(t->rchild, key); return t; } //n个数据在数组d中,tree为二叉排序树根 BiTree* CreateBiTree(BiTree *tree, int d[], int n) { for (int i = 0; i < n; i++) tree = InsertBST(tree, d[i]); }
二叉树的删除可不再像二叉树的插入那么容易了,以为删除某个结点以后,会影响到树的其它部分的结构。
删除的时候需要考虑以下几种情况:
a)删除结点为叶子结点;
b)删除的结点只有左子树;
c)删除的结点只有右子树
d)删除的结点既有左子树又有右子树。
参考代码如下:
/* 若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点, */ /* 并返回TRUE;否则返回FALSE。 */ Status DeleteBST(BiTree *T,int key) { if(!*T) /* 不存在关键字等于key的数据元素 */ return FALSE; else { if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ return Delete(T); else if (key<(*T)->data) return DeleteBST(&(*T)->lchild,key); else return DeleteBST(&(*T)->rchild,key); } } /* 从二叉排序树中删除结点p,并重接它的左或右子树。 */ Status Delete(BiTree *p) { BiTree q,s; if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树(待删结点是叶子也走此分支) */ { q=*p; *p=(*p)->lchild; free(q); } else if((*p)->lchild==NULL) /* 只需重接它的右子树 */ { q=*p; *p=(*p)->rchild; free(q); } else /* 左右子树均不空 */ { q=*p; s=(*p)->lchild; while(s->rchild) /* 转左,然后向右到尽头(找待删结点的前驱) */ { q=s; s=s->rchild; } (*p)->data=s->data; /* s指向被删结点的直接前驱(将被删结点前驱的值取代被删结点的值) */ if(q!=*p) q->rchild=s->lchild; /* 重接q的右子树 */ else q->lchild=s->lchild; /* 重接q的左子树 */ free(s); } return TRUE; }
本文固定URL:https://www.dotcpp.com/course/157
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程