118.cpp

c++课程习题集的源代码

#include<iostream.h>
class node
{
 friend class tree;
 public:
  node(int x);
  ~node();
 private:
  int data;
  node *left;
  node *right;
};
 class tree
{
 private:
  node *root;
 public:
  tree(void);
  ~tree();
  node* get_r();
  void free_t(node *r);
  void build_t(int d);
  void preorder(node *r);
  void inorder(node *r);
  void postorder(node *r);
  int c_leaf(node *r);
};
 node::node(int x)
{
 data=x;
}
 node::~node()
{
 cout<<"二叉树的结点被析构"<<endl;
}
 tree::tree(void)
{
 root=0;
}
 tree::~tree()
{
 free_t(root);
 cout<<"二叉树被析构"<<endl;
}
 void tree::free_t(node *r)
{
 if(r!=0)
 {
  free_t(r->left);
  free_t(r->right);
  delete r;
 } 
}
 node* tree::get_r()
{
 return(root);
}
 void tree::build_t(int d)
{
 node *p,*q;
 if(root==0)//空树
 {
  root=new node(d);
  root->left=0;
  root->right=0;
 }
 else
 {
  p=root;
  while(p!=0)
  {
   q=p;
   if(d<p->data)
	p=p->left;
   else
	p=p->right;
  }
  node *newp=new node(d);
  newp->left=0;
  newp->right=0;
  if(d<q->data)
   q->left=newp;
  else
   q->right=newp;
 }
}
 void tree::preorder(node *r)//前序遍历
{
 if(r!=0)
 {
  cout<<r->data<<" ";
  preorder(r->left);
  preorder(r->right);
 }
}
 void tree::inorder(node *r)//中序遍历
{
 if(r!=0)
 {
  inorder(r->left);
  cout<<r->data<<" ";
  inorder(r->right);
 }
}
 void tree::postorder(node *r)//后序遍历
{
 if(r!=0)
 {
  postorder(r->left);
  postorder(r->right);
  cout<<r->data<<" ";
 }
}
 int tree::c_leaf(node *r)
{
 int count;
 if(r==0)
  count=0;
 else if(r->left==0&&r->right==0)
  count=1;
 else
  count=c_leaf(r->left)+c_leaf(r->right);  
 return(count);
}
 int main(void)
{
  tree t;
  int count;
  t.build_t(10);
  t.build_t(18);
  t.build_t(32);	
  t.build_t(16);
  t.build_t(3);
  t.build_t(77);	
  t.build_t(200);
  cout<<"中序遍历："<<endl;
  t.inorder(t.get_r());
  cout<<endl;
  count=t.c_leaf(t.get_r());
  cout<<"叶子数："<<count<<endl;
  return(0);
 }