6-12 二叉搜索树的操作集 (30分)

6-12 二叉搜索树的操作集 (30分)

Insert(BinTree BST,ElementType x){ //二叉排序树插入时，只能插入到叶子结点 if(BST == NULL){ BST = (BinTree)malloc(sizeof(struct TNode)); BST->Data = x; BST->Left = NULL; BST->Right = NULL; }//插入到左子树 else if(xData){ BST->Left = Insert(BST->Left, x); }//插入到右子树 else if(x>BST->Data){ BST->Right = Insert(BST->Right, x); } return BST;}BinTree Delete(BinTree BST,ElementType x){ BinTree tmp; if (BST != NULL){ if(xData){ BST->Left = Delete(BST->Left, x); }else if(x>BST->Data){ BST->Right = Delete(BST->Right, x); }else{ //找到了删除位置 //左子树和右子树都不是空的 //找到左子树最大的或者右子树最小的，数据进行交换，然后删除左子树或者右子树里用于交换的数据 if(BST->Left&&BST->Right){ tmp = FindMin(BST->Right); BST->Data = tmp->Data; BST->Right = Delete(BST->Right, tmp->Data); } else{//这里的else关系特殊 tmp=BST; if(BST->Left==NULL){ BST=BST->Right; }else if(BST->Right==NULL) BST=BST->Left; free(tmp);//不要忘记free掉 } } return BST; } printf("Not Found\n"); return BST;}Position Find(BinTree BST,ElementType x){ //如果树是空的 返回NULL if(!BST) return NULL; if(BST->Data == x) return BST; else if(x < BST->Data){ return Find(BST->Left, x); }else if(x>BST->Data){ return Find(BST->Right, x); }} //整棵树的最左下角Position FindMin(BinTree BST){ if(BST){ while(BST->Left){//请注意这里的条件一定是Bst->left 否则BST会指向空 BST = BST->Left; } } return BST;} //整棵树的最右下角Position FindMax(BinTree BST){ if(BST){ while(BST->Right){ BST = BST->Right; } } return BST;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。