[題目分析]葉子結點只有在遍歷中才能知道這裡使用中序遞歸遍歷設置前驅結點指針pre初始為空第一個葉子結點由指針head指向遍歷到葉子結點時就將它前驅的rchild指針指向它最後葉子結點的rchild為空
LinkedList headpre=null; //全局變量
LinkedList InOrder(BiTree bt)
//中序遍歷二叉樹bt將葉子結點從左到右鏈成一個單鏈表表頭指針為head
{if(bt){InOrder(bt>lchild); //中序遍歷左子樹
if(bt>lchild==null && bt>rchild==null) //葉子結點
if(pre==null) {head=bt; pre=bt;} //處理第一個葉子結點
else{pre>rchild=bt; pre=bt; } //將葉子結點鏈入鏈表
InOrder(bt>rchild); //中序遍歷左子樹
pre>rchild=null; //設置鏈表尾
}
return(head); } //InOrder
時間復雜度為O(n)輔助變量使用head和pre棧空間復雜度O(n)
層次遍歷參見上面算法第題中序遍歷序列和後序序列可確定一棵二叉樹詳見上面應用題第題先序序列和後序序列無法確定一棵二叉樹因為無法將二叉樹分成左右子樹如先序序列AB和後序序列BAA是根但B可以是左子女也可以是右子女
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23705.html
