二叉樹和二叉搜索樹
ps：整個文章所涉及的源代碼我都發(fā)布在我的Github主頁上，大家可以自行下載，如果對您有一丟丟的幫助的話，記得在我的github項目上點(diǎn)上【star】喲，當(dāng)然不要忘了在本篇文章下方【點(diǎn)贊】啦，你們的支持將是我最大的動力！
（利他之心是每個優(yōu)秀開發(fā)者的傳統(tǒng)美德！——@惜墨的少年）
樹的相關(guān)術(shù)語
一個樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。除了頂部的第一個節(jié)點(diǎn)，每個節(jié)點(diǎn)都有一個父節(jié)點(diǎn)以及零個或多個子節(jié)點(diǎn)。樹頂部的節(jié)點(diǎn)叫做根節(jié)點(diǎn)，它沒有父節(jié)點(diǎn)。樹中每個元素叫做節(jié)點(diǎn)，節(jié)點(diǎn)分為內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)。至少有一個子節(jié)點(diǎn)的節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn)。沒有子元素的節(jié)點(diǎn)稱為外部節(jié)點(diǎn)即葉子節(jié)點(diǎn)。
有關(guān)樹的另外一個術(shù)語是子樹。子樹由節(jié)點(diǎn)和它的后代構(gòu)成。節(jié)點(diǎn)的一個屬性是深度，節(jié)點(diǎn)的深度取決于它的祖先節(jié)點(diǎn)的數(shù)量。樹的高度取決于所有節(jié)點(diǎn)深度的最大值。一棵樹也可以分解成層級。根節(jié)點(diǎn)在第0層，它的子節(jié)點(diǎn)在第1層，以此類推。
二叉樹和二叉搜索樹
二叉樹中的節(jié)點(diǎn)最多只能有兩個子節(jié)點(diǎn)：一個是左側(cè)子節(jié)點(diǎn)，另一個是右側(cè)子節(jié)點(diǎn)。二叉搜索樹（BST）是二叉樹的一種，但是只允許在左側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）小的值，在右側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）大（或者等于）的值。下面以二叉搜索樹為例。
創(chuàng)建 Node 類
創(chuàng)建 BinarySearchTree 類
中序遍歷
中序遍歷是一種以上行順序訪問BST所有節(jié)點(diǎn)的遍歷方式，也就是以從小到大的順序訪問所有節(jié)點(diǎn)。中序遍歷的一種應(yīng)用是對樹進(jìn)行排序操作。
先序遍歷
先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個節(jié)點(diǎn)的。先序遍歷的一種應(yīng)用是打印一個結(jié)構(gòu)化的文檔。
后序遍歷
后序遍歷是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身。后續(xù)遍歷的一種應(yīng)用是計算一個目錄和它的子目錄中所有文件所占空間大小。
搜索樹中的值
（1）最小值
（2）最大值
（3）搜索特定的值
移除一個節(jié)點(diǎn)
（1）移除一個葉子結(jié)點(diǎn)
（2）移除有一個左或右子節(jié)點(diǎn)的節(jié)點(diǎn)
（3）移除有兩個子節(jié)點(diǎn)的節(jié)點(diǎn)
