前言
前面介紹學習的大多是線性表相關(guān)的內(nèi)容，把指針搞懂后其實也沒有什么難度。規(guī)則相對是簡單的。
再數(shù)據(jù)結(jié)構(gòu)中樹、圖才是數(shù)據(jù)結(jié)構(gòu)標志性產(chǎn)物，(線性表大多都現(xiàn)成api可以使用),因為樹的難度相比線性表大一些并且樹的拓展性很強，你所知道的樹、二叉樹、二叉排序樹，AVL樹，線索二叉樹、紅黑樹、B數(shù)、線段樹等等高級數(shù)據(jù)結(jié)構(gòu)。然而二叉排序樹是所有的基礎(chǔ)，所以徹底搞懂二叉排序樹也是非常重要的。
樹
參考王道數(shù)據(jù)結(jié)構(gòu)
二叉樹也是樹的一種，而二叉排序樹又是二叉樹的一種。
- 樹是遞歸的，將樹的任何一個節(jié)點以及節(jié)點下的節(jié)點都能組合成一個新的樹。并且很多操作基于遞歸完成。
- 根節(jié)點： 最上面的那個節(jié)點(root)，根節(jié)點沒有前驅(qū)節(jié)點，只有子節(jié)點（0個或多個都可以）
- 層數(shù)： 一般認為根節(jié)點是第1層(有的也說第0層)。而樹的高度就是層數(shù)最高(上圖層數(shù)開始為1)節(jié)點的層數(shù)
- 節(jié)點關(guān)系: 父節(jié)點：就是鏈接該節(jié)點的上一層節(jié)點,孩子節(jié)點:和父節(jié)點對應(yīng)，上下關(guān)系。而祖先節(jié)點是父節(jié)點的父節(jié)點(或者祖先）節(jié)點。兄弟節(jié)點：擁有同一個父節(jié)點的節(jié)點們！
- 度： 節(jié)點的度就是節(jié)點擁有孩子節(jié)點的個數(shù)(是孩子不是子孫).而樹的度(最大)節(jié)點的度。同時，如果度大于0就成為分支節(jié)點,度等于0就成為葉子節(jié)點（沒有子孫）。
相關(guān)性質(zhì)：
- 樹的節(jié)點數(shù)=所有節(jié)點度數(shù)+1.
- 度為m的樹第i層最多有mi-1個節(jié)點。(i>=1)
- 高度而h的m叉樹最多（mh-1）/(m-1)個節(jié)點(等比數(shù)列求和)
- n個節(jié)點的m叉樹最小高度[logm(n(m-1)+1)]
二叉樹
二叉樹是一樹的一種，但應(yīng)用比較多，所以需要深入學習。二叉樹的每個節(jié)點最多只有兩個節(jié)點。
二叉樹與度為2的樹的區(qū)別：
- 一：度為2的的樹必須有三個節(jié)點以上，二叉樹可以為空。
- 二：二叉樹的度不一定為2：比如說斜樹。
- 三：二叉樹有左右節(jié)點區(qū)分，而度為2的樹沒有左右節(jié)點的區(qū)分。
幾種特殊二叉樹：
- 滿二叉樹。高度為n的滿二叉樹有2n-1個節(jié)點
- 完全二叉樹：上面一層全部滿，最下一層從左到右順序排列
- 二叉排序樹：樹按照一定規(guī)則插入排序(本文詳解)。
- 平衡二叉樹：樹上任意節(jié)點左子樹和右子樹深度差距不超過1.
二叉樹性質(zhì)：
相比樹，二叉樹的性質(zhì)就是樹的性質(zhì)更加具體化。
- 非空二叉樹葉子節(jié)點數(shù)=度為2的節(jié)點樹+1.本來一個節(jié)點如果度為1.那么一直延續(xù)就一個葉子，但如果出現(xiàn)一個度為2除了延續(xù)原來的一個節(jié)點，會多出一個節(jié)點需要維系。所以到最后會多出一個葉子。
- 非空第i層最多有2i-1個節(jié)點。
- 高為h的樹最多有2h-1個節(jié)點(等比求和)。
- 完全二叉樹若從左往右，從上到下編號如圖：
二叉排序(搜索)樹
概念
前面鋪墊那么多，咱們言歸正傳，詳細實現(xiàn)一個二叉排序樹。首先要了解二叉排序樹的規(guī)則：
- 從任意節(jié)點開始，節(jié)點左側(cè)節(jié)點值總比節(jié)點右側(cè)值要小。
- 例如。一個二叉排序樹依次插入15，6，23，7，4，71，5，50會形成下圖順序
構(gòu)造
首先二叉排序樹是由若干節(jié)點構(gòu)成。
- 對于node需要這些屬性：left，right，和value。其中l(wèi)eft和right是左右指針，而value是儲存的數(shù)據(jù)，這里用int 類型。
node類構(gòu)造為：
class node {//結(jié)點
public int value;
public node left;
public node right;
public node()
{
}
public node(int value)
{
this.value=value;
this.left=null;
this.right=null;
}
public node(int value,node l,node r)
{
this.value=value;
this.left=l;
this.right=r;
}
}
既然節(jié)點構(gòu)造好了，那么就需要節(jié)點等其他信息構(gòu)造成樹。有了鏈表構(gòu)造經(jīng)驗，很容易得知一棵樹最主要的還是root根節(jié)點。
所以樹的構(gòu)造為：
public class BinarySortTree {
node root;//根
public BinarySortTree()
{root=null;}
public void makeEmpty()//變空
{root=null;}
public boolean isEmpty()//查看是否為空
{return root==null;}
//各種方法
}
主要方法
- 既然已經(jīng)構(gòu)造號一棵樹，那么就需要實現(xiàn)主要的方法。因為二叉排序樹中每個節(jié)點都能看作一棵樹。所以我們創(chuàng)建方法的是時候加上節(jié)點參數(shù)(也就是函數(shù)對每一個節(jié)點都能有效)
findmax(),findmin()
findmin()找到最小節(jié)點：
- 因為所有節(jié)點的最小都是往左插入，所以只需要找到最左側(cè)的返回即可。
findmax()找到最大節(jié)點：
- 因為所有節(jié)點大的都是往右面插入，所以只需要找到最右側(cè)的返回即可。
- 代碼使用遞歸函數(shù)
public node findmin(node t)//查找最小返回值是node，調(diào)用查看結(jié)果時需要.value
{
if(t==null) {return null;}
else if(t.left==null) {return t;}
else return(findmin(t.left));
}
public node findmax(node t)//查找最大
{
if(t==null) {return null;}
else if(t.right==null) {return t;}
else return(findmax(t.right));
}
isContains(int x)
這里的意思是查找二叉查找樹中是否存在x。
- 假設(shè)我們我們插入x，那么如果存在x我們一定會在查找插入路徑的過程中遇到x。因為你可以如果已經(jīng)存在的點，再它的前方會走一次和它相同的步驟。也就是說前面固定，我來1w次x，那么x都會到達這個位置。那么我們直接進行查找比較即可！
public boolean isContains(int x)//是否存在
{
node current=root;
if(root==null) {return false;}
while(current.value!=x&¤t!=null)
{
if(x<current.value) {current=current.left;}
if(x>current.value) {current=current.right;}
if(current==null) {return false;}//在里面判斷如果超直接返回
}
//如果在這個位置判斷是否為空會導(dǎo)致current.value不存在報錯
if(current.value==x) {return true;}
return false;
}
insert(int x)
插入的思想和前面isContains類似。找到自己的位置(空位置)插入。但是又不太一樣。你可能會疑問為什么不直接找到最后一個空，然后將current賦值過去current=new node(x)。這樣的化current就相當于指向一個new node(x)節(jié)點。和樹就脫離關(guān)系，所以要提前判定是否為空，若為空將它的left或者right賦值即可。
public node insert(int x)// 插入 t是root的引用
{
node current = root;
if (root == null) {
root = new node(x);
return root;
}
while (current != null) {
if (x < current.value) {
if (current.left == null) {
return current.left = new node(x);}
else current = current.left;}
else if (x > current.value) {
if (current.right == null) {
return current.right = new node(x);}
else current = current.right;
}
}
return current;//其中用不到
}
- 比如說上面結(jié)構(gòu)插入51
delete(int x)
刪除操作算是一個相對較難理解的操作了。
刪除節(jié)點規(guī)則：
- 先找到這個點。這個點用這個點的子樹可以補上的點填充該點，然后在以這個點為頭刪除替代的子節(jié)點（調(diào)用遞歸）然后在添加到最后情況（只有一個分支，等等）。
- 首先要找到移除的位置，然后移除的那個點分類討論，如果有兩個兒子，就選右邊兒子的最左側(cè)那個點替代，然后再子樹刪除替代的那個點。如果是一個節(jié)點，判斷是左空還是右空，將這個點指向不空的那個。不空的那個就替代了這個節(jié)點。入股左右都是空，那么他自己變空null就刪除了。
刪除的節(jié)點沒有子孫:
- 這種情況不需要考慮，直接刪除即可。(途中紅色點)。另節(jié)點=null即可。
左節(jié)點為空、右節(jié)點為空：
- 此種情況也很容易，直接將刪除點的子節(jié)點放到被刪除位置即可。
左右節(jié)點均不空
- 這種情況相對是復(fù)雜的。因為這涉及到一個策略問題。
- 如果拿19或者71節(jié)點填補。雖然可以保證部分側(cè)大于小于該節(jié)點，但是會引起合并的混亂.比如你若用71替代23節(jié)點。那么你需要考慮三個節(jié)點(19,50,75)之間如何處理，還要考慮他們是否滿，是否有子女。這是個極其復(fù)雜的過程。
- 首先，我們要分析我們要的這個點的屬性：能夠繼承被刪除點的所有屬性。如果取左側(cè)節(jié)點(例如17)那么首先能滿足所有右側(cè)節(jié)點都比他大（右側(cè)比左側(cè)大）。那么就要再這邊選一個最大的點讓左半枝都比它小。我們分析左支最大的點一定是子樹最右側(cè)！
- 如果這個節(jié)點是最底層我們很好考慮，可以直接替換值，然后將最底層的點刪除即可。但是如果這個節(jié)點有左枝。我們該怎么辦？
- 這個分析起來也不難，用遞歸的思想啊。我們刪除這個節(jié)點，用可以滿足的節(jié)點替換了。會產(chǎn)生什么樣的后果？
- 多出個用過的19節(jié)點，轉(zhuǎn)化一下，在左子樹中刪除19的點！那么這個問題又轉(zhuǎn)化為刪除節(jié)點的問題，查找左子樹中有沒有能夠替代19這個點的。
所以整個刪除算法流程為：
代碼為
public node remove(int x, node t)// 刪除節(jié)點
{
if (t == null) {
return null;
}
if (x < t.value) {
t.left = remove(x, t.left);
} else if (x > t.value) {
t.right = remove(x, t.right);
} else if (t.left != null && t.right != null)// 左右節(jié)點均不空
{
t.value = findmin(t.right).value;// 找到右側(cè)最小值替代
t.right = remove(t.value, t.right);
} else // 左右單空或者左右都空
{
if (t.left == null && t.right == null) {
t = null;
} else if (t.right != null) {
t = t.right;
} else if (t.left != null) {
t = t.left;
}
return t;
}
return t;
}
完整代碼
二叉排序樹完整代碼為：
package 二叉樹;
import JAVA.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
public class BinarySortTree {
class node {// 結(jié)點
public int value;
public node left;
public node right;
public node() {
}
public node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
public node(int value, node l, node r) {
this.value = value;
this.left = l;
this.right = r;
}
}
node root;// 根
public BinarySortTree() {
root = null;
}
public void makeEmpty()// 變空
{
root = null;
}
public boolean isEmpty()// 查看是否為空
{
return root == null;
}
public node findmin(node t)// 查找最小返回值是node，調(diào)用查看結(jié)果時需要.value
{
if (t == null) {
return null;
} else if (t.left == null) {
return t;
} else
return (findmin(t.left));
}
public node findmax(node t)// 查找最大
{
if (t == null) {
return null;
} else if (t.right == null) {
return t;
} else
return (findmax(t.right));
}
public boolean isContains(int x)// 是否存在
{
node current = root;
if (root == null) {
return false;
}
while (current.value != x && current != null) {
if (x < current.value) {
current = current.left;
}
if (x > current.value) {
current = current.right;
}
if (current == null) {
return false;
} // 在里面判斷如果超直接返回
}
// 如果在這個位置判斷是否為空會導(dǎo)致current.value不存在報錯
if (current.value == x) {
return true;
}
return false;
}
public node insert(int x)// 插入 t是root的引用
{
node current = root;
if (root == null) {
root = new node(x);
return root;
}
while (current != null) {
if (x < current.value) {
if (current.left == null) {
return current.left = new node(x);}
else current = current.left;}
else if (x > current.value) {
if (current.right == null) {
return current.right = new node(x);}
else current = current.right;
}
}
return current;//其中用不到
}
public node remove(int x, node t)// 刪除節(jié)點
{
if (t == null) {
return null;
}
if (x < t.value) {
t.left = remove(x, t.left);
} else if (x > t.value) {
t.right = remove(x, t.right);
} else if (t.left != null && t.right != null)// 左右節(jié)點均不空
{
t.value = findmin(t.right).value;// 找到右側(cè)最小值替代
t.right = remove(t.value, t.right);
} else // 左右單空或者左右都空
{
if (t.left == null && t.right == null) {
t = null;
} else if (t.right != null) {
t = t.right;
} else if (t.left != null) {
t = t.left;
}
return t;
}
return t;
}
}
結(jié)語
- 這里我們優(yōu)先學習了樹，二叉樹，以及二叉搜素樹的基本構(gòu)造。對于二叉搜素樹插入查找比較容易理解但是實現(xiàn)的時候要注意函數(shù)對參數(shù)的引用等等。需要認真考慮。
- 而偏有難度的是二叉樹的刪除，利用一個遞歸的思想，要找到特殊情況和普通情況，遞歸一定程度也是問題的轉(zhuǎn)化(轉(zhuǎn)成自己相同問題，作用域減小)需要思考。
- 下面還會介紹二叉搜素樹的三序遍歷(遞歸和非遞歸).和層序遍歷。需要的朋友請持續(xù)關(guān)注。另外，筆者數(shù)據(jù)結(jié)構(gòu)專欄歡迎查房。！
- 如果對后端、爬蟲、數(shù)據(jù)結(jié)構(gòu)算法等感性趣歡迎關(guān)注我的個人公眾號交流：bigsai。回復(fù)爬蟲，數(shù)據(jù)結(jié)構(gòu)等有精美資料一份。
