二叉排序树的实现
实验内容与要求
1) 实现二叉排序树，包括生成、插入，删除；
2) 对二叉排序树进行先根、中根、和后根非递归遍历；
3) 每次对树的修改操作和遍历操作的显示结果都需要在屏
幕上用树的形状表示出来。
实验方案
1. 选择链表的方式来构造节点，存储二叉排序树的节点。// 树的结构struct BSTNode {
// 定义左右孩子指针
struct BSTNode *lchild,*rchild;
// 节点的关键字
TElemType key; };
int depth=0;
// 定义一个struct BSTNode 类型的指针typedef BSTNode *Tree;
2. 对树的操作有如下方法：
// 创建二叉排序树
Tree CreatTree(Tree T) ；
// 二叉树的深度，返回一个int 值为该树的深度
int TreeDepth(Tree T)
// 树状输出二叉树，竖向输出
void PrintTree(Tree T , int layer) ；
// 查找关键字，如果关键字存在则返回所在节点的父节点，如果关键字不存在则返回叶子所在的节点
Status SearchBST(Tree T , TElemType key , Tree f,Tree &p) ；
// 向树中插入节点
Status InsertBST(Tree &T , TElemType e) ；
// 删除节点
Status Delete(Tree &T) ；
// 删除指定节点，调用Delete(Tree &T) 方法
Status DeleteData(Tree &T , TElemType key) ；
// 非递归先序遍历void x_print(Tree T);
// 非递归中序遍历
Void z_print(Tree T );
// 非递归后序遍历
void h_print(Tree T);
3. 对二叉排序树非递归先根、中根、后根遍历，采用栈来存储一次遍历过的节点的形式来辅助实现
// 自定义类型以SElemType 作为栈中指针返回的值的类型
// 也就是要返回一个节点的指针
typedef Tree SElemType;
// 栈的结构
struct Stack
{
// 栈底指针SElemType *base;
// 栈顶指针SElemType *top;
// 栈的容量
int stacksize;
};
4. 栈的操作方法：
// 创建一个空栈
Status InitStack(Stack &S) // 获取栈顶元素并删除栈中该位置的元素SElemType Pop(Stack
&S,SElemType &elem)
// 获取栈顶元素返回栈顶元素不对栈做任何修改SElemType getTop(Stack S,SElemType
&elem) // 删除栈顶元素
Status DeleteTop(Stack &S)
// 往栈中压入数据
Status Push(Stack &S,SElemType elem)
// 判断栈是否为空
Status IsEmpty(Stack S)
三、代码实现
#include
#include using namespace std;
// 定义宏#define OK 1 #define ERROR 0
#define STACK_INIT_SIZE 10
#define STACK_INCREMENT 2
// 定义宏分别为栈的初始容量和栈的增加容量#define STACK_INIT_SIZE 10 #define STACK_INCREMENT 2 typedef int TElemType;
// 树的结构
struct BSTNode
{
// 定义左右孩子指针
struct BSTNode *lchild,*rchild;
// 节点的关键字
TElemType key;
};
int depth=0;
// 定义一个struct BSTNode 类型的指针
typedef BSTNode *Tree;
// 自定义类型以SElemType 作为栈中指针返回的值的类型
// 也就是要返回一个节点的指针typedef Tree SElemType;
// 栈的结构
struct Stack
{
// 栈底指针SElemType *base;
// 栈顶指针
SElemType *top;
// 栈的容量
int stacksize;
};
// 自定义类型typedef int Status;
// 创建一个空栈
Status InitStack(Stack &S)
{
// 给栈指针分配空间
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
// 如果分配空间失败则退出if(!S.base)
exit(OVERFLOW);
// 栈底、栈顶指针相等表示栈为空
