．[題目分析]本題靜態鏈表中結點是按動態二叉鏈表的前序遍歷順序存放的首先對動態二叉鏈表的二叉樹進行前序遍歷填寫靜態鏈表的下標和data域再對動態二叉鏈表的二叉樹進行層次遍歷設隊列Q填寫靜態鏈表的lchild域和rchild域
typedef struct node //靜態鏈表結點結構
{ElemType data; //結點數據
int rowlchildrchild ; //下標左右子女
}component
component st[]; //st容量足夠大
struct node {BiTree t; int idx; }qbt;
static int num=;
void PreOrder(BiTree bt);
// 前序遍歷二叉樹填寫靜態鏈表的下標和data域
{if (bt)
{st[++num]data=bt>data; st[num]row=num;
PreOrder(bt>lchild); PreOrder(bt>rchild);
} }
int Locate(ElemType x)
//在靜態鏈表中查二叉樹結點的下標
{for (i=;i<=num;i++) if (st[i]data==x) return (i);
}
void DynaToST (BiTree bt) //將二叉樹的動態二叉鏈表結構轉為靜態鏈表結構
{int i=; //i為靜態鏈表st的下標
if (bt!=null)
{QueueInit(Q); //Q是隊列容量足夠大隊列元素是qbt
qbtt=bt; qbtidx=; QueueIn(Qqbt); st[]data=bt>data;
while(!QueueEmpty(Q))
{qbt=QueueOut(Q); //出隊列
p=qbtt; i=qbtidx; //二叉樹結點及在靜態鏈表中的下標
if (p>lchild!=null) //若左子女存在查其在靜態鏈表中的下標 填lchild域值
{lch=Locate(p>lchild>data)st[i]lchild=lch;
qbtt=p>lchild; qbtidx=lch; QueueIn(Qqbt); }
else st[i]lchild=; //無左子女其lchild域填
if (p>rchild!=null) //若右子女存在查其在靜態鏈表中的下標填rchild域值
{rch=Locate(p>>rchild>data)st[i]rchild=rch;
qbtt=p>rchild; qbtidx=rch; QueueIn(Qqbt); }
else st[i]rchild=; //無左子女其lchild域填
}//while
}//結束DynaToST
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23738.html
