#include
using namespace std;
//二叉树结点的ADT
template
class BinNode{
public:
E e;
BinNode* left;
BinNode* right;
BinNode(){
left=right=NULL;
}
BinNode(E ee){
e=ee;
left=right=NULL;
}
BinNode* Left(){
return left;
}
BinNode* Right(){
return right;
}
void setLeft(BinNode* l){
left=l;
}
void setRight(BinNode* r){
right=r;
}
};
//用二叉链表来实现二叉树ADT
template
class BSTNode:public BinNode{
BinNode* root;
public:
BSTNode(){
root=NULL;
}
~BSTNode(){}
BinNode* ROOT() const{ return root;}
//二叉树的构建
void create(E ee){
if(root==NULL)
root=new BinNode(ee);
else{
BinNode *temp;
BinNode *curr;
while(curr!=NULL){
temp=curr;
if(curr->e>ee)
curr=curr->left;
else
curr=curr->right;
}
if(temp->e>ee)
{temp->setLeft(new BinNode(ee));
}
else
temp->setRight(new BinNode<E>(ee));
}
}
//计算二叉树结点的个数
int NodeCount(BinNode<E> *root){
if(root==NULL)
return 0;
else
return 1+NodeCount(root->Left())+NodeCount(root->Right());
}
//打印结点的值
void visit(BinNode<E> *p){
cout<<p->e<<" ";
}
//先序遍历二叉树
void Preorder(BinNode<E> *root){
if(root==NULL) return;
visit(root);
Preorder(root->left);
Preorder(root->right);
}
//中序遍历二叉树
void inorder(BinNode<E> *root){
if(root==NULL) return;
inorder(root->left);
visit(root);
inorder(root->right);
}
//后序遍历二叉树
void Postorder(BinNode<E> *root){
if(root==NULL) return;
Postorder(root->left);
Postorder(root->right);
visit(root);
}
};
int main(){
BSTNode tree1;
BSTNode tree2;
int a[9]={37,24,42,7,2,40,42,32,120};
int b[9]={120,42,42,7,2,32,37,24,40};
int i;
for(i=0;i<9;i++){
tree1.create(a[i]);
}
for(i=0;i<9;i++){
tree2.create(b[i]);
}
cout<<"第一棵二叉树的结点个数为:"<<tree1.NodeCount(tree1.ROOT())<<endl;
cout<<"第一棵二叉树的先序遍历序列为:";
tree1.Preorder(tree1.ROOT());
cout<<endl;
cout<<"第一棵二叉树的中序遍历序列为:";
tree1.inorder(tree1.ROOT());
cout<<endl;
cout<<"第一棵二叉树的后序遍历序列为:";
tree1.Postorder(tree1.ROOT());
cout<<endl;
cout<<"第二棵二叉树的结点个数为:"<<tree2.NodeCount(tree2.ROOT())<<endl;
cout<<"第二棵二叉树的先序遍历序列为:";
tree2.Preorder(tree2.ROOT());
cout<<endl;
cout<<"第二棵二叉树的中序遍历序列为:";
tree2.inorder(tree2.ROOT());
cout<<endl;
cout<<"第二棵二叉树的后序遍历序列为:";
tree2.Postorder(tree2.ROOT());
return 0;
}