[題目分析] 本題使用的存儲結構是一種雙親表示法對每個結點直接給出其雙親（的下標）而且用正或負表示該結點是雙親的右子女或左子女該類結構不適於直接進行前序遍歷（即若直接前序遍歷算法要很復雜）較好的辦法是將這類結構轉為結點及其左右子女的順序存儲結構即
Tree=ARRAY[max] OF RECORD data: char; //結點數據
lcrc: integer; END;//結點的左右子女在數組中的下標
void Change (Tree t Tree bt int *root) //先將t轉為如上定義類型的變量bt;
{for(i=;i<=max;i++) {bt[i]lc=bt[i]rc=;} //先將結點的左右子女初始化為
for(i=;i<=max;i++) //填入結點數據和結點左右子女的信息
{bt[i]data=t[i]data;
if(t[i]parent<) bt[t[i]parent]lc=i; //左子女
else if(t[i]parent>) bt[t[i]parent]rc=i; //右子女
else *root=i; //root記住根結點
} }//change
void PreOrder(Tree bt) //對二叉樹進行前序遍歷
{int *roottop=; int s[]; //s是棧
change(tbtroot); int i=*root;
while(i!=||top>)
{while (i!=)
{printf (bt[i]data)if(bt[i]rc!=) s[++top]=bt[i]rc; //右子女進棧
i=bt[i]lc;
}
if (top>) i=s[top];
} }//結束preorder
[算法討論]本題的前序遞歸算法如下
void PreOrder(int root)//root是二叉樹根結點在順序存儲中的下標本算法前序遍歷二叉樹bt
{if(root!=){printf(bt[root]data);//訪問根結點
PreOrder(bt[root]lc);//前序遍歷左子樹
PreOrder(bt[root]rc);//前序遍歷右子樹
} }//結束preorder初始調用時root是根結點的下標
這類問題的求解方法值得注意當給定數據存儲結構不合適時可由已給結構來構造好的數據結構以便於運算象上面第題也是這樣先根據L和R數組構造一個結點的雙親的數組T
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23716.html
