．[題目分析] 二叉樹的層次遍歷序列的第一個結點是二叉樹的根實際上層次遍歷序列中的每個結點都是局部根確定根後到二叉樹的中序序列中查到該結點該結點將二叉樹分為左根右三部分若左右子樹均有則層次序列根結點的後面應是左右子樹的根若中序序列中只有左子樹或只有右子樹則在層次序列的根結點後也只有左子樹的根或右子樹的根這樣定義一個全局變量指針R指向層次序列待處理元素算法中先處理根結點將根結點和左右子女的信息入隊列然後在隊列不空的條件下循環處理二叉樹的結點隊列中元素的數據結構定義如下
typedef struct
{ int lvl; //層次序列指針總是指向當前根結點在層次序列中的位置
int lh; //中序序列的下上界
int f; //層次序列中當前根結點的雙親結點的指針
int lr; // 雙親的左子樹 雙親的右子樹
}qnode;
BiTree Creat(datatype in[]level[]int n)
//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹 n是二叉樹的結點數
{if (n<) {printf(參數錯誤\n); exit();}
qnode sQ[]; //Q是元素為qnode類型的隊列容量足夠大
init(Q); int R=; //R是層次序列指針指向當前待處理的結點
BiTree p=(BiTree)malloc(sizeof(BiNode)); //生成根結點
p>data=level[]; p>lchild=null; p>rchild=null; //填寫該結點數據
for (i=; i<n; i++) //在中序序列中查找根結點然後左右子女信息入隊列
if (in[i]==level[]) break;
if (i==) //根結點無左子樹遍歷序列的n是右子樹
{p>lchild=null;
slvl=++R; sl=i+; sh=n; sf=p; slr=; enqueue(Qs);
}
else if (i==n) //根結點無右子樹遍歷序列的n是左子樹
{p>rchild=null;
slvl=++R; sl=; sh=i; sf=p; slr=; enqueue(Qs);
}
else //根結點有左子樹和右子樹
{slvl=++R; sl=; sh=i; sf=p; slr=;enqueue(Qs);//左子樹有關信息入隊列
slvl=++R; sl=i+;sh=n;sf=p; slr=;enqueue(Qs);//右子樹有關信息入隊列
}
while (!empty(Q)) //當隊列不空進行循環構造二叉樹的左右子樹
{ s=delqueue(Q); father=sf;
for (i=sl; i<=sh; i++)
if (in[i]==level[slvl]) break;
p=(bitreptr)malloc(sizeof(binode)); //申請結點空間
p>data=level[slvl]; p>lchild=null; p>rchild=null; //填寫該結點數據
if (slr==) father>lchild=p;
else father>rchild=p //讓雙親的子女指針指向該結點
if (i==sl)
{p>lchild=null; //處理無左子女
slvl=++R; sl=i+; sf=p; slr=; enqueue(Qs);
}
else if (i==sh)
{p>rchild=null; //處理無右子女
slvl=++R; sh=i; sf=p; slr=; enqueue(Qs);
}
else{slvl=++R; sh=i; sf=p; slr=; enqueue(Qs);//左子樹有關信息入隊列
slvl=++R; sl=i+; sf=p; slr=; enqueue(Qs); //右子樹有關信息入隊列
}
}//結束while (!empty(Q))
return(p);
}//算法結束
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23693.html
