二叉排序树的插入与删除

课程设计题目：二叉排序树的插入、删除算法

沈阳航空航天大学课程设计报告

2

沈阳航空航天大学课程设计报告第1章需求分析

1 需求分析

了解二叉排序树组成与其性质，知道其构成。创建一个二叉排序树，并对其先序遍历，输出。然后根据二叉排序树性质，删除，插入，查找其结点与叶子，然后先序遍历输出。

内容：1. 给定一组关键字，生成一棵二叉排序树；

2. 删除该二叉排序树中的指定节点，删除后二叉排序树性质不发生变化； 3. 用直观、易于理解的形式来演示二叉排序树的插入、删除过程。

要求：1、独立完成系统的设计、编码和调试。

2、系统利用C语言实现。

3、按照课程设计规范书写课程设计报告。

4

沈阳航空航天大学课程设计报告第2章系统设计

2系统设计

2.1 数据结构设计

typedefstruct Tree{ int data; struct Tree *lchild, *rchild; }Tree, *PTree;

定义结构体Tree，data：数据，*lchild：指针左孩子，*rchild：指针右孩子 *PTree代表结构体的指针

2.2 函数设计

本系统所设计的函数见表2.1。

表2.1 函数列表

函数名称 main Insert void main(); int Insert(PTree&p, int k) 函数原型 系统主程序 将数据挨个插入到二叉排序树中 创建新的二叉排序树 查找二叉排序树中的数据 在二叉树中插入结点 删除二叉树中的结点 删除结点并重新排序 遍历先序二叉排序树 功能描述 Tree *Create Tree *Create(int A[], int n) search sert DeleteTree f preorder int search(Tree *T, int e, Tree *f, PTree&p) void sert(PTree&T, int e) intDeleteTree(PTree&T, int e) void f(PTree&p) void preorder(Tree *T) 本系统函数的调用关系见图2.1。

5