建设外卖网站规划书电子商务网站与建设课件

当前位置： 首页 > news >正文

建设外卖网站规划书,电子商务网站与建设课件,外语网站开发,吉林省网络推广公司二叉排序树习题1.设计算法构建一棵二叉排序树(又称二叉搜索树BST)2.查找二叉排序树中结点为x的结点所在的层数3.删除二叉排序树T中值为x的结点4.查找二叉排序树中所有小于key的关键字5.编写算法#xff0c;将一棵二叉树t分解成两棵二叉排序树t1和t2#xff0c;使得t1中的所有…二叉排序树习题1.设计算法构建一棵二叉排序树(又称二叉搜索树BST)2.查找二叉排序树中结点为x的结点所在的层数3.删除二叉排序树T中值为x的结点4.查找二叉排序树中所有小于key的关键字5.编写算法将一棵二叉树t分解成两棵二叉排序树t1和t2使得t1中的所有结点关键字的值都小于xt2中所有结点关键字的值都大于x6.已知二叉排序树中每一个结点值为整型采用二叉链表存储编写算法删除二叉排序树中所有关键字小于x的结点 文章目录 1.设计算法构建一棵二叉排序树(又称二叉搜索树BST)2.查找二叉排序树中结点为x的结点所在的层数3.删除二叉排序树T中值为x的结点4.查找二叉排序树中所有小于key的关键字5.编写算法将一棵二叉树t分解成两棵二叉排序树t1和t2使得t1中的所有结点关键字的值都小于xt2中所有结点关键字的值都大于x6.已知二叉排序树中每一个结点值为整型采用二叉链表存储编写算法删除二叉排序树中所有关键字小于x的结点 1.设计算法构建一棵二叉排序树(又称二叉搜索树BST) 二叉树搜索树的构建就是多个插入操作的重复使用下面的代码并用二叉树的前序遍历检验插入结果。 二叉排序树中序序列序列就变成了有序输出 #include stdio.h #include stdlib.htypedef int ElemType; typedef struct BiTNode {ElemType data;struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;//二叉排序树的插入操作 void insertKey(BiTree T,ElemType key) {//if是根(子树根)节点的操作else if是左右子树操作 根节点左右子树的操作问题的解if(TNULL){BiTNode * p(BiTNode *)malloc(sizeof(BiTNode));p-lchildNULL;p-rchildNULL;p-datakey;Tp;}else if(keyT-data)//如果key当前结点{insertKey(T-lchild, key);}else if(key T-data){insertKey(T-rchild, key);} }BiTNode * creatBSTree() {BiTNode *TNULL;ElemType keyList[]{40,10,45,15};int keyListLength4;for(int i0;ikeyListLength;i){insertKey(T, keyList[i]);}return T; }void preOreder(BiTree T) {if(TNULL) return;printf(%d ,T-data);preOreder(T-lchild);preOreder(T-rchild); } int main() {BiTree TcreatBSTree();preOreder(T);printf(\n); } 2.查找二叉排序树中结点为x的结点所在的层数 我的思考在上一节中我们可以用层序遍历来完成这个事但是那个是全部二叉树可用这一次有什么区别 答之前的二叉树要遍历完全部的结点才能找到x。需要横着找 这次有序的寻找就不同了是竖着找 int nodelevel0; int getNode(BiTree T,int x) {if(T!NULL){nodelevel;if(x T-data) return nodelevel;else if(xT-data){getNode(T-lchild, x);}else if(xT-data){getNode(T-rchild, x);}}else nodelevel0;//表明没有查到x返回0return nodelevel; }3.删除二叉排序树T中值为x的结点 找到值为x的结点然后删除该点 我们这里以方法1为例子右孩子插入到左孩子的最大结点中 思路提炼 关于存在两棵子树的时候 找到左子树的最右子树最大结点它肯定没有右孩子将待删除结点的右孩子变成它的右孩子删掉待删除结点即可 void deleteopr(BiTree T) {//第一种情况删除结点是根节点第二种情况只有一个子树第三种情况有两个子树if(T-lchildNULLT-rchildNULL){TNULL;}else if(T-lchild!NULLT-rchild!NULL){BiTNode *pMaxT-lchild;while(pMax-rchild!NULL){pMaxpMax-rchild;}pMax-rchildT-rchild;BiTNode *pT;TT-lchild;free(p);}else //只有一边有子树{//如果左边有子树if(T-lchild!NULL){//记录被抛弃的结点的存储空间用完它之后就给他free掉BiTNode *pT;TT-lchild;free(p);}else{BiTNode pT;TT-rchild;free(p);}} } void delete_treeNode(BiTree T,ElemType x) {if(T-datax){//删除这个结点删除操作开始,否则的话就继续往左右子树里寻找这个结点deleteopr(T);}else if(xT-data){delete_treeNode(T-lchild, x);}else if(xT-data){delete_treeNode(T-rchild, x);} } 4.查找二叉排序树中所有小于key的关键字 思路:二叉排序树中序遍历是有序的所以在中序遍历的过程中就能找到全部小于key的结点中止中序遍历就行。 简单代码已省略 5.编写算法将一棵二叉树t分解成两棵二叉排序树t1和t2使得t1中的所有结点关键字的值都小于xt2中所有结点关键字的值都大于x 思路 6.已知二叉排序树中每一个结点值为整型采用二叉链表存储编写算法删除二叉排序树中所有关键字小于x的结点 错误思路是以为找到某点小于x就把它连同它的左子树全部删除若它存在右子树就让它右子树代替它。这种思路就漏解了漏掉了小于结点的右子树中仍可能存在小于x的结点。 明确使用哪种遍历-使用前序遍历因为根节点是划分区间的依据只有使用前序遍历我们才能够先拿到根结点。
void deleteFunc(BiTree T) //删除一整棵树先删除左子树再删除右子树最后删除根节点就不用保存根节点的信息了 {if(T!NULL){deleteFunc(T-lchild);deleteFunc(T-rchild);free(T);T NULL; // 避免悬空指针直接将T设为NULL已经释放掉的指针} }void preOrderTraversing(ElemType x,BiTree T) {//如果树不为空if(T!NULL){if(T-datax) //如果当前正正好好T的左子树小于xT的右子树大于x那么删除左子树即可{//deleteFunc(T-lchild); //删除函数删除了T的左孩子T-lchildNULL;}else if(xT-data) //如果当前x大于该结点那么该结点的左孩子肯定都比x小需要删除右孩子中可能存在着小于x的值所以右孩子要递归{//递归删除右子树preOrderTraversing(x,T-rchild);//删除左子树和根节点这里注意删除根节点的时候它可能存在右孩子所以要让指针指向他的右孩子我们保存根节点信息直接让指针指向其右孩子BiTNode pT;TT-rchild;p-rchildNULL; //右子树置空为什么要把右子树置空要切断它指针的联系因为现在的右子树已经是新的根节点了如果不把老的根节点的右子树置空删除操作的时候会把右子树也删除了//deleteFunc(p); //删除根节点和它的左孩子}else if(xT-data) //如果当前x小于该结点那么该结点的右孩子肯定都比x大左孩子中可能存在着小于x的值所以左孩子要递归{//右子树不用管处理它的左子树就行preOrderTraversing(x,T-lchild);}} }