今天繼續是講二叉樹，樹一個重要的操作就是遍歷。所謂遍歷就是輸出所有的結點，二叉樹不同于樹只有前序和后序遍歷，因為二叉樹左右子樹木特點，所有還有另一種遍歷方法，就是中序。這些遍歷也十分簡單，最主要的還是看根遍歷的前后來分別是前中后序遍歷的。下面看圖第十四天
這些顏色圈著代表分別當一個樹來看，所有我們知道其規律就可以寫出程序來了，程序也十分簡單，如下：out1(btree *t) /*前序遍歷*/
{
printf("%d",t->data);
out1(t->left);
out1(t->right);
}
out2(btree *t) /*中序遍歷*/
{
out2(t->left);
printf("%d",t->data);
out2(t->right);
}
out3(btree *t) /*后序遍歷*/
{
out3(t->left);
out3(t->right);
printf("%d",t->data);
}
上面三種遍歷是不是很簡單（這個遞歸想一想就明白的了），而且他們很像似只是改變了行位置，我們由此可以看出如果是前序的那個輸出是最先的，跟著才是進入左樹到右樹�？赐炅吮闅v就看看二叉查找樹，二叉查找樹是這樣的一種樹，他的左結點都小于根，右結點都大于左結點。有這么一種性質所以他的插入特別好辦，用中序遍歷的方法設計這個排序算法特別好，因為這個樹本來就是這樣排序下來的。下面就來看看程序是如何實現的
insert(btree *h,btree *p)
{
if(h= =NULL) h=p; p->left=p->right=NULL; /*最后一個結點一定是沒有左右子樹*/
else
{
if(p->data<h->data) insert (h->left);
if(p->data>h->data) insert(h->right);
}
}
看上去很簡單的幾行，可是因為遞歸就得弄明白一些思路，看看它是如何產生插入到合適的位置，和前一堂課的建立二叉樹思路一樣，也是比較他的值大小排位置。大家要好好的看明白。就是因為我們班里的幾個同學都對樹比較陌生，跟不上來所以老師決定先把樹告一斷落，其實樹還有很多方面的知識還沒有講到，只好等過一排思維清晰了才可以繼續，其實如果我之前沒有自己看過一下，到老師說的時候可能真的聽不明白，突意間飛來的大難點啊。
時間真的用了很多在這些樹上，而且還沒有什么大的效果。老師也馬上看機行事，跳過這節來講一下查找這章。到于查其實我們平常也接觸得多了，特別是我以前學Foxbase的時候，基本上什么都離不開查找，不過當時的查找就是這么一條命令就搞定了�，F在要自己編出來也真的挺好玩的，以前完全封裝性的Foxbase命令，今天就要編成這個系統的C語言來深入研究它，之前說的鏈表和結構就是用來做數據庫的了（如果我沒有估錯的話）。說多了費了，馬上講講學習查找的情況。順序查找相信大家都知道原理了，因為一個一個順序的判斷是否相等這是最常見的了。我在這里就不再多講，繼續講下一個，折半查找法。在講這個之前老師和我們做了一個游戲，就是他在紙上寫下一個數值，范圍在1到1000內讓我們來猜，如果我們說的數大過這個數老師就是太大了，反之就太小了。其實這個折半原理早就在QB里見過了，也沒有什么難度嘛。很快我們就按照那個方法給猜出來了得數，老師都見我們懂了的樣子就直接叫我們寫個程序好了，當時我一時看到這題有重復的規律性就一直以遞歸的思路來做這題了，可是我錯了，不過這個錯令我學到了另一個技巧。下面先來看看我的程序，如下：
假如a[]已經是有了值，而且還是順序排好的了。
serch(int r, int k, int n)
{
int mid;
if(r>k) return(-1);
else
{
mid=(r+k)/2;
if(a[mid]>n) serch(r,mid-1,n);
if(a[mid]<n) serch(mid+1,k,n);
if(a[mid]= =n) return(mid) /*注意就是這里有問題了*/
}
}
好像看上去沒有什么問題似的，其實問題都挺大的，因為返回值根本不能返到最頂的那個自調用里，就只能返回一層，所有我的答案也根本出不來嘛。雖然老師還是贊了我一下會去用遞歸來做這題（其實因為本來循環可以很簡單的可以實現了，而且不會浪費那么多的空間了），不過錯還是錯的。老師按照我的這個思路寫了一個新的出來，如下：
serch(int r,int k,int n)
{
int mid;
if (r > k) return (-1);
mid =(r+k)/2;
if(a[mid]= =n) return(mid);
else
{
a[mid]<n ? r=mid+1; k=mid-1;
return (serch(r,k,n) ); /*巧妙的就是這里了*/
}
}
一條程序可以反應該人的水平說的真沒錯，這條程序幾個地方都寫得很好，特別巧妙的可以令遞歸返回值到最頂的那個可真棒啊。就這樣隨著時間的到來，我們也差不多放學了，我還真的要努力才行了，我要努力再努力，堅持再堅持。
文章來源于領測軟件測試網 http://www.kjueaiud.com/