二叉排序树插入与删除元素

1、数据结构实验报告知识范畴：查找实验题目：二叉排序树插入与删除元素实验内容及要求：编写控制台应用程序，提供以下菜单项：插入元素从键盘输入若干两两互不相同的非0整数，直到输入0时停止。将输入的所有非0整数按 输入次序插入二叉排序树（初始时是空树）。插入某个非0整数时，若该整数已在二叉排序树中，则插入该整数失败（应显示提示信息）。 全部整数插入结束后，显示成功插入的整数个数。删除元素输入一个整数，若它在二叉排序树中，则删除它（提示删除成功与失败）。输出输出二叉排序树的先序和中序递归遍历结点访问次序。结束程序实验目的：掌握二叉排序树插入、删除元素的基本算法。数据结构设计简要描述:采用单向二叉链表存储二

2、叉排序树，结点采用结构体存储，该结构体包含两个整型数据域， 两个结构体本身类型的指针域，结构如下：typedef struct node（KeyTp K; /关键字ElemTp data; /数据域struct node *lchild, *rchild; /左、右儿子指针BSTNode, *BST;算法设计简要描述：插入结点算法：插入结点时，先将待插入的结点与当前结点比较大小，若关键字大于当前结点则遍历 指针指向当前结点的右儿子，再与右儿子比较大小；若关键字小于当前结点，遍历指针指 向当前结点的左儿子。循环执行该步骤，直至遍历指针指向的地址为空。则查找到了合适的位置，记录父母 指针，若待插入

3、的结点关键字大于父母指针，则带插入结点作为右儿子，否则为左儿子。树为空时直接作为根结点。删除结点算法：已知bt为根结点地址，？为待删除的结点，f为待删除的结点的父母指针。Pl指向p 的左儿子，pr指向右儿子，s指向pl。删除p，若pl不为空，pr为空，s指向pl；若？】为空，pr不为空，s指向pr。若pr和pl都不为空，查找pl为根结点的最后一个右儿子(ps=s; s=s-rchild;)。ps为s的双亲结点。孤立s结点，若ps为空，则pl指向s的左儿子；否则ps的右 儿子指向s的左儿子。找到pl，pr作为s的左右儿子。若p为f的左儿子，则f的左儿子指向s；若p为f的右儿子，则f的右儿子指向s

4、。输入/输出设计简要描述：插入元素时需输入插入的元素的关键字，以空格分隔，输入0时结束输入。删除元素时输入删除元素的关键字。执行输出时输出二叉排序树的先序遍历和中序遍历。输入输出均与提示信息。编程语言说明：使用Visual C+编程。主要代码采用C语言实现；动态存储分配采用C+的new和 delete操作符实现；输入与输出采用C+的cin和cout流；程序注释采用C/C+规范。主要函数说明：BST search(BST bt, KeyTp key) 递归查找算法int insert(BST &bt, BST p) /二叉排序树插入结点算法void CrtBst(BST &bt) 二叉排序树的建

5、立方法，从空树开始，反复插入新结点void delNode(BST &bt, KeyTp key) 删除结点void preorder(BST bt) /先序遍历void midorder(BST bt) 中序遍历程序测试简要报告：插入元素：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; 关键字ElemTp data; /数据域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);/二叉排序树插入结点算法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; /空树插入第一个结点*preturn 1;二叉排序树的建立方法void CrtBst(BST &bt) /从空树开始，反复插入新结点 (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个元素K)(f=p;if(keyK)p=p-lchild;elsep=p-rchild;if(!p) 查找失败，直接结束(cout该结点不存在，删除失败!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删除关键字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请输入待插入的元素(0结束):;CrtBst(bt);break;case 2:(coutendldelKey;delNode(bt, delKey);break;case 3:(coutendl先序遍历:； preorder(bt);coutendl中序遍历:；midorder(bt);bre