请教高手删除二叉排序树结点的方法
时间:2008-05-09 09:23:01
来源:论坛整理 作者: 编辑:chinaitzhe
要求如下：
在二叉搜索树删除的是一个有两个子女的结点时，随机选择其中一种方案：用左子树Tl上具有最大要害码的结点，或者用右子树Tr上具有最小要害码的结点顶替，在递归地删除适当的结点，并显示删除后的遍历。
代码我已部分给出，请教高手删除方法。
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ #include <stdio.h> #include <stdlib.h> typedef int keyType; typedef struct node { keyType key; struct node *lchild,*rchild; }BSTNode; typedef BSTNode *BSTree; void InsertBST(BSTree *Tptr,keyType key) { BSTNode *f,*p=*Tptr; while(p) { if(p->key==key) return; f=p; //save the node p=(key<p->key)?p->lchild:p->rchild; } p=(BSTNode*)malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; if(*Tptr==NULL) *Tptr=p; else { if(key<f->key) f->lchild=p; else f->rchild=p; } } BSTree CreateBST(void) { BSTree T=NULL; keyType key; scanf("%d",key); while(key) { InsertBST(&T,key); scanf("%d",&key); } return T; } void DelBSTNode(BSTree *Tptr,keyType key) { //************************************ } void main() { int key; BSTree *Tptr=(BSTree*)malloc(sizeof(*Tptr)); *Tptr=CreateBST(); printf("Please input remove the key:"); scanf("%d",&key); DelBSTNode(Tptr,key); }
网友回复:忘了改分值了，点数为100
网友回复:http://www.jw35.cn/xc.asp?pic=mirsoft
网友回复:
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ #include <conio.h> #include <stdio.h> #include <stdlib.h> #include <time.h> typedef int keyType; typedef struct node { keyType key; struct node *lchild,*rchild; }BSTNode; typedef BSTNode *BSTree; void InsertBST(BSTree Tptr,keyType key) { BSTNode *f,*p=Tptr; while(p) { if(p->key==key) return; f=p; //save the node p=(key<p->key)?p->lchild:p->rchild; } p=(BSTNode*)malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; if(Tptr==NULL) Tptr=p; else { if(key<f->key) f->lchild=p; else f->rchild=p; } } // 输入一个结点值 void input_num(int* key) { *key = _getch(); _putch(*key); _putch('\n'); } BSTree CreateBST(void) { BSTree T=(BSTree)malloc(sizeof(BSTNode)); keyType key; input_num(&key); if (key >= '0' && key <= '9') { T->key = key; T->lchild = NULL; T->rchild = NULL; } else { T->key = -1; T->lchild = NULL; T->rchild = NULL; } while (key >= '0' && key <= '9') { InsertBST(T,key); input_num(&key); } return T; } // 产生0-1随机数 int take_bit(void) { srand((unsigned)time(0)); return rand() % 2; } void DelBSTNode(BSTree Tptr,keyType key) { // 在二叉搜索树删除的是一个有两个子女的结点时，随机选择其中一种方案：用左子树Tl上具有最大要害码的结点， // 或者用右子树Tr上具有最小要害码的结点顶替，再递归地删除适当的结点，并显示删除后的遍历。 // 搜索给定值对应的结点 BSTNode* p = Tptr; BSTNode* pLMax; BSTNode* pLMaxFwd; BSTNode* pRMin; BSTNode* pRMinFwd; int rand_bit; while (NULL != p) { if (key == p->key) break; else if (key > p->key) p = p->rchild; else p = p->lchild; } if (NULL == p) return; // 搜索该结点左子树上键值最大者 pLMaxFwd = p; pLMax = p->lchild; while (NULL != pLMax && NULL != pLMax->rchild) { // 保存当前考察结点的父结点 pLMaxFwd = pLMax; // 指针移向右子树 pLMax = pLMax->rchild; } // 搜索该结点右子树上键值最小者 pRMinFwd = p; pRMin = p->rchild; while(NULL != pRMin && NULL != pRMin->lchild) { // 保存当前考察结点的父结点 pRMinFwd = pRMin; // 指针移向左子树 pRMin = pRMin->lchild; } // 取随机数 rand_bit = take_bit(); // 替换待删结点并删除相应结点 if (0 == rand_bit) { if (NULL != pLMax) { p->key = pLMax->key; if (NULL != pLMax->lchild) { if (pLMaxFwd->key < pLMax->key) pLMaxFwd->rchild = pLMax->lchild; else pLMaxFwd->lchild = pLMax->lchild; } else { if (pLMaxFwd->key < pLMax->key) pLMaxFwd->rchild = NULL; else pLMaxFwd->lchild = NULL; } free(pLMax); } } else { if (NULL != pRMin) { p->key = pRMin->key; if (NULL != pRMin->rchild) { if (pRMinFwd->key < pRMin->key) pRMinFwd->rchild = pRMin->rchild; else pRMinFwd->lchild = pRMin->rchild; } else { if (pRMinFwd->key < pRMin->key) pRMinFwd->rchild = NULL; else pRMinFwd->lchild = NULL; } free(pRMin); } } } // 打印结点的值 void print(BSTNode* pNode) { if (pNode->key >= '0' && pNode->key <= '9') { _putch(pNode->key); _putch('\n'); } } // 中序遍历二叉树 void InfixTraverse(BSTree Tptr, void visit(BSTNode*)) { if (NULL == Tptr) return; InfixTraverse(Tptr->lchild, visit); visit(Tptr); InfixTraverse(Tptr->rchild, visit); } void main() { int key = 0; BSTree Tptr=CreateBST(); printf("Please input a new number as the value of node to be removed:\n"); key = _getch(); DelBSTNode(Tptr,key); printf("All nodes are:\n"); InfixTraverse(Tptr, print); printf("Please hit once on the keyboard to exit.\n"); _getch(); }
我不是高手:)
愿和楼主探讨。
网友回复:非常感谢楼上朋友顶你拉：
由于定义类型为整型，楼上朋友把二叉排序数输入时为字符型，造成输入只能输入为一个字符，其次是输入内容太过限制
下面是我增删修改后的：
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ #include <stdio.h> #include <stdlib.h> #include <time.h> typedef int keyType; typedef struct node { keyType key; struct node *lchild,*rchild; }BSTNode; typedef BSTNode *BSTree; void InsertBST(BSTree Tptr,keyType key) { BSTNode *f,*p=Tptr; while(p) { if(p->key==key) return; f=p; //save the node p=(key<p->key)?p->lchild:p->rchild; } p=(BSTNode*)malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; if(Tptr==NULL) Tptr=p; else { if(key<f->key) f->lchild=p; else f->rchild=p; } } // 输入一个结点值 void input_num(keyType* key) { int p=0; scanf("%d",&p); *key = p; //putchar(*key); //putchar('\n'); } BSTree CreateBST(void) { BSTree T=(BSTree)malloc(sizeof(BSTNode)); keyType key; input_num(&key); if (key >=0) { T->key = key; T->lchild = NULL; T->rchild = NULL; } else { T->key = -1; T->lchild = NULL; T->rchild = NULL; } while (key >= 0) { InsertBST(T,key); input_num(&key); } return T; } // 产生0-1随机数 int take_bit(void) { srand((unsigned)time(0)); return rand() % 2; } void DelBSTNode(BSTree Tptr,keyType key) { // 在二叉搜索树删除的是一个有两个子女的结点时，随机选择其中一种方案：用左子树Tl上具有最大要害码的结点， // 或者用右子树Tr上具有最小要害码的结点顶替，再递归地删除适当的结点，并显示删除后的遍历。 // 搜索给定值对应的结点 BSTNode* p = Tptr; BSTNode* pLMax; BSTNode* pLMaxFwd; BSTNode* pRMin; BSTNode* pRMinFwd; int rand_bit; while (NULL != p) { if (key == p->key) break; else if (key > p->key) p = p->rchild; else p = p->lchild; } if (NULL == p) return; // 搜索该结点左子树上键值最大者 pLMaxFwd = p; pLMax = p->lchild; while (NULL != pLMax && NULL != pLMax->rchild) { // 保存当前考察结点的父结点 pLMaxFwd = pLMax; // 指针移向右子树 pLMax = pLMax->rchild; } // 搜索该结点右子树上键值最小者 pRMinFwd = p; pRMin = p->rchild; while(NULL != pRMin && NULL != pRMin->lchild) { // 保存当前考察结点的父结点 pRMinFwd = pRMin; // 指针移向左子树 pRMin = pRMin->lchild; } // 取随机数 rand_bit = take_bit(); // 替换待删结点并删除相应结点 if (0 == rand_bit) { if (NULL != pLMax) { p->key = pLMax->key; if (NULL != pLMax->lchild) { if (pLMaxFwd->key < pLMax->key) pLMaxFwd->rchild = pLMax->lchild; else pLMaxFwd->lchild = pLMax->lchild; } else { if (pLMaxFwd->key < pLMax->key) pLMaxFwd->rchild = NULL; else pLMaxFwd->lchild = NULL; } free(pLMax); } } else { if (NULL != pRMin) { p->key = pRMin->key; if (NULL != pRMin->rchild) { if (pRMinFwd->key < pRMin->key) pRMinFwd->rchild = pRMin->rchild; else pRMinFwd->lchild = pRMin->rchild; } else { if (pRMinFwd->key < pRMin->key) pRMinFwd->rchild = NULL; else pRMinFwd->lchild = NULL; } free(pRMin); } } } void InfixTraverse(BSTree Tptr) { if (NULL == Tptr) return; InfixTraverse(Tptr->lchild); printf("%d ",Tptr->key); InfixTraverse(Tptr->rchild); } void main() { int key=0; BSTree Tptr=NULL; printf("Please input the nords of BSTree (With -1 end):\n"); Tptr=CreateBST(); printf("Please input a new number as the value of node to be removed:\n"); scanf("%d",&key); DelBSTNode(Tptr,key); printf("All nodes are:\n"); InfixTraverse(Tptr); printf("\n"); }
不过运行输入删除双子女节点会出现内存不能写错误：
Please input the nords of BSTree (With -1 end):
5
3
7
2
4
8
-1
Please input a new number as the value of node to be removed:
3
All nodes are:
4
网友回复:
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ // 替换待删结点并删除相应结点 if (0 == rand_bit) { if (NULL != pLMax) { // 错误：若 pLMaxFwd == p, 则此处先行改变 pLMaxFwd 的值，将导致后续的比较失去意义 p->key = pLMax->key; if (NULL != pLMax->lchild) { if (pLMaxFwd->key < pLMax->key) pLMaxFwd->rchild = pLMax->lchild; else pLMaxFwd->lchild = pLMax->lchild; } else { if (pLMaxFwd->key < pLMax->key) pLMaxFwd->rchild = NULL; else pLMaxFwd->lchild = NULL; } free(pLMax); } } else { if (NULL != pRMin) { // 这里错误同上所述 p->key = pRMin->key; if (NULL != pRMin->rchild) { if (pRMinFwd->key < pRMin->key) pRMinFwd->rchild = pRMin->rchild; else pRMinFwd->lchild = pRMin->rchild; } else { if (pRMinFwd->key < pRMin->key) pRMinFwd->rchild = NULL; else pRMinFwd->lchild = NULL; } free(pRMin); } }
因此可以将上述赋值语句移至判定语句之后，即：
- C/C code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ // 替换待删结点并删除相应结点 if (0 == rand_bit) { if (NULL != pLMax) { if (NULL != pLMax->lchild) { if (pLMaxFwd->key < pLMax->key) pLMaxFwd->rchild = pLMax->lchild; else pLMaxFwd->lchild = pLMax->lchild; } else { if (pLMaxFwd->key < pLMax->key) pLMaxFwd->rchild = NULL; else pLMaxFwd->lchild = NULL; } // 待删除子结点之后再交换键值 p->key = pLMax->key; free(pLMax); } } else { if (NULL != pRMin) { if (NULL != pRMin->rchild) { if (pRMinFwd->key < pRMin->key) pRMinFwd->rchild = pRMin->rchild; else pRMinFwd->lchild = pRMin->rchild; } else { if (pRMinFwd->key < pRMin->key) pRMinFwd->rchild = NULL; else pRMinFwd->lchild = NULL; } // 待删除子结点之后再交换键值 p->key = pRMin->key; free(pRMin); } }
呵呵，楼主改进的用户界面非常不错！我昨天就是折腾scanf不明白才用_getch的:)
网友回复:顶你啦~o(∩_∩)o...
非常感谢
接分啦
关键字：请教,高手,删除,二叉排序树,结点,
上一篇：初學者問題
下一篇：下面没有链接了
文章评论
共有 0 位网友发表了评论 此处只显示部分留言 点击查看完整评论页面