二叉樹刪除算法

1、二叉樹刪除算法姓名：李曉娜學號：20122593班級：軟件一班1、問題描述 使用算法實現(xiàn)二叉樹的建立及刪除。2、解題思路二叉樹的刪除操作比較復(fù)雜，主要分三種情況：1、刪除沒有子節(jié)點的節(jié)點，2、刪除只有一 個節(jié)點的節(jié)點(其中有分為兩種情況)，3、刪除有兩個節(jié)點的節(jié)點。首先看第一種情況：(刪除沒有子節(jié)點的節(jié)點)刪除沒有子節(jié)點的節(jié)點只需要將被刪除節(jié)點的父節(jié)點指向空即可if (pNode . lc?ild = null 在包 pNode . rcnld = null)-if (pNode = root) /如果是根節(jié)點，那么就刪除整棵樹root = null;:-else if (pNode = pN

2、ode . parent. lchld)-/如果這個節(jié)點是父節(jié)點的左節(jié)點，則將父節(jié)點的左節(jié)點設(shè)為空pNode. parent. lchild = null;:-else if (pNode = pNode . parent. rchild-_/如果這個節(jié)點是父節(jié)點的右節(jié)點，則將父節(jié)點的右節(jié)點設(shè)為空pNode. parent. rchild = null;第二種情況：(刪除只有一個子節(jié)點的節(jié)點)刪除有一個子節(jié)點的節(jié)點，只需要將被刪除節(jié)點的父節(jié)點指向刪除節(jié)點的子節(jié)點即可/V第二種情況：(刪除有一個子節(jié)點的節(jié)點)/7如果要刪除的節(jié)點只有右節(jié)點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如果要刪除的節(jié)點只有左節(jié)點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;第三種情況：(刪除有兩個子節(jié)點的節(jié)點，即左右子樹都非空)刪除有兩個子節(jié)點的節(jié)點，到底誰來替代被刪除的節(jié)點的位置呢？是左節(jié)點，還是右節(jié)點， 代替以后這個子節(jié)點的子節(jié)點應(yīng)該怎么安排？ 一系列的問題都出來了。簡便的方法就是要找 一個節(jié)點代替這個被刪除的節(jié)點，這就要從二叉搜索樹的定義來看。因為二叉搜索樹是有序的， 我們要找的節(jié)點在這棵樹上，而且這個節(jié)點要比被刪除的左節(jié)點大，比右節(jié)點小。先看看這個已 被刪除節(jié)點的右節(jié)點為根的子樹的所有節(jié)點的值都要比被刪除節(jié)點大，這是二叉搜索樹定義的， 但是要在這個集合中找到最小的一個，來代替被刪除的節(jié)點，那就要在這棵子樹上一直往左找。 這個節(jié)點比被刪除的節(jié)點的右節(jié)

6、點小，且比左節(jié)點大，那這個節(jié)點就叫做被刪除節(jié)點的后繼節(jié)點， 用這個節(jié)點來代替被刪除節(jié)點。/就二更樹當中刪除指定的節(jié)點public void delete ( int k已甘)throws Zxceptio -TreeNode pNode = 已已arc?: (krey);i (pNcjci已 =null) throw new Zxceptior. (中不存在要刪除的這個節(jié)點！，r )；delete(pNode);/7這個方法可以算是一個遞歸的方法，適用于要刪除的節(jié)點的兩個子節(jié)點都非空,/7笄且要刪除的這個節(jié)點的后續(xù)節(jié)點也有子樹的情:兄下private void delete (TreeNode

7、 pNode) throws Zxceptio -/第一種情況：刪除沒有子節(jié)點的節(jié)點if (pNode . lchild = null 蒞蒞 pNode . rchild = = null)-if (pNode = root如果是根節(jié)點，那么裁刪除整棵樹root = nul1;:-else if (pNode = pNode. parent. lchld-/如果這個節(jié)點是父節(jié)點的左節(jié)點，則將父節(jié)點的左節(jié)點設(shè)為空 pNode. parent. lchld = null;:-else if (pNode = pNode. parent. rchild-/如果這個節(jié)點是父節(jié)點的右節(jié)點，則將父節(jié)點的右

8、節(jié)點設(shè)為空3、實驗代碼FNode- parent - rchild =null;#include vstdio.h#include typedef int InfoType; typedef int KeyType; typedef struct node KeyType key;InfoType otherinfo;/假定關(guān)鍵字類型為整數(shù)/結(jié)點類型/關(guān)鍵字項其它數(shù)據(jù)域，InfoType視應(yīng)用情況而定卜面不處理它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(”請輸入關(guān)鍵字(輸入0為結(jié)束標志)：n);T=CreateBST();ListBinTree(T);printf(n);printf(請輸入欲刪除關(guān)鍵字：); scanf(%d,&key);DelBSTNode(&T,key);ListBinTree(T);pr

10、intf(n);void InsertBST(BSTree *Tptr,KeyType key)若二叉排序樹*Tptr中沒有關(guān)鍵字為key，則插入，否則直接返回BSTNode *f,*p=*Tptr;/p的初值指向根結(jié)點while(p)/查找插入位置if(p-key=key)return;樹中已有 key，無須插入f=p；f保存當前查找的結(jié)點p=(keykey)? p-lchild:p-rchild;若keykey，則在左子樹中查找，否則在右子樹中查找p=(BSTNode *)malloc(sizeof(BSTNode); p-key=key;p-lchild=p-rchild=NULL;/生

11、成新結(jié)點if(*Tptr=NULL)/原樹為空*Tptr=p;/新插入的結(jié)點為新的根else/原樹非空時將新結(jié)點*p作為*f的左孩子或右孩子插入 if(keykey) f-lchild=p;else f-rchild=p;BSTree CreateBST(void)/初始時 T /初始時 T 為空樹/讀入一個關(guān)鍵字/讀入一個關(guān)鍵字/假設(shè) key=0 是輸入結(jié)束標志 /將 key 插入二叉排序樹 T/讀入下一關(guān)鍵字/返回建立的二叉排序樹的根指針I(yè)nsertBST(&T,key); scanf(%d,&key); return T;void DelBSTNode(BSTree *Tptr,KeyT

12、ype key)在二叉排序樹*Tptr中刪去關(guān)鍵字為key的結(jié)點BSTNode *parent=NULL,*p=*Tptr,*q,*child;while(p)從根開始查找關(guān)鍵字為key的待刪結(jié)點if(p-key=key) break; /已找到，跳出查找循環(huán)parent=p;/parent指向*p的雙親p=(keyvp-key)?p-lchild:p-rchild;/parent 指向 *p 的左或右子樹中繼續(xù)找if(!p) return;q=p;/找不到被刪結(jié)點則返回/q記住被刪結(jié)點*pif(q-lchild & q-rchild) *q的兩個孩子均非空，故找*q的中序后繼*p for(p

13、arent=q,p=q-rchild; p-lchild; parent=p,p=p-lchild);現(xiàn)在情況(3)已被轉(zhuǎn)換為情況(2)，而情況(1)相當于是情況(2)中child=NULL狀況 child=(p-lchild)? p-lchild:p-rchild;/若是情況(2),則 child 非空；否則 child 為空if(!parent)*p的雙親為空，說明*p為根，刪*卩后應(yīng)修改根指針*Tptr=child;若是情況，則刪去*卩后，樹為空；否則child變?yōu)楦鵨lse *p不是根，將*p的孩子和*卩的雙親進行連接，*p從樹上被摘下if(p=parent-lchild) paren

14、t-lchild=child;else parent-rchild=child; if(p!=q)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的數(shù)據(jù)復(fù)制到*q/若還有其它數(shù)據(jù)域亦需復(fù)制釋放*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-