參考資料： http://cslibrary.stanford.edu/110/BinaryTrees.html

?

今天頂著要交年終文檔的壓力，總算理清了遞歸方式實現(xiàn)二叉樹的方法，徹底弄明白要如何建一顆二叉樹了！終于了切了一樁心愿！苦苦思索近兩個星期了，郁悶得快不行了。終于一見廬山真面目，真是凡事一定要堅持到底呀！

?????? 言歸正傳，下面講如何創(chuàng)建二叉樹，以及遍歷二叉樹。

一、 首先記錄一下自己一直迷惑不解的幾個問題

1.1??? 一顆二叉樹是如何表示的呢？為什么 yanghui 說返回一個根 root 結點就行了呢？

1.2??? 二叉樹結點的結構應該如何設置？以前都是 {int data; Node left;Node right;} 就行了，為什么 yanghui ， chexiaoyao 他們建的樹是第一個孩子和第一個弟弟的結構，有層次（ int level ）等項呢？

1.3??? 遞歸怎么寫？遞歸實現(xiàn)一顆樹又怎么寫？

1.4??? 創(chuàng)建一個樹的函數(shù)（ buildTree(),insert(),create() ）應該怎么寫？應該接收什么參數(shù)，返回什么？為什么 yanghui 說肯定要傳一個 root 參數(shù)，并且返回一個根 root 結點呢？不傳根 root 參數(shù)可以嗎？返回的結點好像是每次加入的新結點呀，怎么直接 return root ，就是根 root 結點了呢？真是想不明白啊。一個研二的學生了，也不好意思去問別人，人家都是考研過來的，這些早就熟爛了。

1.5??? 根據(jù)網(wǎng)上的建議，看了遞歸的內容，重新了解了堆棧的概念，看了自己買的《數(shù)據(jù)結構 算法與應用 C++ 》二叉樹部分，遞歸方法應該是掌握了，這本書中羅列了三種遞歸的遍歷方式，清晰明了。但是偏偏我最想要的內容建立二叉樹的函數(shù)，這本書里沒有，有的只是根據(jù)已有的左右子樹合并成一顆新樹，暈，這點誰不會！郁悶啊，難怪自己一直沒有理解如何建立二叉樹，一則是完成 wuping 老師的程序的時候，照著她的書拷貝程序，程序調通了就萬事 ok ，哪里還管其他的，二則自己的救命草就是這本書，這本書沒有，自己肯定也沒去思考過，更沒有去找過其他的資料。

?

二、 在編碼實踐中領悟和解決上述問題

在 baidu 和 google 上搜索了眾多的資料，但是搜索結果很令人失望，沒講什么內容，而且程序還不能確保正確。大部分也都是 c 或者 c++ 寫的， java 的程序很難搜索到?？戳艘粌商爝@些網(wǎng)頁上的程序，感覺思路越來越亂了！

某一天上午，突然靈光一動，上次自己搜索到的決策樹的好東西都是在 google 中用全英文的關鍵字搜索到的，以前看過一個帖子提過 google 中如果用英文檢索，會得到很多好結果。于是，在 google 中輸入“ Binary Trees ”，哇，第一條的內容是斯坦福大學 CS 專業(yè)的二叉樹的代碼和講解，并且有 C,C++,JAVA 三個版本的代碼，以及詳細的講解，這正是我夢寐以求的資料！我知道我將有希望搞定二叉樹了！

2.1 BinaryTree 類的代碼如下：

http://cslibrary.stanford.edu/110/BinaryTrees.html

// BinaryTree.java

package study;

?

public class BinaryTree {

? // Root node pointer. Will be null for an empty tree.

? private Node root ;

?

? private static class Node {

??? Node left ;

??? Node right ;

??? int data ;

?

??? Node( int newData) {

????? left = null ;

????? right = null ;

????? data = newData;

??? }

? }

?

? /**

?? Creates an empty binary tree -- a null root pointer.

? */

? public BinaryTree() {

??? root = null ;

? }

?

? /**

?? Inserts the given data into the binary tree.

?? Uses a recursive helper.

? */

? public void insert( int data) {

??? root = insert( root , data);

? }

?

?

? /**

?? Recursive insert -- given a node pointer, recur down and

?? insert the given data into the tree. Returns the new

?? node pointer (the standard way to communicate

?? a changed pointer back to the caller).

? */

? private Node insert(Node node, int data) {

??? if (node== null ) {

????? node = new Node(data);

??? }

??? else {

????? if (data <= node. data ) {

??????? node. left = insert(node. left , data);

????? }

????? else {

??????? node. right = insert(node. right , data);

????? }

??? }

?

??? return (node); // in any case, return the new pointer to the caller

? }

?

???

? public void buildTree( int [] data){

??? ?

??? ? for ( int i=0;i<data. length ;i++){

?????? ? insert(data[i]);

??? ? }?

? }

?

? public void printTree() {

??? ? printTree( root );

??? ? System. out .println();

??? ?}

? private void printTree(Node node) {

??? ? if (node == null ) return ;

?

??? ? // left, node itself, right

??? ? printTree(node. left );

??? ? System. out .print(node. data + "? " );

??? ? printTree(node. right );

??? ?}

?

?

}

?

?

?

測試類代碼如下：

//test.java

public class test {

??? public static void main(String[] args) {

?????? BinaryTree biTree=new BinaryTree();

?????? int[] data={2,8,7,4};

?????? biTree.buildTree(data);

?????? biTree.printTree();

??????

??? }

}

?

?

2.2? Node 類

private static class Node {

??? Node left ;

??? Node right ;

??? int data ;

?

??? Node( int newData) {

????? left = null ;

????? right = null ;

????? data = newData;

??? }

? }

?

2.2.1 注意它的封裝性和訪問控制權限。設置為 private 類以及 BinaryTree 的函數(shù)都相應有 private 和 public 方法來實現(xiàn)很好的封裝和訪問控制，這種方式以后自己要多加學習，積極運用。

?

2.2.2 把類設置為 static 的作用和藝術？？自己還沒有理解，也還沒有查資料，有待學習。。。不用 static 關鍵字程序也能運行。 Static 類有何用途呢？？

?

?

2.3 關鍵函數(shù) insert()

private Node insert(Node node, int data) {

??? if (node== null ) {

????? node = new Node(data);

??? }

??? else {

????? if (data <= node. data ) {

??????? node. left = insert(node. left , data);

????? }

????? else {

??????? node. right = insert(node. right , data);

????? }

??? }

?

??? return (node); // in any case, return the new pointer to the caller

? }

?

?

自己對這個 insert() 研究了兩三天，今天總算琢磨明白了！

?

2.3.1 為什么需要 Node node 參數(shù)？能不要這個參數(shù)嗎？也就是這個函數(shù)如果是 insert(int data) 可以實現(xiàn)創(chuàng)建二叉樹的功能嗎？

編碼實踐實驗：

1 ）把 Node node 參數(shù)去掉，寫一個函數(shù) insert(int data) 如下：

private Node insert( int data) {

??? if (node== null ) {

????? root = new Node(data);

??? }

??? else {

????? if (data <= root. data ) {

??????? root. left = insert(data);

????? }

????? else {

??????? root. right = insert(data);

????? }

??? }

?

??? return (node); // in any case, return the new pointer to the caller

? }

?

?

這時，程序運行會報一大堆的 stack 溢出錯誤。剛開始怎么也想不明白為什么會 stack 溢出。后來，自己手工用一個例子數(shù)據(jù) {2 ， 1 ， 3 ， 6 ， 4} 一步一步按照上述代碼走一遍，終于發(fā)現(xiàn)錯誤根源！當運行到 data ＝ 1 的時候，程序便在這里 ” root. left = insert(data); ” 進入死循環(huán)了??！因為沒有退出遞歸的條件！！

?

發(fā)現(xiàn)問題后，思索了一會，發(fā)現(xiàn)其實還是自己根本沒有理解遞歸！這個程序是遞歸算法，遞歸算法的本質是要有一個不斷遞歸的變量，比如說求 n ！階層的遞歸函數(shù)中，要傳一個 n 變量，并且 n 變量要每次調用都自減 1 。寫一個遞歸函數(shù)就要先清楚要根據(jù)哪一個自變化的遞歸變量遞歸呀??！上述 insert(int data) 函數(shù)沒有了遞歸變量 Node node ，當然就進入死循環(huán)， stack 溢出了！

所以，如果要用遞歸的方式實現(xiàn)創(chuàng)建二叉樹的函數(shù)，那么這個根 root 結點參數(shù)肯定是要有的！

現(xiàn)在確定， insert 函數(shù)必須有兩個參數(shù)。下面接著討論返回值的問題。

?

2.3.2 為什么需要返回值？返回值為 void 可以嗎？ C ＋＋版本的建樹函數(shù)是可以不用返回值的。

1 ）把返回值去掉，寫一個函數(shù) void insert(Node node ， int data) 如下：

private void insert(Node node, int data) {

??? if (node== null ) {

????? node = new Node(data);

??? }

??? else {

????? if (data <= node. data ) {

?????? ???? insert(node. left , data);

????? }

????? else {

??????? ???? insert(node. right , data);

????? }

??? }

?

? }

?

?

?????? 這時程序運行，沒有任何的輸出結果。百思不得其解呀！后來考慮到 C++ 中是傳引用或者指針，而 java 中是值傳遞的問題，猜到可能是沒有返回值的話， root 數(shù)據(jù)成員可能始終為空，因為函數(shù)的調用絲毫不能影響實參。于是加上 root 的返回值，代碼如下：

private Node insert(Node node, int data) {

??? if (node== null ) {

????? node = new Node(data);

??? }

??? else {

????? if (data <= node. data ) {

?????? ???? insert(node. left , data);

????? }

????? else {

??????? ???? insert(node. right , data);

????? }

??? }

? ?? return node ；

? }

?

此時，插入數(shù)據(jù) int data[]={2,1,3,6,4}, 程序有輸出了，但是只輸出“ 2 ”，也就是只能輸出 root 根結點的值。于是，把 root.left 和 root.right 的引用加上，因為猜想可能還是因為 java 是值傳遞的問題，使得 root.left 和 root.right 始終為空。加上后代碼如下：

private Node insert(Node node, int data) {

??? if (node== null ) {

????? node = new Node(data);

??? }

??? else {

????? if (data <= node. data ) {

??????? node. left = insert(node. left , data);

????? }

????? else {

? ??????node. right = insert(node. right , data);

????? }

??? }

?

??? return (node); // in any case, return the new pointer to the caller

? }

?

哈，驗證了自己的猜想，此時能夠正確輸出結果了：（中序遍歷）

1? 2? 3? 4? 6

ok ！

?

三、 小結

已經是 20070202 01 ： 44 了，通過今晚，二叉樹的困惑已經沒太大問題了！這兩個星期時常對它們的苦苦思索也將告終，雖然有點累了，也擔心明早起不來，而且還要交文檔，但心情還是挺愉快的?？偹銢]有辜負先放棄文檔的代價。

二叉樹對別人來說可能是微不足道的程序，但這次對于我卻至關重要，關鍵是信心的問題，現(xiàn)在又對自己充滿信心了！不怕烏龜跑得慢，就怕它沒能堅持一直往前沖！

?

最后小結一下二叉樹的知識點：

1）? 理解遞歸方法，理解要又一個自變化的遞歸變量作參數(shù)；

2）? 理解編譯原理的 stack 的概念；

3）? 理解引用調用，值調用的方式；

4）? 理解 root 根結點的引用；創(chuàng)建一顆樹時，要返回一個 root 根結點的應用，這樣才能根據(jù) root 找到這顆樹！

5）? 進一步加深了對寫一個函數(shù)關鍵要確定接口，即參數(shù)和返回值；

6）? 理解上述 private Node insert(Node node, int data) 函數(shù)為什么每次調用得到都是 root 根結點，而不是新加入的新結點。這一點很重要。自己可以手工一步一步把代碼走一遍就明白了！

7）? 這次調程序的一個經驗和收獲：

就像 yanghui 說的，寫程序之前，自己也手工算一遍并走一遍！這點太重要了，尤其時算法類的程序！這次能夠最終理解二叉樹，就是靠手工一步一步走一遍，最終發(fā)現(xiàn)問題所在的！

?

Ok ！