二叉排序树节点插入和删除实验设计报告(用C语言实现).docx

二叉排序树节点的插入和删除实验设计报告 1程序功能描述： 用二叉树的所学知识建立二叉排序树，对已建立的排序二叉树进行遍历（先序，中序，后序），插入，查找，删除。 2主要数据结构描述： 二叉排序树若不为空树，那么相比于其他的树，它具有一下特性： 1.、左儿子永远小于双亲结点；2、右儿子永远大于双亲结点。 其中结点由一个存放信息的空间和两个指针构成。 3程序结构描述： 以C语言为工具，在主函数外部定义二叉排序树的遍历（先序，中序，后序），插入，删除函数，在主函数中调用，其中主函数中用switch…case…结构，有选择性的进行功能的实现。 4算法描述： 二叉排序树插入结点的算法： 1若建立的二叉排序树中已有与欲插入的数相同的结点则无须插入； 2以while(p)控制循环变量，若欲插入的数比根结点小的话，执行 P=P-lchild;若大于p-data；则执行 P=P-rchild; ，直至p为空。此过程中一直用指针F记录前一步p的位置。 3在第2歩确定了的位置的基础上进行插入，若与插入的数小于F-data，则执行F-lchild=S;若大于F-data，则执行 F-rchild=S; 二叉排序树的建立： 通过对插入函数的调用即 T=InsertBST(T,k)；以while(k!=-1)控制循环，递归的进行插入直至生成二叉排序树。 二叉排序树的遍历算法： 先序遍历：先输出根结点的信息；然后调用函数PreOrderTraverse(T-lchild)，递归的输出左子树的信息；最后调用函数PreOrderTraverse(T-rchild)，递归输出有子树的信息。 中序遍历：先调用函数PreOrderTraverse(T-lchild)，递归的输出左子树的信息；然后输出根结点的信息；最后调用函数PreOrderTraverse(T-rchild)，递归输出有子树的信息。 后序遍历：先调用函数PreOrderTraverse(T-lchild)，递归的输出左子树的信息；然后调用函数PreOrderTraverse(T-rchild)，递归输出有子树的信息，最后输出根结点的信息。 二叉排序树的删除算法： 通过*f,*p,*q,*c;四个指针，先对二叉排序树查找，用f,q指针跟谁p指针，通过q-data=p-data，掩盖与删除的信息;再借助指针c,通过语句 f-lchild=c和free(p)或f-rchild=c和free(p)，删除结点p，此时结点的删除得以实现。 5程序测试方案与测试结果描述： 功能1:二叉树的遍历 输入节点信息：3 6 8 4 1 -1； 先序遍历31648 中序遍历13468 后序遍历14863 截图如下： 功能2：向原有的二叉树中插入一个结点 插入2 插入后遍历如下： 先序遍历：312648 中序遍历：123468 后序遍历：214863 截图如下： 功能3：删除一个结点： 删除4 删除后遍历结果如下： 先序遍历：31268 中序遍历：12368 后序遍历：21863 截图如下： 功能0: 输入0 显示:退出。 截图如下：