二叉樹(shù)可以采用數(shù)組的方法進(jìn)行存儲(chǔ)，把數(shù)組中的數(shù)據(jù)依次自上而下,自左至右存儲(chǔ)到二叉樹(shù)結(jié)點(diǎn)中，一般二叉樹(shù)與完全二叉樹(shù)對(duì)比，比完全二叉樹(shù)缺少的結(jié)點(diǎn)就在數(shù)組中用0來(lái)表示
結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)均為非負(fù)整數(shù)
Input
第一行輸入一個(gè)整數(shù)t，表示有t個(gè)二叉樹(shù)
第二行起，每行輸入一個(gè)數(shù)組，先輸入數(shù)組長(zhǎng)度，再輸入數(shù)組內(nèi)數(shù)據(jù)，每個(gè)數(shù)據(jù)之間用空格隔開(kāi)，輸入的數(shù)據(jù)都是非負(fù)整數(shù)
連續(xù)輸入t行
Output
每行輸出一個(gè)示例的先序遍歷結(jié)果，每個(gè)結(jié)點(diǎn)之間用空格隔開(kāi)
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
分析：這道題的關(guān)鍵在于：設(shè)定數(shù)組位置從1開(kāi)始編號(hào)，那么位置為i的結(jié)點(diǎn)，它的左孩子在數(shù)組的位置是2i，右孩子在數(shù)組的位置是2i+1
這道題的難點(diǎn)在把樹(shù)建立起來(lái)，其他都容易。
代碼：
#include <iostream>
using namespace std;
class BiTreeNode
{
private:
BiTreeNode *leftChild; //左子樹(shù)指針
BiTreeNode *rightChild; //右子樹(shù)指針
public:
int data; //數(shù)據(jù)域
//構(gòu)造函數(shù)和析構(gòu)函數(shù)
BiTreeNode():leftChild(NULL), rightChild(NULL){}
BiTreeNode(int item, BiTreeNode *left = NULL,
BiTreeNode *right = NULL):
data(item), leftChild(left), rightChild(right){}
~BiTreeNode(){}
BiTreeNode * &Left(void) //注意返回值類(lèi)型為指針的引用類(lèi)型
{return leftChild;}
BiTreeNode * &Right(void) //注意返回值類(lèi)型為指針的引用類(lèi)型
{return rightChild;}
};
class BiTree
{
private:
BiTreeNode *root; //根結(jié)點(diǎn)指針
int i,len; //len是樹(shù)結(jié)點(diǎn)的數(shù)量
void Destroy(BiTreeNode * &t);
void PreOrder(BiTreeNode * &t);
void CreateBiTree(BiTreeNode * &T,const int arrTree[],int pos);
public:
//構(gòu)造函數(shù)和析構(gòu)函數(shù)
BiTree(void):root(NULL),i(0){}; //構(gòu)造函數(shù)
~BiTree(void){}; //析構(gòu)函數(shù)
//構(gòu)造二叉樹(shù)
void MakeTree(const int arrTree[],int num); //構(gòu)造二叉樹(shù)，利用先序遍歷結(jié)果建樹(shù)
void Destroy(void); //銷(xiāo)毀二叉樹(shù)
void PreOrder(); //前序遍歷
};
//2、定義銷(xiāo)毀函數(shù)
void BiTree ::Destroy(void) //銷(xiāo)毀二叉樹(shù)，公有函數(shù)
{
Destroy(root);
}
void BiTree ::Destroy(BiTreeNode * &t)
//銷(xiāo)毀二叉樹(shù)，私有函數(shù)供共有函數(shù)調(diào)用
{
if(t != NULL && t->Left() != NULL)
Destroy(t->Left());
if(t != NULL && t->Right() != NULL)
Destroy(t->Right());
if(t != NULL)
{
delete t;
}
}
//3、定義建樹(shù)函數(shù)
void BiTree::MakeTree(const int arrTree[],int num)
//構(gòu)造二叉樹(shù)，利用先序遍歷結(jié)果建樹(shù)，公有函數(shù)
{
i=0;
len = num;
CreateBiTree(root,arrTree,1);//數(shù)組位置從1開(kāi)始
}
void BiTree::CreateBiTree(BiTreeNode * &T, const int arrTree[],int pos) //遞歸建樹(shù)私有函數(shù)
{
int ch;
ch=arrTree[pos];
if (ch == 0 || pos > len) T = NULL;
else
{
T=new BiTreeNode();
T->data = ch; // 生成根結(jié)點(diǎn)
i++;
if(i>len) return;
CreateBiTree(T->Left(), arrTree,2*pos); // 構(gòu)造左子樹(shù)
CreateBiTree(T->Right(), arrTree,2*pos+1); // 構(gòu)造右子樹(shù)
}
}
//4、定義先序遍歷函數(shù)
void BiTree::PreOrder()
//前序遍歷訪問(wèn)二叉樹(shù)，公有函數(shù)
{
PreOrder(root);
}
void BiTree::PreOrder(BiTreeNode* &t)
//前序遍歷訪問(wèn)二叉樹(shù)，私有函數(shù)t
{
if(t!=NULL)//若二叉樹(shù)結(jié)點(diǎn)不為空，執(zhí)行如下操作：
{
cout<<t->data<<" ";//1、輸出當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)，表示該結(jié)點(diǎn)被訪問(wèn)了
PreOrder(t->Left());//2、先序遍歷該結(jié)點(diǎn)的左孩子
PreOrder(t->Right());//3、先序遍歷該結(jié)點(diǎn)的右孩子
}
}
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;
}