Visual Studio下实现二叉排序树及其操作

                                 数据结构课程设计
一、  程序运行环境：整个程序在Visual Sdudio 2005 的可视化环境中运行及实现。
二、  编译运行步骤：程序一开始调用菜单函数Menu1()，用以告诉用户使用这个软件的方法及步骤。然后调用菜单函数Menu2()，用户便可以按照提示及说明进行操作。
三、  程序功能说明：在菜单提示中可以得知，当选择'1'时，可以创建一棵二叉排序树，输入的数据会依次插入到树中；当选择'2'时，可以插入节点，实现节点的随时增加；当选择'3'时，可以删除不需要的节点，实现节点的随时删减；当选择'4'时，可以查找某个或多个数据是否存在于二叉排序树中；当输入其他不正确的选择时，会提示“输入错误”，并重新输入选择；当输入#时，就可以退出整个程序。
四、  源程序如下
#include "stdafx.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class Type> class BSTree;//二叉排序树的前视觉定义
template<class Type>
class BSTreeNode//二叉排序树节点类的定义
{
friend class BSTree<Type>;//友元函数
public:
BSTreeNode():leftChild(NULL),rightChild(NULL){}//构造空节的构造函数
BSTreeNode(const Type d,BSTreeNode<Type> *lp=NULL,BSTreeNode<Type> *rp=NULL):data(d),leftChild(lp),rightChild(rp){}//构造非空节点
~BSTreeNode(){}//析构函数
Type GetData() const{return data;}//取节点数据
BSTreeNode<Type> *GetLeftChild() const{return leftChild;}//取左指针
BSTreeNode<Type> *GetRightChild() const{return rightChild;}//取右指针
void SetData(const Type &d){data=d;}//设置节点数据
void SetLeftChild(BSTreeNode<Type> *p){leftChild=p;}//设置左指针
void SetRightChild(BSTreeNode<Type> *p){rightChild=p;}//设置右指针
private:
Type data;
BSTreeNode<Type> *leftChild,*rightChild; //左右指针声明
};
template<class Type>
class BSTree//二叉排序树类的定义

{
public:
BSTree():root(NULL){}//构造空树
~BSTree(){destroy(root);}//析构函数
BSTreeNode<Type> *Find(const Type &k)const{return Find(k,root);}//查找函数，看某个节点是否存在
BSTreeNode<Type> * Min(BSTreeNode<Type> *p);//找最小节点
BSTreeNode<Type> * Max(BSTreeNode<Type> *p);//找最大节点
void Insert(const Type &x){Insert(x,root);}//插入节点
void Delete(const Type &k){ Delete(k,root);}//删除节点
    int IsEmpty(){return root==NULL?1:0;}//判断树是否为空
BSTreeNode<Type> *Root(){return root;}//返回树根节点
void SetRoot(BSTreeNode<Type> *p){root=p;}
BSTreeNode<Type> *Parent(BSTreeNode<Type> *p){return Parent(root,p);}
void CreatRoot(Type d){root=new BSTreeNode<type>(d);}//建立一棵二叉排序树的根节点
    BSTreeNode<Type> *LeftChild(BSTreeNode<Type> *p){return p==NULL?NULL:p->GetLeftChild();}//返回左指针
    BSTreeNode<Type> *RightChild(BSTreeNode<Type> *p){return p==NULL?NULL:p->GetRightChild();}//返回右指针
Type Retrieve(BSTreeNode<Type> *p){return p->GetData();}//获取节点数据
void Assign(BSTreeNode<Type> *p,Type d){p->SetData(d);}//设置节点数据
void PreOrder(BSTreeNode<Type> *r);//前序遍历
void InOrder(BSTreeNode<Type> *r);//中序遍历
void PostOrder(BSTreeNode<Type> *r);//后序遍历
void CreatBSTree();//建立一棵二叉排序树
void Menu1();//菜单函数，用于说明如何操作
void Menu2();//菜单函数，用于实现各种操作
int IsInt(int p);
private:
BSTreeNode<Type> *root;//根节点
BSTreeNode<Type> *Parent(BSTreeNode<Type> *start,BSTreeNode<Type> *p);
void destroy(BSTreeNode<Type> *p);//释放内存
BSTreeNode<Type> *Find(const Type &k,BSTreeNode<Type> *p)const;//在以p为根的树上查找k是否存在