网站怎么做订单,wordpress 后台添加广告位置,精准营销的案例,html模板语法数据结构#xff1a;二叉查找树 二叉查找树 基础知识 关于二叉树的基础知识#xff0c;请看我的一篇博客:二叉树的链式存储 二叉查找树的特征 二叉查找树或者是一棵空树#xff0c;或者是具有下列性质的二叉树#xff1a; 1.若其左子树不空#xff0c;则左子树上所有结…数据结构二叉查找树 二叉查找树 基础知识 关于二叉树的基础知识请看我的一篇博客:二叉树的链式存储 二叉查找树的特征 二叉查找树或者是一棵空树或者是具有下列性质的二叉树 1.若其左子树不空则左子树上所有结点的值均小于它的根结点的值 2.若其右子树不空则右子树上所有结点的值均大于它的根结点的值; 3.其左、右子树也分别为二叉排序树 二叉查找树的建立 反复插入节点所构造出来的若二叉树为空树则插入元素作为树根节点。若根结点的键值等于key则插入失败若key小于根结点的键值则插入到根的左子树上否则插入到根的右子树上新插入的节点一定是一个叶子节点 代码分析 void InsertBST(BiStree Tree,ElemType e)
{BiStree T Tree; //定义执行副本BiStree father NULL; //定义while (TT-data.key!e.key){fatherT;if(e.keyT-data.key)TT-Rchild;elseTT-Lchild;}if(T) //跳出循环的只有两种情况要么就是T不存在要么就是找到了对应元素T 存在说明只能是对应元素也存在那我我们就不用插入了return;BiSnode *s (BiSnode*)malloc(sizeof(BiSnode));//能到这里说明节点不存在新建一个节点并初始化s-datae;s-Rchilds-LchildNULL;if(fatherNULL) //如果farther不存在那说明就是没有执行While语句也即是树是空的因为一旦执行就不会为NULLTrees;else if(e.keyfather-data.key) //到这里说明Farther存在,那么剩下的就是往farther左右节点插入元素了father-Rchilds;elsefather-Lchilds;
}删除运算 删除运算是的基础是查找元素首先要查找要删除的元素如果找到就删除找不到就不用删除了。 查找代码 void DelBST(BiStree Tree,char key)
{if(!Tree) //如果节点为空节点说明要删除的元素不可能存在所以返回就好return;else //下面是节点存在的分情况判断{if(Tree-data.keykey) //如果找到了要删除的节点{deleteNode(Tree); //删除该节点}else if(Tree-data.keykey) //如果要删除的节点大于该节点则往该节点的右子树方向进行查找DelBST(Tree-Rchild,key);elseDelBST(Tree-Lchild,key);//如果要删除的节点小于该节点则往该节点的左子树方向进行查找}
} 到现在我们已经找到元素了 要对其删除就是要实现deleteNode(Tree);方法 但是删除元素的运算是存在多种情况的我们要分别处理 ★待删除的结点*p是个叶子结点 ★待删除的结点*p是仅有一个非空子树 ★待删除的结点*p有两个非空子树 如何找出直接前驱:找到要删除节点的第一个左子树然后一直向右 删除代码 void deleteNode(BiStree p)
{if(!p-Rchild) //对第一种及第二种情况的处理{BiSnode * q p;pp-Lchild;free(q);}else if(!p-Lchild) //对第一种及第二种情况的处理{BiSnode * q p;pp-Rchild;free(q);} else{BiSnode * q p;BiSnode * s p-Lchild;while (s-Rchild){qs;ss-Rchild;}//s指向被删节点p的前驱p-datas-data;if(q!p) //详见下两图q-Rchilds-Lchild; //左图elseq-Lchilds-Lchild; //右图free(s);}} 转载于:https://www.cnblogs.com/MrSaver/p/6087402.html
