排序二叉树的遍历（递归非递归都行）

Question

输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。
要求：1.用菜单实现
2.能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。

很急啊～～～各位大侠们帮帮忙啊～～～
一楼给的那个不能用菜单实现吧？
对数据结构掌握得比较好的大侠们一定要帮帮忙啊～～～

Answer 1

***********************main*************************
#include<iostream>
#include<cstdlib>
#include<ctime>
#include"BST_tree.h"
#include"BST_tree.cpp"
using namespace std;
int main()
{
BST_tree<int> temp;
srand(clock()%1000);
for(int i=0;i<6;i++)
temp.add_node(rand()%43);

temp.mid_order_tree();
cout<<endl;

temp.delete_node(29);//删除结点操作
temp.mid_order_tree();//中序

temp.pre_order_tree();//前序
temp.post_order_tree();//后序

return 0;
}
****************************BST_tree.h*****************************
#ifndef _BST_TREE_
#define _BST_TREE_
#include<iostream>
using namespace std;
#define PRA 1
#define SON 0
template <class T>
class BST_tree_node
{
public:
T key;
BST_tree_node* rchild;
BST_tree_node* lchild;
BST_tree_node(T key):key(key),lchild(NULL),rchild(NULL)
{}
};
template <class T>
class BST_tree
{
public:
BST_tree_node<T> *root;
int nodes_num;

BST_tree():root(NULL),nodes_num(0)
{}

BST_tree_node<T> * search_node(T key,bool lag);
void add_node(T key);
void delete_node(T key);
void delete_tree(BST_tree_node<T> *root);
void Mid_Order_Tree(BST_tree_node<T>*root);
void mid_order_tree()
{
Mid_Order_Tree(root);
cout<<endl;
}
void Pre_Order_Tree(BST_tree_node<T>*root);
void pre_order_tree()
{
Pre_Order_Tree(root);
cout<<endl;
}
void Post_Order_Tree(BST_tree_node<T>*root);
void post_order_tree()
{
Post_Order_Tree(root);
cout<<endl;
}
~BST_tree()
{delete_tree(root);}
};
#endif
*********************************BST_tree.cpp**********************
#include"BST_tree.h"

template<class T>
void BST_tree<T>::add_node(T key)
{
nodes_num++;
BST_tree_node<T> *r=root;
if(root==NULL)
root=new BST_tree_node<T>(key);//new 的时候也得加上T
else
{
BST_tree_node<T> *pre=NULL;//in order to make it clear
while(r!=NULL)//不晓得循环条件，暂时，可以用break；
{
pre=r;
if(r->key<key)
r=r->rchild;
else r=r->lchild;
}
if(pre->key<key)
pre->rchild=new BST_tree_node<T>(key);
else pre->lchild=new BST_tree_node<T>(key);
}
}
template <class T>
void BST_tree<T>::Mid_Order_Tree(BST_tree_node<T>*root)
{
if(root!=NULL)
{

Mid_Order_Tree(root->lchild);
cout<<root->key<<' ';
Mid_Order_Tree(root->rchild);
}
}
template <class T>
void BST_tree<T>::delete_tree(BST_tree_node<T> *root)
{
if(root!=NULL)
{
delete_tree(root->lchild);
delete_tree(root->rchild);
delete root;
}
}

//primary text succese error 1 :min_order_traverse error 2 :forget T when new a node.
template <class T>
BST_tree_node<T> * BST_tree<T>::search_node(T key,bool lag)
{
BST_tree_node<T>*r=root,*pre=NULL;
while(r!=NULL)
{
if(r->key>key)
{
pre=r;
r=r->lchild;
}
else if(r->key<key)
{
pre=r;
r=r->rchild;
}
else return lag==SON?r:pre;
}
cout<<"can not find what you want"<<endl;
return NULL;
}
template <class T>
void BST_tree<T>::delete_node(T key)
{
BST_tree_node<T>*r=search_node(key,SON);
if(r==NULL)return ;
BST_tree_node<T>*temp=r,*pre=r;
if(r->lchild==NULL&&r->rchild==NULL)
{
temp=search_node(key,PRA);
if(temp->key>key) temp->lchild=NULL;
else temp->rchild=NULL;
delete r;
}
else if(r->lchild!=NULL)
{
r=r->lchild;
if(r->rchild==NULL)
{
pre->lchild=r->lchild;
temp->key=r->key;
delete r;
}
else {
while(r->rchild!=NULL)
{
pre=r;
r=r->rchild;
}
temp->key=r->key;
pre->rchild=r->lchild;
delete r;
}
}
else if(r->rchild!=NULL)
{
r=r->rchild;
if(r->lchild==NULL)
{
pre->rchild=r->rchild;
temp->key=r->key;
delete r;
}
else {
while(r->lchild!=NULL)
{
pre=r;
r=r->lchild;
}
temp->key=r->key;
pre->lchild=r->rchild;
delete r;
}
}
}

template<class T>
void BST_tree<T>::Pre_Order_Tree(BST_tree_node<T> *root)
{
if(root!=NULL)
{
cout<<root->key<<' ';
Pre_Order_Tree(root->lchild);
Pre_Order_Tree(root->rchild);
}
}
template<class T>
void BST_tree<T>::Post_Order_Tree(BST_tree_node<T> *root)
{
if(root!=NULL)
{
Pre_Order_Tree(root->lchild);
cout<<root->key<<' ';
Pre_Order_Tree(root->rchild);
}
}

Answer 2

#include<iostream>
#include<cstdlib>
#include<ctime>
#include"BST_tree.h"
#include"BST_tree.cpp"
using namespace std;
int main()
{
BST_tree<int> temp;
srand(clock()%1000);
for(int i=0;i<6;i++)
temp.add_node(rand()%43);

temp.mid_order_tree();
cout<<endl;

temp.delete_node(29);//删除结点操作
temp.mid_order_tree();//中序

temp.pre_order_tree();//前序
temp.post_order_tree();//后序

return 0;
}
****************************BST_tree.h*****************************
#ifndef _BST_TREE_
#define _BST_TREE_
#include<iostream>
using namespace std;
#define PRA 1
#define SON 0
template <class T>
class BST_tree_node
{
public:
T key;
BST_tree_node* rchild;
BST_tree_node* lchild;
BST_tree_node(T key):key(key),lchild(NULL),rchild(NULL)
{}
};
template <class T>
class BST_tree
{
public:
BST_tree_node<T> *root;
int nodes_num;

BST_tree():root(NULL),nodes_num(0)
{}

BST_tree_node<T> * search_node(T key,bool lag);
void add_node(T key);
void delete_node(T key);
void delete_tree(BST_tree_node<T> *root);
void Mid_Order_Tree(BST_tree_node<T>*root);
void mid_order_tree()
{
Mid_Order_Tree(root);
cout<<endl;
}
void Pre_Order_Tree(BST_tree_node<T>*root);
void pre_order_tree()
{
Pre_Order_Tree(root);
cout<<endl;
}
void Post_Order_Tree(BST_tree_node<T>*root);
void post_order_tree()
{
Post_Order_Tree(root);
cout<<endl;
}
~BST_tree()
{delete_tree(root);}
};
#endif
*********************************BST_tree.cpp**********************
#include"BST_tree.h"

template<class T>
void BST_tree<T>::add_node(T key)
{
nodes_num++;
BST_tree_node<T> *r=root;
if(root==NULL)
root=new BST_tree_node<T>(key);//new 的时候也得加上T
else
{
BST_tree_node<T> *pre=NULL;//in order to make it clear
while(r!=NULL)//不晓得循环条件，暂时，可以用break；
{
pre=r;
if(r->key<key)
r=r->rchild;
else r=r->lchild;
}
if(pre->key<key)
pre->rchild=new BST_tree_node<T>(key);
else pre->lchild=new BST_tree_node<T>(key);
}
}
template <class T>
void BST_tree<T>::Mid_Order_Tree(BST_tree_node<T>*root)
{
if(root!=NULL)
{

Mid_Order_Tree(root->lchild);
cout<<root->key<<' ';
Mid_Order_Tree(root->rchild);
}
}
template <class T>
void BST_tree<T>::delete_tree(BST_tree_node<T> *root)
{
if(root!=NULL)
{
delete_tree(root->lchild);
delete_tree(root->rchild);
delete root;
}
}

//primary text succese error 1 :min_order_traverse error 2 :forget T when new a node.
template <class T>
BST_tree_node<T> * BST_tree<T>::search_node(T key,bool lag)
{
BST_tree_node<T>*r=root,*pre=NULL;
while(r!=NULL)
{
if(r->key>key)
{
pre=r;
r=r->lchild;
}
else if(r->key<key)
{
pre=r;
r=r->rchild;
}
else return lag==SON?r:pre;
}
cout<<"can not find what you want"<<endl;
return NULL;
}
template <class T>
void BST_tree<T>::delete_node(T key)
{
BST_tree_node<T>*r=search_node(key,SON);
if(r==NULL)return ;
BST_tree_node<T>*temp=r,*pre=r;
if(r->lchild==NULL&&r->rchild==NULL)
{
temp=search_node(key,PRA);
if(temp->key>key) temp->lchild=NULL;
else temp->rchild=NULL;
delete r;
}
else if(r->lchild!=NULL)
{
r=r->lchild;
if(r->rchild==NULL)
{
pre->lchild=r->lchild;
temp->key=r->key;
delete r;
}
else {
while(r->rchild!=NULL)
{
pre=r;
r=r->rchild;
}
temp->key=r->key;
pre->rchild=r->lchild;
delete r;
}
}
else if(r->rchild!=NULL)
{
r=r->rchild;
if(r->lchild==NULL)
{
pre->rchild=r->rchild;
temp->key=r->key;
delete r;
}
else {
while(r->lchild!=NULL)
{
pre=r;
r=r->lchild;
}
temp->key=r->key;
pre->lchild=r->rchild;
delete r;
}
}
}

template<class T>
void BST_tree<T>::Pre_Order_Tree(BST_tree_node<T> *root)
{
if(root!=NULL)
{
cout<<root->key<<' ';
Pre_Order_Tree(root->lchild);
Pre_Order_Tree(root->rchild);
}
}
template<class T>
void BST_tree<T>::Post_Order_Tree(BST_tree_node<T> *root)
{
if(root!=NULL)
{
);
cout<<root->key<<' ';

}