遞歸實現(xiàn)二叉樹的遍歷
class BinaryTree{
? ? ? ? ?public int value;
? ? ? ? ?public BinaryTree left;
? ? ? ? ?public BinaryTree right;
? ? ? ? ?public BinaryTree(int data){
? ? ? ? ? ? ? ? ? this.value = data;
? ? ? ? ?}
? ? ? ? ?//先序遍歷二叉樹
? ? ? ? ?public void preOrderRecur(BinaryTree head){
? ? ? ? ? ? ? ? ?if(head==null){
? ? ? ? ? ? ? ? ? ? ? ? ?return;
? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ?System.out.println(head.value+" ");
? ? ? ? ? ? ? ? ?preOrderRecur(head.left);
? ? ? ? ? ? ? ? preOrderRecur(head.right);
? ? ? ? ?}
? ? ? ? //中序遍歷二叉樹
? ? ? ? public void inOrderRecur(BinaryTree head){
? ? ? ? ? ? ? ? ? ?if(head==null){
? ? ? ? ? ? ? ? ? ? ? ? return;
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? inOrderRecur(head.left);
? ? ? ? ? ? ? ? ? System.out.println(head.value+" ");? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? inOrderRecur(head.right);
? ? ? ? ?}
? ? ? ? ?//后序遍歷二叉樹
? ? ? ? ?public void postOrderRecur(BinaryTree head){
? ? ? ? ? ? ? ? ?if(head==null){
? ? ? ? ? ? ? ? ? ? ?return;
? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? postOrderRecur(head.left);
? ? ? ? ? ? ? ? postOrderRecur(head.right);
? ? ? ? ? ? ? ? System.out.println(head.value+" ");
? ? ? ?}
}
用遞歸方法實現(xiàn)二叉樹的遍歷，那么也可以非遞歸來實現(xiàn)。遞歸方法是利用棧來保存信息的，棧是具有記憶功能的數(shù)據(jù)結(jié)構(gòu)。我個人不怎么喜歡用遞歸，建議盡量不要用遞歸來解決問題。因為遞歸涉及到重復(fù)計算，還有當(dāng)數(shù)據(jù)規(guī)模很大時就會導(dǎo)致內(nèi)存溢出。下面介紹用非遞歸的方法來實現(xiàn)二叉樹遍歷。
1.非遞歸先序遍歷二叉樹
a.申請一個棧stack，將頭結(jié)點head壓入stack中；
b.從stack中彈出棧頂節(jié)點元素cur,然后打印節(jié)點元素的值，再將節(jié)點cur的右子樹先壓入stack中，最后將cur的左子樹壓入stack中，前提是左子樹和右子樹不為空
c.不斷重復(fù)步驟b，一直到stack為空，全部過程結(jié)束
舉例說明（這里要說明的是棧是后進(jìn)先出，所以先是右子樹進(jìn)棧，然后再左子樹進(jìn)棧，這樣就可以使左子樹的元素先打印出來）
第一步，1進(jìn)棧，彈出來并打印，3進(jìn)棧，2進(jìn)棧（棧頂?shù)綏５滓来问?,3）
第二步，2彈出并打印，5進(jìn)棧，4進(jìn)棧（棧頂?shù)綏５滓来问?,5,3）
第三步，4彈出來并打?。ｍ?shù)綏５滓来问?,3）
第四步，5彈出來并打?。Ｖ兄挥?）
第五步，3彈出來并打印，7進(jìn)棧，6進(jìn)棧（棧頂?shù)綏５滓来问?,7）
第六步，6彈出并打印
第七步，7彈出并打印
非遞歸的先序遍歷代碼如下：
public void preOrderUnRecur(BinaryTree head){
? ? ? ? System.out.println("非遞歸先序遍歷：");
? ? ? ? if(head!=null){
? ? ? ? ? ? ? Stack<BinaryTree> stack = new Stack<BinaryTree>();
? ? ? ? ? ? ? ?stack.add(head);
? ? ? ? ? ? ? ?while(!stack.isEmpty()){
? ? ? ? ? ? ? ? ? ? ?head = stack.pop();//頭結(jié)點元素出棧
? ? ? ? ? ? ? ? ? ? ?System.out.println(head.value+" ");
? ? ? ? ? ? ? ? ? ? ?if(head.right!=null){
? ? ? ? ? ? ? ? ? ? ? ? ? ? stack.push(head.right);
? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ? ?if(head.left!=null){
? ? ? ? ? ? ? ? ? ? ? ? ? ? stack.push(head.left);
? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? }
? ? ? ? }
? ? ? ?System.out.println();
}
就寫到這里了，實驗室要關(guān)門了，不往下寫了。非遞歸的關(guān)鍵點就是要利用棧的性質(zhì)，還有就是輸出的結(jié)果跟元素進(jìn)棧的順序是相反的，這里還是棧的性質(zhì)，非遞歸的中序遍歷和后序遍歷跟這差不多。希望各位前輩同仁指正！謝謝...
