對(duì)于什么是樹(shù)，以及樹(shù)的概念亲茅，我們?cè)谶@里不做贅述了回铛，大家在數(shù)據(jù)結(jié)構(gòu)的課程里都應(yīng)該學(xué)過(guò)狗准，這里我推薦mooc慕課中浙江大學(xué)陳越老師的《數(shù)據(jù)結(jié)構(gòu)》課程，非常便于理解數(shù)據(jù)結(jié)構(gòu)的知識(shí)茵肃，而且對(duì)于算法的講解很透徹腔长。
今天我們主要講的是如何設(shè)計(jì)一個(gè)二叉樹(shù)類，大家都知道Java中是沒(méi)有結(jié)點(diǎn)以及指針類型的验残，實(shí)現(xiàn)起來(lái)有時(shí)會(huì)讓我們摸不到頭腦捞附，這一講也是為了以后深入了解二叉樹(shù)相關(guān)算法和十分重要的二叉樹(shù)的遍歷作為提前的知識(shí)儲(chǔ)備，比較簡(jiǎn)單您没，很容易理解：）
二叉樹(shù)的抽象數(shù)據(jù)類型
首先我們要了解二叉樹(shù)基本實(shí)現(xiàn)所需要的抽象數(shù)據(jù)類型鸟召，從兩個(gè)方面介紹
①.數(shù)據(jù)集合：為二叉樹(shù)的結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間關(guān)系的指針組成氨鹏。
②.操作集合：
（1）雙親結(jié)點(diǎn)parent()：
（2）左孩子結(jié)點(diǎn)leftChild()
（3）右孩子結(jié)點(diǎn)rightSibling()
（4）左插入結(jié)點(diǎn)insertLeftNode(x)
（5）右插入結(jié)點(diǎn)insertRightNode(x)：
（6）左刪除子樹(shù)deleteLeftTree()
（7）右刪除子樹(shù)deleteRightTree()
（8）遍歷二叉樹(shù)traverse(vs)---最重要也就是這個(gè)啦
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
1.順序存儲(chǔ)結(jié)構(gòu)
（a）為非完全二叉樹(shù)欧募，既然我們要存儲(chǔ)（a），首先我們要把它變成完全二叉樹(shù)喻犁，也就是將空余部分補(bǔ)上槽片，因?yàn)槎鏄?shù)本身就是有順序的，樹(shù)根為0肢础，所以A為0 B為1 C為2 我們順序把結(jié)點(diǎn)存入數(shù)組，空出來(lái)的地方就為空
2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用指針建立二叉樹(shù)中結(jié)點(diǎn)之間的關(guān)系碌廓。
二叉鏈存儲(chǔ)結(jié)構(gòu)的每個(gè)結(jié)點(diǎn)包含三個(gè)域 传轰。
data：為數(shù)據(jù)域 ?leftChild：為左孩子的指針域 ?rightChild：為右孩子的指針域
舉個(gè)小栗子~
（a）不帶頭結(jié)點(diǎn)的二叉樹(shù)，可以看到谷婆，沒(méi)有指針域的結(jié)點(diǎn)慨蛙，左邊或者右邊為空
（b）帶頭結(jié)點(diǎn)的二叉樹(shù)，頭結(jié)點(diǎn)只負(fù)責(zé)指向我們的樹(shù)根結(jié)點(diǎn)
設(shè)計(jì)二叉樹(shù)
二叉樹(shù)由三個(gè)部分組成：結(jié)點(diǎn)纪挎、左孩子期贫、右孩子，因此我們要設(shè)計(jì)的二叉樹(shù)類由兩個(gè)部分組成：二叉樹(shù)類和二叉樹(shù)結(jié)點(diǎn)類异袄。
二叉樹(shù)結(jié)點(diǎn)類
首先我們聲明三個(gè)私有的成員變量：數(shù)據(jù)元素（即結(jié)點(diǎn)的值）通砍、左孩子和右孩子，生成get/set方法烤蜕，為了方便初始化和傳值封孙，我們分別聲明一個(gè)無(wú)參的構(gòu)造方法和有參的構(gòu)造方法。具體代碼如下讽营。
二叉樹(shù)類
當(dāng)我們有了二叉樹(shù)結(jié)點(diǎn)類虎忌，我們就可以創(chuàng)建一個(gè)二叉樹(shù)了，我們把結(jié)點(diǎn)的數(shù)據(jù)元素傳給我們的二叉樹(shù)結(jié)點(diǎn)類橱鹏，并且區(qū)分好左右膜蠢，這樣我們的二叉樹(shù)就建立好了堪藐。
總結(jié)
理解好二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)至關(guān)重要，也是為了我們接下來(lái)學(xué)習(xí)遍歷二叉樹(shù)而大號(hào)基礎(chǔ)挑围。
下一講礁竞，我們就開(kāi)始研究如何遍歷二叉樹(shù)的算法！直奔主題贪惹！
PS：有什么問(wèn)題或者不解的地方可以評(píng)論苏章，我都會(huì)一一就行回復(fù)的，如果有錯(cuò)誤或者言語(yǔ)不明的地方奏瞬，還請(qǐng)大神多多指點(diǎn)枫绅！
