数据结构——二叉搜索树（BST）

二叉排序树首先是二叉树1.BST的定义1空树也是二叉搜索树2若二叉搜索树的左子树不为空则其左子树的所有节点中关键值都小于其根节点的关键值3若二叉搜索树的右子树不为空则其右子树的所有节点中关键值都小于其根节点的关键值4二叉搜索树的子树也是二叉树5二叉搜索的关键值互不相同如果要进行中序遍历一定是递增的如果用链式结构来实现二叉搜索树他既有链表的插入和删除的高效率并且还拥有快速查找的优点。应用十分广泛文件系统和数据库里面都会用这种结构进行排序和检索有效节点定义1需要一个变量来存关键值2需要两个指针指向他的两个左右孩子3需要一个指针来指向孩子节点的双亲指针可以不需要4计数器一般情况下二叉搜索树中的关键值是不可以重复的但是如果重复了可以用计数器来统计但一般情况下是不需要的辅助节点定义1用一个指针来存储有效节点的根节点所需的函数接口#pragma once typedef int ELEMTYPE; //有效节点结构体定义 typedef struct BstNode { ELEMTYPE data;//数据域 struct BstNode* leftchild;//左孩子指针 struct BstNode* rightchild;//右孩子指针 struct BstNode* parent;//双亲指针 }SBstNode,*PBstNde; //辅助节点结构体定义 typedef struct BSTree { struct BstNode* root; }; //要实现的函数 //1.初始化 void Init_BSTree(BSTree* pTree); //2.查找 BstNode* Search_BST(BSTree* pTree, ELEMTYPE val); BstNode* Search_BST1(BSTree* pTree, ELEMTYPE val); //3.打印 void Show_InOder(BstNode* root); void Show_InOfer2(BstNode* root); //4.插入 bool Insert_BST(BSTree* pTree, ELEMTYPE val); //5.删除 bool Delete_BST(BSTree* pTree, ELEMTYPE val); bool Delete_BST2(BSTree* pTree, ELEMTYPE val); bool Delete_BST_F(BSTree* pTree, ELEMTYPE val); //6.购买新节点 BstNode* BuyNode();所需标头#define _CRT_SECURE_NO_WARNINGS #include stdio.h #include stdlib.h #include string.h #include assert.h #include memory.h #include stack #include queue #includeBSTree.h函数实现1.初始化默认为空树//1.初始化 void Init_BSTree(BSTree* pTree) { assert(pTree ! NULL); pTree-root NULL; }2.查找逻辑1.从根节点出发如果当前节点存在的话2.用当前节点的关键字和我需要找的值进行比较3.如果等于我需要的值则找到直接结束如果大于我需要的值则走其左子树如果小于我需要的值则走其右子树当遇到空节点则直接结束查找的值不在简单逻辑BstNode* Search_BST(BSTree* pTree, ELEMTYPE val) { //0.assert assert(pTree ! NULL); //1.申请一个指针用来指向根节点 BstNode* p pTree-root; //2.进入while循环循环条件就是当前p指向的节点存在 while (p!NULL) { //3.判断当前P指向的节点的关键值和我要查找的val 值进行比较 //4.如果相等-》则找到了 if (p-data val) { return p; } //5.如果我查找的val值p指向的节点关键值则让p走起自身左子树 else if (val p-data) { p p-leftchild; } //6.如果我查找的val值p指向的节点关键值则让p走起自身右子树 else { p p-rightchild; } } //7.当while循环结束则认为p遇到了空节点-则没找到 return }3.打印递归//3.打印(中序遍历 void Show_InOder(BstNode* root) { if (root NULL) { return; } //递归 Show_InOder(root-leftchild); printf(%d , root-data); Show_InOder(root-rightchild); }非递归//3.打印 中序遍历 非递归 void Show_InOfer2(BstNode* root) { assert(root ! NULL); //非递归 std::stackBstNode*st; //将根节点入栈 st.push(root); bool tag true; while (!st.empty()) { while (st.top()-leftchild ! NULLtag) { st.push(st.top()-leftchild); } BstNode* tmp st.top(); st.pop(); printf(%d , tmp-data); if (tmp-rightchild ! NULL) { st.push(tmp-rightchild); tag true; } else { tag false; } } }购买新节点BstNode* BuyNode() { BstNode* pnewnode (BstNode*)malloc(sizeof(BstNode)); if (pnewnode NULL) { exit(EXIT_FAILURE); } return pnewnode; }BST的插入1如果要插入的值在这个二叉搜索树中已经有了就不用在插了默认二叉搜索树中不可以有重复值search函数找到了81则不用再插了2假如此时我们要插入值800.通过search函数调用接收返回值是一个空地址则确定80不存在1.购买一个新节点2.找到合适的插入位置找到插入哪一个节点的下面3.此时直接插入//4.插入 bool Insert_BST(BSTree* pTree, ELEMTYPE val) { //assert 确保辅助节点存在 assert(pTree ! NULL); //1.申请两个临时指针p和PP p用来遍历val值是否存在pp用来保存P的上家 BstNode* p pTree-root; BstNode* pp NULL; //2.让p进入while循环去跑循环条件p指向的节点存在 但是值不是我要的 while (p ! NULL p-data ! val) { if (val p-data) { pp p; p p-leftchild; } else { pp p; p p-rightchild; } } //3.while循环退出 此时 需要判断while循环因为 什么情况导致退出 //情况1.准备插入的val值不存在 //情况2准备插入的val值存在 //情况1准备插入的val值存在 直接返回 if (p ! NULL p-data val) { return true; } //如果val不在则购买新节点 准备插入 BstNode* pnewnode BuyNode(); pnewnode-data val; //防止一个是对一个空的BST树进行插入 if (pTree-root NULL) { pTree-root pnewnode; //pnewnode-parent NULL; return true; } //5.如果不是空的BST树 则正常对pp下面插入即可 pnewnode-parent pp; if (pnewnode-data pp-data) { pp-leftchild pnewnode; } else { pp-rightchild pnewnode; } }BST的删除1.如果待删除节点是0分支如果待删除节点没有一个孩子则直接让其父节点指向它的指针断开直接释放该节点即可。//5.删除 bool Delete_BST(BSTree* pTree, ELEMTYPE val) { assert(pTree ! NULL); // 1.如果待删除节点是0分支如果待删除节点没有一个孩子 // 则直接让其父节点指向它的指针断开直接释放该节点即可。 //只删除没有孩子节点的节点 也就是叶子节点 BstNode* p Search_BST(pTree,val); if (p NULL)//p不存在直接返回 return false; if (p-leftchild ! NULL||p-rightchild!NULL) {//如果存在左右孩子我不删 return false; } BstNode* pp p-parent; if (pp NULL) {//防止删除的是根节点 因为如果要删除根节点的话就要更新辅助节点的中的root值 pTree-root NULL; } //如果是叶子节点就要判断他是在他父节点的左边还是右边 再将链接断开 else { if (val pp-data) {//如果这个值比父节点的关键值还要小说明这个值在父节点的左边将左孩子的指针置为空 并释放左孩子节点 pp-leftchild NULL; } else {//如果不是左孩子字就是右孩子将父节点中右孩子指针域置为空并将这个右孩子的节点内存释放掉 pp-rightchild NULL; } } free(p); p NULL; return true; }如果待删除节点是可能是0分支有可能是1分支单分支处理策略让父节点抓住其孩子然后在释放孩子节点bool Delete_BST2(BSTree* pTree, ELEMTYPE val){//删除没有孩子节点的节点和只有一个节点的节点 assert(pTree ! NULL); BstNode* p Search_BST(pTree, val); if (p NULL)//p不存在直接返回 return false; if (p-leftchild ! NULL p-rightchild ! NULL) { return false; } BstNode* pp p-parent; //将这个待删除节点的孩子抽象出来 //并且如果孩子节点是空也作为其孩子节点 //先默认待删除节点的左孩子是存在的 BstNode* childp-leftchild; //如果右孩子不为空那么就意味着我们刚刚默认错误了将其孩子节点改正即可 if (p-rightchild ! NULL) {//说明是右孩子存在左孩子不存在 //更改child 中的值就好 child p-rightchild; } //如果待删除节点的父节点为空 // 此时待删除节点就是根节点 // 并且他有一个孩子节点 //更新辅助节点中的root值赋为待删除节点的孩子节点 不管孩子节点是有效节点还是空节点 if (pp NULL) {//说明删除的这个节点是根节点 //更改辅助节点中root中的值 pTree-root child; } //待删除节点的父节点存在 //并且其父节点的关键值大于待删除节点的值 //那么就意味着待删除节点在其父节点的左边 //将其父节点接收孩子节点 if (val pp-data) pp-leftchild child; else { //待删除节点的父节点存在 //并且其父节点的关键值小于待删除节点的值 //那么就意味着待删除节点在其父节点的右边 //将其父节点接收孩子节点 pp-rightchild child; } if (child ! NULL) { child-parent pp; } free(p); p NULL; return true; }如果待删除节点有可能是0分支有可能是1分支还有可能是2分支双分支处理策略狸猫换太子用待删除节点的直接前驱或者直接后继去代替待删除节点被删除具体策略1找到待删除节点确定是双分支2找到直接后继用cat 指向找其右子树的里面的最小值3将cat的关键值给P的关键值4这时把删除p转换为删除cat如果我们此时要删除53将这个二叉搜索树按照中序遍历进行打印结果为此时待删除节点53 的直接前驱就是45 直接后继就是65此时53的直接前驱就是其左子树的最大值 53的直接后继就是其右子树的最小值删除逻辑用p指向我们的待删除节点在给一个狸猫cat 指针指向待删除节点的直接后继将65拷贝一份 覆盖待删除节点中的53 此时就相当于53被删除了 在将这个狸猫cat节点释放掉代码实现//最终版 bool Delete_BST_F(BSTree* pTree, ELEMTYPE val) {//所有情况都能删 //0.assert assert(pTree ! NULL); if (pTree-root NULL) {//表示一个节点都没有 return false; } BstNode* p Search_BST(pTree, val); if (p NULL)//p不存在直接返回 return false; if (p-leftchild ! NULL p-rightchild ! NULL) { //狸猫换太子 //用直接后继 找其右子树的最小值 BstNode* cat p-rightchild; while (cat-leftchild) { cat cat-leftchild; } p-data cat-data; p cat;//让p等于cat 后期说是删除P节点其实就是删除cat 这个节点 } BstNode* pp p-parent; BstNode* child p-leftchild; if (p-rightchild ! NULL) {//说明是右孩子存在左孩子不存在 //更改child 中的值就好 child p-rightchild; } if (pp NULL) {//说明删除的这个节点是根节点 //更改辅助节点中root中的值 pTree-root child; } if (val pp-data) pp-leftchild child; else { pp-rightchild child; } if (child ! NULL) { child-parent pp; } free(p); p NULL; return true; }怎么找任意一个节点的直接前驱或者直接后继假设直接找后继如果当前节点右子树存在则直接找右子树中的最小值即可如果当前及节点的右子树不存在怎么找直接后继步骤1定义一个指针PP让其往上走回溯、2如果PP遇到了空地址触顶了说明p没有直接后继3如果pp没有遇到NULL则PP当前指向的节点存在则再去判断p在pp的左子树上还是右子树上4如果p在PP的右子树上则说明当前PP节点是无用的因为此时以PP为根节点的子树P就是最大值5如果P在PP的左子树上说明当前的PP节点是有用的PP的值是大于P的值则找到了//寻找当前节点的直接后继 BstNode* Get_Next(BstNode* node) { assert(node ! NULL); //1.简单情况node右子树存在 则直接找右子树中的最小值 if (node-rightchild ! NULL) { BstNode* p node-rightchild; while (p-leftchild ! NULL) { p p-leftchild; return p; } } //2.复杂情况node的右子树不存在 //定义一个pp 向上回溯 BstNode* pp node-parent; while (pp ! NULL) { if (node-data pp-data) { pp pp-parent; } else { return pp; } } ////while循环的优化 //while (pp ! NULL node-data pp-data) // pp pp-parent; //return NULL; //while循环退出 说明触顶 Node没有直接后继 return NULL; }找任意节点的直接前驱//寻找当前节点的直接前驱 BstNode* Get_Prior(BstNode* node) { assert(node ! NULL); //1.简单情况Node的左孩子存在 则直接找左子树中的最大值 if (node-leftchild ! NULL) { BstNode* p node-leftchild; while (p-rightchild ! NULL) { p p-rightchild; } return p; } //2.复杂情况Node的左孩子不存在 //定义一个pp向上回溯 BstNode* pp node-parent; while (pp ! NULL) { if (pp-data node-data) { pp pp-parent; } else { return pp; } } }