二叉排序树的实现 一、 实验内容与要求 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 name...
VIP
