#include<iostream> using namespace std; typedef struct ElemType{ int key; }ElemType; typedef struct BSTNode{ ElemType data; BSTNode *lchild,*rchild; }BSTNode,*BSTree; int flag=1; void InsertBST(BSTree &T,ElemType e ) ;//实现细节隐藏 void CreateBST(BSTree &T ) ;//实现细节隐藏 void InOrderTraverse(BSTree &T);//中序遍历,实现细节隐藏 void DeleteBST(BSTree &T,char key) { BSTree p=T;BSTree f=NULL; BSTree q; BSTree s; while(p){ if (p->data.key == key) break; f=p; if (p->data.key> key) p=p->lchild; else p=p->rchild; } if(!p) ; if ((p->lchild)&& (p->rchild)) { q = p; s = p->lchild; while (s->rchild) {q = s; s = s->rchild;} p->data= s->data; if(q!=p) ; else ; delete s; } else{ if(!p->rchild) { q = p; p = p->lchild; } else if(!p->lchild) { q = p; p = p->rchild; } if(!f) ; else if (q==f->lchild) ; else ; delete q; } } int main() { BSTree T; CreateBST(T); int key; cin>>key; DeleteBST(T,key); InOrderTraverse(T); }
时间: 2024-02-04 15:04:31 浏览: 32
这是一个二叉搜索树的删除操作的实现代码。其中,InsertBST、CreateBST和InOrderTraverse的实现细节被隐藏了。DeleteBST的参数包括二叉搜索树的根节点指针T和待删除节点的key值。具体实现过程如下:
1. 初始化BSTree类型的指针p,f,q,s,分别指向二叉搜索树的根节点,p的父节点、待删除节点和p的左子树中最大的节点。
2. 在二叉搜索树中查找待删除节点,如果找到了就跳出循环,否则根据二叉搜索树的性质继续向下搜索。
3. 如果p的左右子树都非空,则用节点s来代替待删除节点p,s为p的左子树中最大的节点。具体实现过程是:先用q指向p,s指向p的左子树,然后在s的右子树中找到最大的节点,用s来代替p,再将s的数据赋给p,最后删除s。
4. 如果p的左右子树中有一个为空,则将p的父节点f指向p的非空子树,然后删除p。
5. 如果p的父节点为空,则p为根节点,直接删除。
6. 如果p为f的左子树,则将f的左子树指向p的非空子树。
7. 如果p为f的右子树,则将f的右子树指向p的非空子树。
8. 删除节点p。
在主函数中,首先创建二叉搜索树T,然后输入待删除节点的key值,最后调用DeleteBST函数删除节点,并中序遍历输出删除后的二叉搜索树。
相关问题
直接插入排序。 #include <iostream> #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void InsertSort(SqList &L) { int i,j; for(i=2;i<=
L.length;i++) { //从第二个元素开始插入排序 if(L.r[i].key<L.r[i-1].key) { L.r[0]=L.r[i]; //哨兵 L.r[i]=L.r[i-1]; for(j=i-2;L.r[0].key<L.r[j].key;j--) { //从后往前比较 L.r[j+1]=L.r[j]; //记录后移 } L.r[j+1]=L.r[0]; //插入到正确位置 } } }
以上是直接插入排序的 C++ 代码实现,使用了哨兵来简化代码。对于一个长度为n的序列,平均时间复杂度为O(n^2),最坏时间复杂度为O(n^2),空间复杂度为O(1)。
#include <iostream> #include <cstdlib> using namespace std; // self-referential structure struct listNode { char data; // each listNode contains a character struct listNode *nextPtr; // pointer to next node }; typedef struct listNode ListNode; // synonym for struct listNode typedef ListNode *ListNodePtr; // synonym for ListNode* // prototypes void insert(ListNodePtr *sPtr, char value); char delete(ListNodePtr *sPtr, char value); int isEmpty(ListNodePtr sPtr); void printList(ListNodePtr currentPtr); void instructions(void);
这段代码存在两个问题:
1. 第一行代码 "#include <iostream> #include <cstdlib>" 中间缺少了换行符,应该写成 "#include <iostream>\n#include <cstdlib>" 以便阅读。
2. C++ 中的 "delete" 是一个保留关键字,不能用作函数名。因此,函数名中的 "delete" 应该改成其他的名字,例如 "deleteNode"。