數據結構考研分類復習真題 第六章 答案 (五)[41]

　　[題目分析] 雙鏈就利用二叉樹結點的左右指針重新定義左指針為指向前驅的指針右指針是指向後繼的指針鏈表在遍歷中建立下面采用中序遍歷二叉樹

　　BiTree head=nullpre; //全局變量鏈表頭指針headpre
　　void CreatLeafList(BiTree bt) //將BiTree 樹中所有葉子結點鏈成帶頭結點的雙鏈表
　　{if（bt）       //若bt不空
　　{CreatLeafList（bt>lchild）;              //中序遍歷左子樹
　　if(bt>lchild==null && bt>rchild==null)  //葉子結點
　　if(head==null)//第一個葉子結點
　　{head=(BiTree)malloc(sizeof(BiNode)); //生成頭結點
　　head>lchild=null; head>rchild=bt;  //頭結點的左鏈為空右鏈指向第一個葉子結點
　　bt>lchild=head; pre=bt;  //第一個葉子結點左鏈指向頭結點pre指向當前葉子結點
　　}
　　else    //已不是第一個葉子結點
　　{pre>rchild=bt; bt>lchild=pre; pre=bt;} //當前葉子結點鏈入雙鏈表
　　CreatLeafList(bt>rchild);  //中序遍歷右子樹
　　pre>rchild=null;    //最後一個葉子結點的右鏈置空（鏈表結束標記）
　　}//if(bt)   }//結束CreatLeafList;

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23697.html