《二叉树删除算法》由会员分享，可在线阅读，更多相关《二叉树删除算法（5页珍藏版）》请在金锄头文库上搜索。
1、二叉树删除算法姓名：李晓娜学号：20122593班级：软件一班1、问题描述 使用算法实现二叉树的建立及删除。2、解题思路二叉树的删除操作比较复杂，主要分三种情况：1、删除没有子节点的节点，2、删除只有一 个节点的节点(其中有分为两种情况)，3、删除有两个节点的节点。首先看第一种情况：(删除没有子节点的节点)删除没有子节点的节点只需要将被删除节点的父节点指向空即可if (pNode . lc?ild = null 在包 pNode . rcnld = null)-if (pNode = root) /如果是根节点，那么就刪除整棵树root = null;:-else if (pNode = pN
2、ode . parent. lchld)-/如果这个节点是父节点的左节点，则将父节点的左节点设为空pNode. parent. lchild = null;:-else if (pNode = pNode . parent. rchild-_/如果这个节点是父节点的右节点，则将父节点的右节点设为空pNode. parent. rchild = null;第二种情况：(删除只有一个子节点的节点)删除有一个子节点的节点，只需要将被删除节点的父节点指向删除节点的子节点即可/V第二种情况：(刪除有一个子节点的节点)/7如果要刪除的节点只有右节点if (pNode . lchild = null 乞乞
3、pNode . rchild = nul 1)-if (pNode = root)-root = pNode. rchild;:-else i f (pNode = pNode . parent. lchild)-pNode. parent. lchld = pNode. rchild;pNode. rchild. parent = pNode. parent;:-else i f (pNode = pNode . parent. rchild)-pNode. parent. rchld = pNode. rchildrpNode. rchild. parent = pNode. parent
4、;/7如果要刪除的节点只有左节点if (pNode . lchild : = null 在包 pNode . rchild = null)-if (pNode = root-root = pNode. lchld;:-else if (pNode = pNode. parent. lchild-pNode. parent. lchild = pNode. lchild;pNode. lchild. parent = pNode. parent;:-else if (pNode = pNode. parent. rchild-pNode. parent. rchild = pNode. lchi
5、ld;第三种情况：(删除有两个子节点的节点，即左右子树都非空)删除有两个子节点的节点，到底谁来替代被删除的节点的位置呢？是左节点，还是右节点， 代替以后这个子节点的子节点应该怎么安排？ 一系列的问题都出来了。简便的方法就是要找 一个节点代替这个被删除的节点，这就要从二叉搜索树的定义来看。因为二叉搜索树是有序的， 我们要找的节点在这棵树上，而且这个节点要比被删除的左节点大，比右节点小。先看看这个已 被删除节点的右节点为根的子树的所有节点的值都要比被删除节点大，这是二叉搜索树定义的， 但是要在这个集合中找到最小的一个，来代替被删除的节点，那就要在这棵子树上一直往左找。 这个节点比被删除的节点的右节
6、点小，且比左节点大，那这个节点就叫做被删除节点的后继节点， 用这个节点来代替被删除节点。/就二更树当中删除指定的节点public void delete ( int k已甘)throws Zxceptio -TreeNode pNode = 已已arc?: (krey);i (pNcjci已 =null) throw new Zxceptior. (中不存在要刪除的这个节点！，r )；delete(pNode);/7这个方法可以算是一个递归的方法，适用于要刪除的节点的两个子节点都非空,/7笄且要刪除的这个节点的后续节点也有子树的情:兄下private void delete (TreeNode
7、 pNode) throws Zxceptio -/第一种情况：刪除没有子节点的节点if (pNode . lchild = null 莅莅 pNode . rchild = = null)-if (pNode = root如果是根节点，那么裁刪除整棵树root = nul1;:-else if (pNode = pNode. parent. lchld-/如果这个节点是父节点的左节点，则将父节点的左节点设为空 pNode. parent. lchld = null;:-else if (pNode = pNode. parent. rchild-/如果这个节点是父节点的右节点，则将父节点的右
8、节点设为空3、实验代码FNode- parent - rchild =null;#include vstdio.h#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
9、()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);pr
10、intf(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;/生
11、成新结点if(*Tptr=NULL)/原树为空*Tptr=p;/新插入的结点为新的根else/原树非空时将新结点*p作为*f的左孩子或右孩子插入 if(keykey) f-lchild=p;else f-rchild=p;BSTree CreateBST(void)/初始时 T 为空树/输入一个结点序列，建立一棵二叉排序树，将根结点指针返回/读入一个关键字/假设 key=0 是输入结束标志 /将 key 插入二叉排序树 T/读入下一关键字/返回建立的二叉排序树的根指针BSTree T=NULL; KeyType key; scanf(%d,&key); while(key)InsertBST(
12、&T,key); scanf(%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=(keyvp-key)?p-lchild:p-rchild;/parent 指向 *p 的左或右子树中继续找if(!p) return;q=p;/找不到被删
13、结点则返回/q记住被删结点*pif(q-lchild & q-rchild) *q的两个孩子均非空，故找*q的中序后继*p for(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为根，删*卩后应修改根指针*Tptr=child;若是情况，则删去*卩后，树为空；否则ch
14、ild变为根else *p不是根，将*p的孩子和*卩的双亲进行连接，*p从树上被摘下if(p=parent-lchild) parent-lchild=child;else parent-rchild=child; if(p!=q)q-key=p-key;free(p);*p是双亲的左孩子*child作为*parent的左孩子*child作为*parent的右孩子是情况(3),需将*p的数据复制到*q/若还有其它数据域亦需复制释放*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) printf(,);ListBinTree(T-rchild); printf();4、运行结果请输入关键字(输入回为结束标志):1 2 3 4 5 60请输入欲删除关键字：石Press anv key to continue5、实验总结 通过此次实验，对二叉树创建删除等过程都有了更进一步的认识
