首页PTA二叉搜索树的删除操作

PTA二叉搜索树的删除操作

时间: 2025-01-10 11:11:39 浏览: 31

### 关于二叉搜索树中的删除操作在处理二叉搜索树（BST）的删除操作时，确实存在多种策略来维持树的性质。当要删除一个节点时，具体的方法取决于该节点是否有子节点以及有多少个子节点。对于无子节点的情况，可以直接移除目标节点[^1]。如果待删节点仅有一个孩子，则让其父节点指向这个唯一的孩子即可完成删除动作[^2]。而针对拥有两个孩子的节点而言，在保持中序遍历顺序的前提下，通常会选择用此节点右子树里的最小值替代之[^3]。下面是基于上述逻辑编写的C语言版本的`Delete`函数实现： ```c typedef struct TNode* Position; typedef Position BinTree; struct TNode { ElementType Data; BinTree Left; BinTree Right; }; // 查找最小元素辅助函数 BinTree FindMin(BinTree BST){ if (!BST) return NULL; while (BST->Left != NULL) BST = BST->Left; return BST; } BinTree Delete(ElementType X, BinTree BST){ if(!BST){ // 若未找到对应元素 printf("Not Found\n"); return NULL; } if(X < BST->Data)// 向左查找较小者 BST->Left = Delete(X,BST->Left); else if(X > BST->Data)//向右查找较大者 BST->Right= Delete(X,BST->Right); else { // 找到匹配项 // 叶子节点或单一子节点情形 if((!BST->Left && !BST->Right)){ free(BST); BST=NULL; }else if(!BST->Left || !BST->Right){//只有一个分支的情形 BinTree temp=BST; BST=(BST->Left)?BST->Left:BST->Right; free(temp); }else{//有两个分支的情形 BinTree minOfRightSubtree = FindMin(BST->Right); BST->Data=minOfRightSubtree->Data;// 替换数据域而非直接交换指针关系 BST->Right=Delete(minOfRightSubtree->Data,BST->Right);// 删除被替换掉的那个位置上的旧节点 } } return BST; } ```

阅读全文