二叉树删除算法.doc

二叉树删除算法姓名：李晓娜 学号：20122593 班级：软件一班1、 问题描述使用算法实现二叉树的建立及删除。2、 解题思路二叉树的删除操作比较复杂，主要分三种情况：1、删除没有子节点的节点，2、删除只有一个节点的节点（其中有分为两种情况），3、删除有两个节点的节点。首先看第一种情况：（删除没有子节点的节点） 删除没有子节点的节点只需要将被删除节点的父节点指向空即可第二种情况：（删除只有一个子节点的节点） 删除有一个子节点的节点，只需要将被删除节点的父节点指向删除节点的子节点即可第三种情况：（删除有两个子节点的节点，即左右子树都非空） 删除有两个子节点的节点，到底谁来替代被删除的节点的位置呢？是左节点，还是右节点，代替以后这个子节点的子节点应该怎么安排？一系列的问题都出来了。简便的方法就是要找一个节点代替这个被删除的节点，这就要从二叉搜索树的定义来看。因为二叉搜索树是有序的，我们要找的节点在这棵树上，而且这个节点要比被删除的左节点大，比右节点小。先看看这个已被删除节点的右节点为根的子树的所有节点的值都要比被删除节点大，这是二叉搜索树定义的，但是要在这个集合中找到最小的一个，来代替被删除的节点，那就要在这棵子树上一直往左找。这个节点比被删除的节点的右节点小，且比左节点大，那这个节点就叫做被删除节点的后继节点，用这个节点来代替被删除节点。3、 实验代码#include #include typedef int InfoType;typedef int KeyType;/假定关键字类型为整数typedef struct node/结点类型 KeyType key;/关键字项InfoType otherinfo;/其它数据域，InfoType视应用情况而定 下面不处理它struct node *lchild,*rchild;/左右孩子指针BSTNode;typedef BSTNode *BSTree;/BSTree是二叉排序树的类型void main()void InsertBST(BSTree *Tptr,KeyType key);BSTree CreateBST(void);void DelBSTNode(BSTree *Tptr,KeyType key);void ListBinTree(BSTree T);/用广义表表示二叉树BSTree T;int key;printf(请输入关键字（输入0为结束标志）：n);T=CreateBST();ListBinTree(T);printf(n);printf(请输入欲删除关键字：);scanf(%d,&key);DelBSTNode(&T,key);ListBinTree(T);printf(n);void InsertBST(BSTree *Tptr,KeyType key)/若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回BSTNode *f,*p=*Tptr;/p的初值指向根结点while(p)/查找插入位置if(p-key=key) return;/树中已有key，无须插入f=p;/f保存当前查找的结点p=(keykey)? p-lchild:p-rchild;/若keykey，则在左子树中查找，否则在右子树中查找p=(BSTNode *)malloc(sizeof(BSTNode);p-key=key;p-lchild=p-rchild=NULL;/生成新结点if(*Tptr=NULL)/原树为空*Tptr=p;/新插入的结点为新的根else/原树非空时将新结点*p作为*f的左孩子或右孩子插入if(keykey)f-lchild=p;else f-rchild=p;BSTree CreateBST(void)/输入一个结点序列，建立一棵二叉排序树，将根结点指针返回BSTree T=NULL;/初始时T为空树KeyType key;scanf(%d,&key);/读入一个关键字while(key)/假设key=0是输入结束标志InsertBST(&T,key);/将key插入二叉排序树Tscanf(%d,&key);/读入下一关键字return T;/返回建立的二叉排序树的根指针void DelBSTNode(BSTree *Tptr,KeyType key)/在二叉排序树*Tptr中删去关键字为key的结点BSTNode *parent=NULL,*p=*Tptr,*q,*child;while(p)/从根开始查找关键字为key的待删结点if(p-key=key) break;/已找到，跳出查找循环parent=p;/parent指向*p的双亲p=(keykey)?p-lchild:p-rchild;/parent指向*p的左或右子树中继续找if(!p) return;/找不到被删结点则返回q=p;/q记住被删结点*pif(q-lchild & q-rchild)/*q的两个孩子均非空，故找*q的中序后继*pfor(parent=q,p=q-rchild; p-lchild; parent=p,p=p-lchild);/现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL状况child=(p-lchild)? p-lchild:p-rchild;/若是情况(2)，则child非空；否则child为空if(!parent)/*p的双亲为空，说明*p为根，删*p后应修改根指针*Tptr=child;/若是情况(1)，则删去*p后，树为空；否则child变为根else /*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下if(p=parent-lchild)/*p是双亲的左孩子parent-lchild=child;/*child作为*parent的左孩子else parent-rchild=child;/*child作为*parent的右孩子if(p!=q)/是情况(3)，需将*p的数据复制到*qq-key=p-key;/若还有其它数据域亦需复制free(p);/释放*p占用的空间void ListBinTree(BSTree T)/用广义表表示二叉树 if (T!=NULL) printf(%d,T-key);if (T-lchild!=NULL|T-rchild!=NULL) printf();ListBinTree(T-lchild);if (T-rchild!=NULL) pr