[[391293]]

前言

前面介紹學(xué)習(xí)的大多是線性表相關(guān)的內(nèi)容，把指針搞懂后其實也沒有什么難度，規(guī)則相對是簡單的，后面會講解一些比較常見的數(shù)據(jù)結(jié)構(gòu)，用多圖的方式讓大家更容易吸收。

在數(shù)據(jù)結(jié)構(gòu)與算法中，樹是一個比較大的家族，家族中有很多厲害的成員，這些成員有二叉樹和多叉樹(例如B+樹等)，而二叉樹的大家族中，二叉搜索樹(又稱二叉排序樹)是最最基礎(chǔ)的，在這基礎(chǔ)上才能繼續(xù)拓展學(xué)習(xí)AVL(二叉平衡樹)、紅黑樹等知識。

對于二叉排序樹而言，本章重點關(guān)注其實現(xiàn)方式以及插入、刪除步驟流程，我們會手寫一個二叉排序樹，二叉樹遍歷部分的內(nèi)容比較多會單獨詳細(xì)講解。

什么是樹

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=1)個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

 

樹是遞歸的，將樹的任何一個節(jié)點以及節(jié)點下的節(jié)點都能組合成一個新的樹，所以樹的很多問題都是使用遞歸去完成。

根節(jié)點： 最上面的那個節(jié)點(root)，根節(jié)點沒有父節(jié)點，只有子節(jié)點(0個或多個都可以)

層數(shù)： 一般認(rèn)為根節(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é)點中最大 (節(jié)點的度)。同時，如果度大于0的節(jié)點是分支節(jié)點,度等于0的節(jié)點是葉子節(jié)點(沒有子孫)。

相關(guān)性質(zhì)：

二叉樹

二叉樹是一樹的一種，但應(yīng)用比較多，所以需要深入學(xué)習(xí)，二叉樹的每個節(jié)點最多只有兩個子節(jié)點(但不一定非得要有兩個節(jié)點)。

二叉樹與度為2的樹的區(qū)別：

1、度為2的的樹必須有三個節(jié)點以上(否則就不叫度為二了，一定要先存在)，二叉樹可以為空。

2、二叉樹的度不一定為2,比如斜樹。

3、二叉樹有左右節(jié)點區(qū)分，而度為2的樹沒有左右節(jié)點的區(qū)分。

幾種特殊二叉樹：

滿二叉樹：高度為n的滿二叉樹有(2^n) -1個節(jié)點

滿二叉樹

完全二叉樹：上面一層全部滿，最下一層從左到右順序排列

完全二叉樹

二叉排序樹：樹按照一定規(guī)則插入排序(本文詳解)。

平衡二叉樹：樹上任意節(jié)點左子樹和右子樹深度差距不超過1(后文詳解).

二叉樹性質(zhì)：

1、二叉樹有用樹的性質(zhì)

2、非空二叉樹葉子節(jié)點數(shù)=度為2的節(jié)點數(shù)+1.本來一個節(jié)點如果度為1.那么一直延續(xù)就一個葉子，但如果出現(xiàn)一個度為2除了延續(xù)原來的一個節(jié)點，會多出一個節(jié)點需要維系。所以到最后會多出一個葉子。

3、非空第i層最多有2^(i-1)個節(jié)點。

4、高為h的樹最多有(2^h)-1個節(jié)點(等比求和)。

二叉樹一般用鏈?zhǔn)酱鎯Γ@樣內(nèi)存利用更高，但二叉樹也可以用數(shù)組存儲的(經(jīng)常會遇到)，各個節(jié)點對應(yīng)的下標(biāo)是可以計算出來的，就拿一個完全二叉樹若從左往右，從上到下編號如圖：

二叉樹節(jié)點位置對應(yīng)關(guān)系

二叉排序(搜索)樹

概念

前面鋪墊那么多，咱們言歸正傳，詳細(xì)講解并實現(xiàn)一個二叉排序樹，二叉搜索樹擁有二叉樹的性質(zhì)，同時有一些自己的規(guī)則：

首先要了解二叉排序樹的規(guī)則：從任意節(jié)點開始，節(jié)點左側(cè)節(jié)點值總比節(jié)點右側(cè)值要小。

例如一個二叉排序樹依次插入15，6，23，7，4，71，5，50會形成下圖順序

 

一個二叉排序樹

構(gòu)造

二叉排序樹是由若干節(jié)點(node)構(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;} 
    //各種方法 
} 

可以用圖來表示一下這個結(jié)構(gòu)：

 

主要方法

既然已經(jīng)構(gòu)造好一棵樹，那么就需要實現(xiàn)主要的方法,因為二叉排序樹中每個節(jié)點都能看作一棵樹。所以我們創(chuàng)建方法的是時候加上節(jié)點參數(shù)(方便一些遞歸調(diào)用)

findmax(),findmin()

findmin()找到最小節(jié)點：

因為所有節(jié)點的最小都是往左插入，所以只需要找到最左側(cè)的返回即可，具體實現(xiàn)可使用遞歸也可非遞歸while循環(huán)。

findmax()找到最大節(jié)點：

因為所有節(jié)點大的都是往右面插入，所以只需要找到最右側(cè)的返回即可，實現(xiàn)方法與findmin()方法一致。

代碼使用遞歸函數(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的節(jié)點。

在具體實現(xiàn)上，根據(jù)二叉排序樹左側(cè)更小，右側(cè)更大的性質(zhì)進(jìn)行往下查找，如果找到值為x的節(jié)點則返回true，如果找不到就返回false，當(dāng)然實現(xiàn)上可以采用遞歸或者非遞歸，我這里使用非遞歸的方式。

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;        
} 

insert(int x)

插入的思想和前面isContains(int x)類似，找到自己的位置(空位置)插入。

但是具體實現(xiàn)上有需要注意的地方，我們要到待插入位置上一層節(jié)點，你可能會疑問為什么不直接找到最后一個空，然后將current賦值過去current=new node(x)，這樣的化current就相當(dāng)于指向一個new node(x)節(jié)點，和原來樹就脫離關(guān)系(原樹相當(dāng)于沒有任何操作)，所以要提前通過父節(jié)點判定是否為空找到位置，找到合適位置通過父節(jié)點的left或者right節(jié)點指向新創(chuàng)建的節(jié)點才能完成插入的操作。

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;//其中用不到 
} 

比如說上面樹插入值為51的節(jié)點。

插入值為51的節(jié)點

delete(int x)

刪除操作算是一個相對較難理解的操作了，因為待刪除的點可能在不同位置所以具體處理的方式也不同，如果是葉子即可可直接刪除，有一個孩子節(jié)點用子節(jié)點替換即可，有兩個子節(jié)點的就要先找到值距離待刪除節(jié)點最近的點(左子樹最大點或者右子樹最小點)，將值替換掉然后遞歸操作在子樹中刪除已經(jīng)替換的節(jié)點，當(dāng)然沒具體分析可以看下面：

刪除的節(jié)點沒有子孫:

這種情況不需要考慮，直接刪除即可(節(jié)點=null即可)(圖中紅色點均滿足這種方式)。

待刪除節(jié)點為葉子節(jié)點

一個子節(jié)點為空：

此種情況也很容易，直接將刪除點的子節(jié)點放到被刪除位置即可。

 

待刪除節(jié)點有1個孩子

左右節(jié)點均不空

左右孩子節(jié)點都不為空這種情況是相對比較復(fù)雜的，因為不能直接用其中一個孩子節(jié)點替代當(dāng)前節(jié)點(放不下，如果孩子節(jié)點也有兩個孩子那么有一個節(jié)點無法放，例如拿下面71節(jié)點替代)

 

待刪除節(jié)點有兩個孩子

如果拿19或者71節(jié)點填補。雖然可以保證部分側(cè)大于小于該節(jié)點，但是會引起合并的混亂.比如你若用71替代23節(jié)點。那么你需要考慮三個節(jié)點(19,50,75)之間如何處理，還要考慮他們是否滿，是否有子女，這是個復(fù)雜的過程，不適合考慮。

所以，我們要分析我們要的這個點的屬性：能夠保證該點在這個位置仍滿足二叉搜索樹的性質(zhì)(找到值最近的)，那么子樹中哪個節(jié)點滿足這樣的關(guān)系呢?

左子樹中最右側(cè)節(jié)點或者右子樹中最左側(cè)節(jié)點都滿足，我們可以選一個節(jié)點將待刪除節(jié)點值替換掉(這里替換成左子樹最右側(cè)節(jié)點)。

這個點替換之后該怎么辦呢?很簡單啊，二叉樹用遞歸思路解決問題，再次調(diào)用刪除函數(shù)在左子樹中刪除替換的節(jié)點即可。

 

先替換值再遞歸在子樹中刪除18節(jié)點

這里演示是選取左子樹最大節(jié)點(最右側(cè))替代，當(dāng)然使用右子樹最小節(jié)點也能滿足在這待刪除的大小關(guān)系，原理一致。整個刪除算法流程為：

刪除流程

這部分操作的代碼為：

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; 
} 

完整代碼

這個完整代碼是筆者在大三時候?qū)懙模赡苡胁簧偈杪┗蛘卟灰?guī)范的地方，僅供學(xué)習(xí)參考，如有疏漏錯誤還請指正。

二叉排序樹完整代碼為：

結(jié)語

這里我們學(xué)習(xí)了解了樹、二叉樹、以及二叉搜素樹，對于二叉搜素樹插入查找比較容易理解，但是實現(xiàn)的時候要注意函數(shù)參數(shù)的引用等等。

偏有難度的是二叉樹的刪除，利用一個遞歸的思想，分類討論待刪除情況，要找到特殊情況和普通情況，遞歸一定程度也是問題的轉(zhuǎn)化(轉(zhuǎn)成自己相同問題，作用域減小)需要思考。

下面還會介紹二叉樹的三序遍歷(遞歸和非遞歸)和層序遍歷。這些都是比較經(jīng)典熱門的問題需要深入了解。