參考資料：
http://cslibrary.stanford.edu/110/BinaryTrees.html
?
今天頂著要交年終文檔的壓力，總算理清了遞歸方式實現(xiàn)二叉樹的方法，徹底弄明白要如何建一顆二叉樹了！終于了切了一樁心愿！苦苦思索近兩個星期了，郁悶得快不行了。終于一見廬山真面目，真是凡事一定要堅持到底呀！
??????
言歸正傳，下面講如何創(chuàng)建二叉樹，以及遍歷二叉樹。
一、
首先記錄一下自己一直迷惑不解的幾個問題
1.1???
一顆二叉樹是如何表示的呢？為什么
yanghui
說返回一個根
root
結(jié)點就行了呢？
1.2???
二叉樹結(jié)點的結(jié)構(gòu)應(yīng)該如何設(shè)置？以前都是
{int data; Node left;Node right;}
就行了，為什么
yanghui
，
chexiaoyao
他們建的樹是第一個孩子和第一個弟弟的結(jié)構(gòu)，有層次（
int level
）等項呢？
1.3???
遞歸怎么寫？遞歸實現(xiàn)一顆樹又怎么寫？
1.4???
創(chuàng)建一個樹的函數(shù)（
buildTree(),insert(),create()
）應(yīng)該怎么寫？應(yīng)該接收什么參數(shù)，返回什么？為什么
yanghui
說肯定要傳一個
root
參數(shù)，并且返回一個根
root
結(jié)點呢？不傳根
root
參數(shù)可以嗎？返回的結(jié)點好像是每次加入的新結(jié)點呀，怎么直接
return
root
，就是根
root
結(jié)點了呢？真是想不明白啊。一個研二的學(xué)生了，也不好意思去問別人，人家都是考研過來的，這些早就熟爛了。
1.5???
根據(jù)網(wǎng)上的建議，看了遞歸的內(nèi)容，重新了解了堆棧的概念，看了自己買的《數(shù)據(jù)結(jié)構(gòu)
算法與應(yīng)用
C++
》二叉樹部分，遞歸方法應(yīng)該是掌握了，這本書中羅列了三種遞歸的遍歷方式，清晰明了。但是偏偏我最想要的內(nèi)容建立二叉樹的函數(shù)，這本書里沒有，有的只是根據(jù)已有的左右子樹合并成一顆新樹，暈，這點誰不會！郁悶啊，難怪自己一直沒有理解如何建立二叉樹，一則是完成
wuping
老師的程序的時候，照著她的書拷貝程序，程序調(diào)通了就萬事
ok
，哪里還管其他的，二則自己的救命草就是這本書，這本書沒有，自己肯定也沒去思考過，更沒有去找過其他的資料。
?
二、
在編碼實踐中領(lǐng)悟和解決上述問題
在
baidu
和
google
上搜索了眾多的資料，但是搜索結(jié)果很令人失望，沒講什么內(nèi)容，而且程序還不能確保正確。大部分也都是
c
或者
c++
寫的，
java
的程序很難搜索到。看了一兩天這些網(wǎng)頁上的程序，感覺思路越來越亂了！
某一天上午，突然靈光一動，上次自己搜索到的決策樹的好東西都是在
google
中用全英文的關(guān)鍵字搜索到的，以前看過一個帖子提過
google
中如果用英文檢索，會得到很多好結(jié)果。于是，在
google
中輸入“
Binary
Trees
”，哇，第一條的內(nèi)容是斯坦福大學(xué)
CS
專業(yè)的二叉樹的代碼和講解，并且有
C,C++,JAVA
三個版本的代碼，以及詳細(xì)的講解，這正是我夢寐以求的資料！我知道我將有希望搞定二叉樹了！
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
注意它的封裝性和訪問控制權(quán)限。設(shè)置為
private
類以及
BinaryTree
的函數(shù)都相應(yīng)有
private
和
public
方法來實現(xiàn)很好的封裝和訪問控制，這種方式以后自己要多加學(xué)習(xí)，積極運用。
?
2.2.2
把類設(shè)置為
static
的作用和藝術(shù)？？自己還沒有理解，也還沒有查資料，有待學(xué)習(xí)。。。不用
static
關(guān)鍵字程序也能運行。
Static
類有何用途呢？？
?
?
2.3
關(guān)鍵函數(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)錯誤根源！當(dāng)運行到
data
＝
1
的時候，程序便在這里
”
root.
left
= insert(data);
”
進(jìn)入死循環(huán)了！！因為沒有退出遞歸的條件！！
?
發(fā)現(xiàn)問題后，思索了一會，發(fā)現(xiàn)其實還是自己根本沒有理解遞歸！這個程序是遞歸算法，遞歸算法的本質(zhì)是要有一個不斷遞歸的變量，比如說求
n
！階層的遞歸函數(shù)中，要傳一個
n
變量，并且
n
變量要每次調(diào)用都自減
1
。寫一個遞歸函數(shù)就要先清楚要根據(jù)哪一個自變化的遞歸變量遞歸呀！！上述
insert(int data)
函數(shù)沒有了遞歸變量
Node node
，當(dāng)然就進(jìn)入死循環(huán)，
stack
溢出了！
所以，如果要用遞歸的方式實現(xiàn)創(chuàng)建二叉樹的函數(shù)，那么這個根
root
結(jié)點參數(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);
????? }
??? }
?
? }
?
?
??????
這時程序運行，沒有任何的輸出結(jié)果。百思不得其解呀！后來考慮到
C++
中是傳引用或者指針，而
java
中是值傳遞的問題，猜到可能是沒有返回值的話，
root
數(shù)據(jù)成員可能始終為空，因為函數(shù)的調(diào)用絲毫不能影響實參。于是加上
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
根結(jié)點的值。于是，把
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
? }
?
哈，驗證了自己的猜想，此時能夠正確輸出結(jié)果了：（中序遍歷）
1?
2? 3? 4? 6
ok
！
?
三、
小結(jié)
已經(jīng)是
20070202 01
：
44
了，通過今晚，二叉樹的困惑已經(jīng)沒太大問題了！這兩個星期時常對它們的苦苦思索也將告終，雖然有點累了，也擔(dān)心明早起不來，而且還要交文檔，但心情還是挺愉快的。總算沒有辜負(fù)先放棄文檔的代價。
二叉樹對別人來說可能是微不足道的程序，但這次對于我卻至關(guān)重要，關(guān)鍵是信心的問題，現(xiàn)在又對自己充滿信心了！不怕烏龜跑得慢，就怕它沒能堅持一直往前沖！
?
最后小結(jié)一下二叉樹的知識點：
1）?
理解遞歸方法，理解要又一個自變化的遞歸變量作參數(shù)；
2）?
理解編譯原理的
stack
的概念；
3）?
理解引用調(diào)用，值調(diào)用的方式；
4）?
理解
root
根結(jié)點的引用；創(chuàng)建一顆樹時，要返回一個
root
根結(jié)點的應(yīng)用，這樣才能根據(jù)
root
找到這顆樹！
5）?
進(jìn)一步加深了對寫一個函數(shù)關(guān)鍵要確定接口，即參數(shù)和返回值；
6）?
理解上述
private
Node insert(Node
node,
int
data)
函數(shù)為什么每次調(diào)用得到都是
root
根結(jié)點，而不是新加入的新結(jié)點。這一點很重要。自己可以手工一步一步把代碼走一遍就明白了！
7）?
這次調(diào)程序的一個經(jīng)驗和收獲：
就像
yanghui
說的，寫程序之前，自己也手工算一遍并走一遍！這點太重要了，尤其時算法類的程序！這次能夠最終理解二叉樹，就是靠手工一步一步走一遍，最終發(fā)現(xiàn)問題所在的！
?
Ok
！