树的生成与遍历

核心提示： 上次，应聘兼职时，树的生成与遍历，他们给了我一些题目，其中的一道是，右边的为右子树#include "iostream.h"#include "stdio.h"#include "stdlib.h"#include "string.h"

  上次，应聘兼职时，他们给了我一些题目，其中的一道是，给我们一些数据，让我们生成树，并进行先，中，后序遍历！！ 有问题的请E-mail:cangzhu@163.com 我的这样做的 ： //建立树的方法是，取数组的中间的数为树根，左边的为左子树，右边的为右子树 #include "iostream.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define N 10 //节点类
class BNode
{
public:
 int data;
 BNode *lchild;
 BNode *rchild;  BNode()
　
}; //二叉树类
class BTree
{
PRivate:
 BNode *root;
public:
 //构造函数
 BTree();
 //析构函数
 ~BTree();  //树的销毁
 void Destroy(BNode *node);
 
 //生成树
 bool CreateTree(BNode *node,int data[],int len);
 bool CreateTree(int data[],int len);  //遍历
 //先序
 void FirstSearch(BNode *node);
 void FirstSearch();
 
 //中序
 void MidSearch(BNode *node);
 void MidSearch();
 
 //后序
 void LastSearch(BNode *node);
 void LastSearch();
}; //构造函数
BTree::BTree()
{ 
 root=new BNode();
} //默认的析构函数
BTree::~BTree()
//树的销毁
void BTree::Destroy(BNode *node)
{
 if(!node)
　return;  delete node; 
 FirstSearch(node->lchild);
 FirstSearch(node->rchild);
} //递归的生成树
bool BTree::CreateTree(BNode *node,int data[N],int len)
{
 int i;　
 BNode *left=new BNode();
 BNode *right=new BNode();  //分割后，只剩一个数据
 if(len==1)
 {
　node->data=data[0];
　return true;
 }
 //分割后，只剩两个数据
 if(len==2)
 {
　node->data=data[1]; 　left=new BNode();
　left->data=data[0]; 　node->lchild=left;
　node->rchild=NULL;
　return true;
 }  //大于等于三个数据
 int mid=(int)(len/2);
 node->data=data[mid];
 node->lchild=left;
 node->rchild=right;  //左边的数据，右边的数据
 int left_data[N];
 int right_data[N];  //左子树的递归
 for(i=0;i<mid;i++)
 
 CreateTree(left,left_data,mid);  //右子树的递归
 for(i=0;i<len-mid-1;i++)
 
 CreateTree(right,right_data,len-mid-1);  return true;
} //生成树的函数
bool BTree::CreateTree(int data[N],int len)
{
 return CreateTree(root,data,len);
} //先序遍历
void BTree::FirstSearch(BNode *node)
{
 if(!node)
　return;  printf("%d ",node->data); 
 FirstSearch(node->lchild);
 FirstSearch(node->rchild);
}
void BTree::FirstSearch()
//中序遍历
void BTree::MidSearch(BNode *node)
{
 if(!node)
　return;   MidSearch(node->lchild);
 printf("%d ",node->data);
 MidSearch(node->rchild);
} void BTree::MidSearch()
//后序遍历
void BTree::LastSearch(BNode *node)
{
 if(!node)
　return;  LastSearch(node->lchild);
 LastSearch(node->rchild);
 printf("%d ",node->data);
} void BTree::LastSearch()
//测试函数
void main()
{
 BTree *T=new BTree();
 int data[N];
 for(int i=0;i<N;i++)
　data[i]=i;
 T->CreateTree(data,N); 
 T->FirstSearch();
 cout<<endl;
 T->MidSearch();
 cout<<endl;
 T->LastSearch();
}