Posted on 2012-10-16 23:47
hoshelly 阅读(1529)
评论(0) 编辑 收藏 引用 所属分类:
Programming 、
DS && Algorithm
二叉树可以采用数组的方法进行存储，把数组中的数据依次自上而下,自左至右存储到二叉树结点中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点就在数组中用0来表示
结点存储的数据均为非负整数
Input
第一行输入一个整数t，表示有t个二叉树
第二行起，每行输入一个数组，先输入数组长度，再输入数组内数据，每个数据之间用空格隔开，输入的数据都是非负整数
连续输入t行
Output
每行输出一个示例的先序遍历结果，每个结点之间用空格隔开
Sample Input
3
3 1 2 3
5 1 2 3 0 4
13 1 2 3 4 0 5 6 7 8 0 0 9 10
Sample Output
1 2 3
1 2 4 3
1 2 4 7 8 3 5 9 10 6
分析：这道题的关键在于：设定数组位置从1开始编号，那么位置为i的结点，它的左孩子在数组的位置是2i，右孩子在数组的位置是2i+1
这道题的难点在把树建立起来，其他都容易。
代码：
#include <iostream>
using namespace std;
class BiTreeNode
{
private:
BiTreeNode *leftChild; //左子树指针
BiTreeNode *rightChild; //右子树指针
public:
int data; //数据域
//构造函数和析构函数
BiTreeNode():leftChild(NULL), rightChild(NULL){}
BiTreeNode(int item, BiTreeNode *left = NULL,
BiTreeNode *right = NULL):
data(item), leftChild(left), rightChild(right){}
~BiTreeNode(){}
BiTreeNode * &Left(void) //注意返回值类型为指针的引用类型
{return leftChild;}
BiTreeNode * &Right(void) //注意返回值类型为指针的引用类型
{return rightChild;}
};
class BiTree
{
private:
BiTreeNode *root; //根结点指针
int i,len; //len是树结点的数量
void Destroy(BiTreeNode * &t);
void PreOrder(BiTreeNode * &t);
void CreateBiTree(BiTreeNode * &T,const int arrTree[],int pos);
public:
//构造函数和析构函数
BiTree(void):root(NULL),i(0){}; //构造函数
~BiTree(void){}; //析构函数
//构造二叉树
void MakeTree(const int arrTree[],int num); //构造二叉树，利用先序遍历结果建树
void Destroy(void); //销毁二叉树
void PreOrder(); //前序遍历
};
//2、定义销毁函数
void BiTree ::Destroy(void) //销毁二叉树，公有函数
{
Destroy(root);
}
void BiTree ::Destroy(BiTreeNode * &t)
//销毁二叉树，私有函数供共有函数调用
{
if(t != NULL && t->Left() != NULL)
Destroy(t->Left());
if(t != NULL && t->Right() != NULL)
Destroy(t->Right());
if(t != NULL)
{
delete t;
}
}
//3、定义建树函数
void BiTree::MakeTree(const int arrTree[],int num)
//构造二叉树，利用先序遍历结果建树，公有函数
{
i=0;
len = num;
CreateBiTree(root,arrTree,1);//数组位置从1开始
}
void BiTree::CreateBiTree(BiTreeNode * &T, const int arrTree[],int pos) //递归建树私有函数
{
int ch;
ch=arrTree[pos];
if (ch == 0 || pos > len) T = NULL;
else
{
T=new BiTreeNode();
T->data = ch; // 生成根结点
i++;
if(i>len) return;
CreateBiTree(T->Left(), arrTree,2*pos); // 构造左子树
CreateBiTree(T->Right(), arrTree,2*pos+1); // 构造右子树
}
}
//4、定义先序遍历函数
void BiTree::PreOrder()
//前序遍历访问二叉树，公有函数
{
PreOrder(root);
}
void BiTree::PreOrder(BiTreeNode* &t)
//前序遍历访问二叉树，私有函数t
{
if(t!=NULL)//若二叉树结点不为空，执行如下操作：
{
cout<<t->data<<" ";//1、输出当前结点的数据，表示该结点被访问了
PreOrder(t->Left());//2、先序遍历该结点的左孩子
PreOrder(t->Right());//3、先序遍历该结点的右孩子
}
}
int main()
{
int m,i,j,k;
int *arrTree;
BiTree myTree;
cin>>m;
for(i=0;i<m;i++)
{
arrTree = new int[800];
cin>>k;
for(j=1;j<=k;j++)
cin>>arrTree[j];
myTree.MakeTree(arrTree,k);
myTree.PreOrder();
cout<<endl;
delete []arrTree;
myTree.Destroy();
}
return 0;
}