









typedef struct TreeNode *BinTree; typedef BinTree Position; struct TreeNode{ ElementType Data; BinTree Left; BinTree Right; }; BinTree BST; BinTree Insert(ElementType X,BinTree BST)//二叉搜索樹的插入算法{ if(!BST){//若原樹為空,生成并返回一個結點的二叉搜索樹 BST=malloc(sizeof(struct TreeNode)); BST->Data=X; BST->Left=BST->Right=NULL; }else//開始找要插入元素的位置 if(X<BST->Data) BST->Left=Insert(X,BST->Left);//遞歸插入左子樹 else if(X>BST->Data) BST->Right=Insert(X,BST->Right);//遞歸插入右子樹 //else X已經存在,什么都不做 return BST; }BinTree Delete(ElementType X,BinTree BST)//二叉搜索樹的刪除算法{ Position Tmp; if(!BST) PRintf("要刪除的元素未找到"); else 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){//被刪除結點有左右兩個結點 Tmp=FindMin(BST->Right); //在右子樹中找最小的元素填充刪除結點 BST->Data=Tmp->Data; BST->Right=Delete(BST->Data,BST->Right); //在刪除結點的右子樹中刪除最小元素 }else{//被刪除結點有一個或無子結點 Tmp=BST; if(!BST->Left)//有右孩子或無子結點 BST=BST->Right; else if(!BST->Right)//有左孩子或無子結點 BST=BST->Left; free(Tmp); } return BST; }
新聞熱點
疑難解答