二叉排序樹(shù)插入與刪除元素

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告知識(shí)范疇：查找實(shí)驗(yàn)題目：二叉排序樹(shù)插入與刪除元素實(shí)驗(yàn)內(nèi)容及要求：編寫(xiě)控制臺(tái)應(yīng)用程序，提供以下菜單項(xiàng)：插入元素從鍵盤(pán)輸入若干兩兩互不相同的非0整數(shù)，直到輸入0時(shí)停止。將輸入的所有非0整數(shù)按 輸入次序插入二叉排序樹(shù)（初始時(shí)是空樹(shù)）。插入某個(gè)非0整數(shù)時(shí)，若該整數(shù)已在二叉排序樹(shù)中，則插入該整數(shù)失?。☉?yīng)顯示提示信息）。 全部整數(shù)插入結(jié)束后，顯示成功插入的整數(shù)個(gè)數(shù)。刪除元素輸入一個(gè)整數(shù)，若它在二叉排序樹(shù)中，則刪除它（提示刪除成功與失?。?。輸出輸出二叉排序樹(shù)的先序和中序遞歸遍歷結(jié)點(diǎn)訪(fǎng)問(wèn)次序。結(jié)束程序?qū)嶒?yàn)?zāi)康模赫莆斩媾判驑?shù)插入、刪除元素的基本算法。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)簡(jiǎn)要描述:采用單向二叉鏈表存儲(chǔ)二

2、叉排序樹(shù)，結(jié)點(diǎn)采用結(jié)構(gòu)體存儲(chǔ)，該結(jié)構(gòu)體包含兩個(gè)整型數(shù)據(jù)域， 兩個(gè)結(jié)構(gòu)體本身類(lèi)型的指針域，結(jié)構(gòu)如下：typedef struct node（KeyTp K; /關(guān)鍵字ElemTp data; /數(shù)據(jù)域struct node *lchild, *rchild; /左、右兒子指針BSTNode, *BST;算法設(shè)計(jì)簡(jiǎn)要描述：插入結(jié)點(diǎn)算法：插入結(jié)點(diǎn)時(shí)，先將待插入的結(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)比較大小，若關(guān)鍵字大于當(dāng)前結(jié)點(diǎn)則遍歷 指針指向當(dāng)前結(jié)點(diǎn)的右兒子，再與右兒子比較大小；若關(guān)鍵字小于當(dāng)前結(jié)點(diǎn)，遍歷指針指 向當(dāng)前結(jié)點(diǎn)的左兒子。循環(huán)執(zhí)行該步驟，直至遍歷指針指向的地址為空。則查找到了合適的位置，記錄父母 指針，若待插入

3、的結(jié)點(diǎn)關(guān)鍵字大于父母指針，則帶插入結(jié)點(diǎn)作為右兒子，否則為左兒子。樹(shù)為空時(shí)直接作為根結(jié)點(diǎn)。刪除結(jié)點(diǎn)算法：已知bt為根結(jié)點(diǎn)地址，？為待刪除的結(jié)點(diǎn)，f為待刪除的結(jié)點(diǎn)的父母指針。Pl指向p 的左兒子，pr指向右兒子，s指向pl。刪除p，若pl不為空，pr為空，s指向pl；若？】為空，pr不為空，s指向pr。若pr和pl都不為空，查找pl為根結(jié)點(diǎn)的最后一個(gè)右兒子(ps=s; s=s-rchild;)。ps為s的雙親結(jié)點(diǎn)。孤立s結(jié)點(diǎn)，若ps為空，則pl指向s的左兒子；否則ps的右 兒子指向s的左兒子。找到pl，pr作為s的左右兒子。若p為f的左兒子，則f的左兒子指向s；若p為f的右兒子，則f的右兒子指向s

4、。輸入/輸出設(shè)計(jì)簡(jiǎn)要描述：插入元素時(shí)需輸入插入的元素的關(guān)鍵字，以空格分隔，輸入0時(shí)結(jié)束輸入。刪除元素時(shí)輸入刪除元素的關(guān)鍵字。執(zhí)行輸出時(shí)輸出二叉排序樹(shù)的先序遍歷和中序遍歷。輸入輸出均與提示信息。編程語(yǔ)言說(shuō)明：使用Visual C+編程。主要代碼采用C語(yǔ)言實(shí)現(xiàn)；動(dòng)態(tài)存儲(chǔ)分配采用C+的new和 delete操作符實(shí)現(xiàn)；輸入與輸出采用C+的cin和cout流；程序注釋采用C/C+規(guī)范。主要函數(shù)說(shuō)明：BST search(BST bt, KeyTp key) 遞歸查找算法int insert(BST &bt, BST p) /二叉排序樹(shù)插入結(jié)點(diǎn)算法void CrtBst(BST &bt) 二叉排序樹(shù)的建

5、立方法，從空樹(shù)開(kāi)始，反復(fù)插入新結(jié)點(diǎn)void delNode(BST &bt, KeyTp key) 刪除結(jié)點(diǎn)void preorder(BST bt) /先序遍歷void midorder(BST bt) 中序遍歷程序測(cè)試簡(jiǎn)要報(bào)告：插入元素：4 5 1 3 2 1 1 2 1輸出：3金. fl害+-!- 一浣：刪除元素：1輸出:插入元素：1源程序代碼：#include#include#include#include/#include using namespace std;typedef int KeyTp;typedef int ElemTp;typedef struct node(KeyT

6、p K; 關(guān)鍵字ElemTp data; /數(shù)據(jù)域struct node *lchild, *rchild; /左、右兒子指針 BSTNode, *BST;遞歸算法BST search(BST bt, KeyTp key) (if(bt=NULL|bt-K=key)return bt;if(keyK)return search(bt-lchild, key);return search(bt-rchild, key);/二叉排序樹(shù)插入結(jié)點(diǎn)算法int insert(BST &bt, BST p)(BST parent,pt;parent=NULL;pt=bt;while(pt)(parent=p

7、t;if(p-K K)pt=pt-lchild;else if(p-K pt-K)pt=pt-rchild;elsereturn 0;if(parent)(if(p-K K)parent-lchild=p;elseparent-rchild=p;elsebt=p; /空樹(shù)插入第一個(gè)結(jié)點(diǎn)*preturn 1;二叉排序樹(shù)的建立方法void CrtBst(BST &bt) /從空樹(shù)開(kāi)始，反復(fù)插入新結(jié)點(diǎn) (BST p;KeyTp Ki;cinKi;int i = 0;while(Ki!=0)(p = new BSTNode;p-K = Ki;p-lchild = NULL;p-rchild = NUL

8、L;if(insert(bt, p)i+；elsecoutKi已存在,插入失敗!Ki;cout插入了 i個(gè)元素K)(f=p;if(keyK)p=p-lchild;elsep=p-rchild;if(!p) 查找失敗，直接結(jié)束(cout該結(jié)點(diǎn)不存在，刪除失敗!lchild;pr=p-rchild;if(pl&pr)(ps=NULL; s=pl;while(s-rchild)(ps=s;s=s-rchild;if(!ps)pl=s-lchild;else ps-rchild=s-lchild;s-lchild=pl;s-rchild=pr;else if(pl)s=pl;elses=pr;if(!

9、f)bt=s;else if(f-lchild=p)f-lchild=s;elsef-rchild=s;delete p; 刪除*?cout刪除關(guān)鍵字key成功endl;先序遍歷void preorder(BST bt)(if(bt)(coutKlchild);preorder(bt-rchild);中序遍歷void midorder(BST bt)(if(bt)(midorder(bt-lchild);coutKrchild);void main()(BST bt;bt = NULL;KeyTp delKey;char flag;coutendl;cout1、插入元素endl;cout2、刪除元素endl;cout3、輸出endl;cout4、清除屏幕endl;cout5、退出程序endl;coutendl;coutflag;switch(flag)(case 1:(cout請(qǐng)輸入待插入的元素(0結(jié)束):;CrtBst(bt);break;case 2:(coutendldelKey;delNode(bt, delKey);break;case 3:(coutendl先序遍歷:； preorder(bt);coutendl中序遍歷:；midorder(bt);bre