樹的生成與遍歷

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++——二叉樹