树的生成与遍历

2019-11-17 05:47:55

字体：大中小

来源：转载

供稿：网友

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

上一篇：双人黑白棋子游戏

下一篇：数据结构学习C++——二叉树

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注