树的生成与遍历

上次，应聘兼职时，他们给了我一些题目，其中的一道是，给我们一些数据，让我们生成树，并进行先，中，后序遍历！！

有问题的请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

　　 CreateTree(left,left_data,mid);

//右子树的递归

　　 for(i=0;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

　　 data[i]=i;

　　 T->CreateTree(data,N);

　　 T->FirstSearch();

　　 cout<

　　 T->MidSearch();

　　 cout<

　　 T->LastSearch();

　　}