上次，应聘兼职时，他们给了我一些题目，其中的一道是，给我们一些数据，让我们生成树，并进行先，中，后序遍历！！
有问题的请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();
}
|
