树的生成与遍历

来源：作者：出处：巧巧读书 2006-11-13 进入讨论组

关键词：

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

有问题的请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();
}