Java數(shù)據(jù)結(jié)構(gòu)與算法之樹(動力節(jié)點java學(xué)院整理)
為什么使用樹：
樹結(jié)合了兩種數(shù)據(jù)結(jié)構(gòu)的有點：一種是有序數(shù)組，樹在查找數(shù)據(jù)項的速度和在有序數(shù)組中查找一樣快；另一種是鏈表，樹在插入數(shù)據(jù)和刪除數(shù)據(jù)項的速度和鏈表一樣。既然這樣，就要好好去學(xué)了....
(最主要討論的是二叉樹中的二叉搜索樹，即一個節(jié)點的左子節(jié)點關(guān)鍵值小于這個節(jié)點，右子節(jié)點的關(guān)鍵值大于這個節(jié)點)
設(shè)計前的思考：
樹——>元素（節(jié)點）
class Node
{
public int iData ;
public float fData ;
public Node left ;
public Node right ;
//方法
public Node(int iData,float fData){}
public void displayNode(){}
}
class Tree
{
Node root ;//樹根
//方法
public void insert(){}
public void displayTree(){}
public void find(){}
public void delete(){}
}
插入數(shù)據(jù)：
//插入子節(jié)點
public void insert(int iData ,float fData)
{
Node newNode = new Node(iData,fData) ;
if(root == null)
root = newNode ;
else
{
Node current = root ;
Node parent ;
while(true)//尋找插入的位置
{
parent = current ;
if(iData<current.iData)
{
current = current.left ;
if(current == null)
{
parent.left = newNode ;
return ;
}
}
else
{
current =current.right ;
if(current == null)
{
parent.right = newNode ;
return ;
}
}
}
}
}
遍歷樹：
//中序遍歷方法
public void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.left) ;//調(diào)用自身來遍歷左子樹
localRoot.displayNode() ;//訪問這個節(jié)點
inOrder(localRoot.right) ;//調(diào)用自身來遍歷右子樹
}
}
查找某個節(jié)點：
//查找某個節(jié)點
public Node find(int iData)
{
Node current = root ;
while(current.iData != iData)
{
if(current.iData<iData)
current = current.right ;
else
current = current.left ;
if(current == null)
return null ;
}
return current ;
}
查找樹中關(guān)鍵字的最大值和最小值：
最大值：不斷地尋找右子節(jié)點
最小值：不斷地尋找左子節(jié)點
//查找關(guān)鍵字最小的節(jié)點
public Node findMinNode()
{
Node current , last ;
last = null ;
current = root ;
if(current.left == null)
return current ;
else
{
while(current != null)
{
last = current ;
current = current.left ;
}
return last ;
}
}
刪除某個節(jié)點：
思考：
1).先找到要刪除的節(jié)點：
public boolean delete(int key)
{
//先找到需要刪除的節(jié)點
Node current = root ;
Node parent = root ;
boolean isLeftChild = false ;
while(current.iData != key)//顯然，當current.iData == key 時，current 就是要找的節(jié)點
{
parent = current ;
if(key < current.iData)
{
isLeftChild = true ;
current = current.left ;
}
else
{
isLeftChild = false ;
current = current.right ;
}
if(current == null)//找不到key時返回false
return false ;
}
//continue ........
}
2).再考慮要刪除的節(jié)點是怎樣的節(jié)點，經(jīng)分析，有三種情況：葉節(jié)點、有一個節(jié)點的節(jié)點、有兩個節(jié)點的節(jié)點
A).如果刪除的是一個葉子節(jié)點，直接刪除即可
//接上................
//分情況考慮刪除的節(jié)點
//刪除的節(jié)點為葉節(jié)點時
if(current.left == null && current.right == null)
{
if(current == root)
root = null ;
else
if(isLeftChild)
parent.left = null ;
else
parent.right = null ;
}
//continue...........
B).如果刪除的節(jié)點有一個節(jié)點時：分兩種情況，刪除的節(jié)點只有一個左子節(jié)點，或者只有一個右子節(jié)點
//接上.......
//刪除的節(jié)點有一個子節(jié)點
else
if(current.right == null)//刪除的節(jié)點只有一個左子節(jié)點時
{
if(current == root)//要刪除的節(jié)點為根節(jié)點
root = current.left ;
else
if(isLeftChild)//要刪除的節(jié)點是一個左子節(jié)點
parent.left = current.left ;
else
parent.right = current.left ;//要刪除的節(jié)點是一個右子節(jié)點
}
else
if(current.left == null)//刪除的節(jié)點只有一個右子節(jié)點時
{
if(current == root)//要刪除的節(jié)點為根節(jié)點
root = current.right ;
else
if(isLeftChild)//要刪除的節(jié)點是一個左子節(jié)點
parent.left = current.right ;
else
parent.right = current.right ;//要刪除的節(jié)點是一個右子節(jié)點
}
//continue.......
c).如果刪除的節(jié)點有兩個節(jié)點時：
這種情況就比較復(fù)雜，需要去尋找一個節(jié)點去替代要刪除的節(jié)點。這個節(jié)點應(yīng)該是什么節(jié)點呢？
據(jù)書本介紹，最合適的節(jié)點是后繼節(jié)點，即比要刪除的節(jié)點的關(guān)鍵值次高的節(jié)點是它的后繼節(jié)點。
說得簡單一些，后繼節(jié)點就是比要刪除的節(jié)點的關(guān)鍵值要大的節(jié)點集合中的最小值。
以上面的為例，40的后繼節(jié)點為74,10的后繼節(jié)點是13,19的后繼節(jié)點時26
以下是尋找后繼節(jié)點的代碼：
//返回后繼節(jié)點
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode ;//后繼節(jié)點的父節(jié)點
Node successor = delNode ;//后繼節(jié)點
Node current = delNode.right ;//移動到位置節(jié)點位置
while(current != null)
{
successorParent = successor ;
successor = current ;
current = current.left ;
}
if(successor != delNode.right)
{
successorParent.left = successor.right ;
successor.right = delNode.right ;
}
return successor ;
}
找到了后繼節(jié)點，接著就要討論如何用后繼節(jié)點替代藥刪除的節(jié)點
a)如果后繼節(jié)點是剛好是要刪除節(jié)點的右子節(jié)點（此時可以知道，這個右子節(jié)點沒有左子點，如果有，就不該這個右子節(jié)點為后繼節(jié)點）
//要刪除的節(jié)點為左子節(jié)點時 parent.left = successor ; successor.left = current.left ; //要刪除的節(jié)點是右子節(jié)點時 parent.right = successor ; successor.left = current.left ;
b)如果后繼節(jié)點為要刪除節(jié)點的右子節(jié)點的左后代：
//假如要刪除的節(jié)點為右子節(jié)點 successorParent.left = successor.right ;//第一步 successor.right = current.right ;//第二步 parent.right = successor ; successor.left = current.left ; //假設(shè)要刪除的節(jié)點為左子節(jié)點 successorParent.left = successor.right ; successor.right = current.right ; parent.left = successor ; successor.left = current.left ;
注意：第一步和第二步在getSuccessor()方法的最后的if語句中完成
以下是刪除的節(jié)點有連個節(jié)點的代碼：
//接上
//刪除的節(jié)點有兩個子節(jié)點
else
{
Node successor = getSuccessor(current) ;//找到后繼節(jié)點
if(current == root)
root = successor ;
else
if(isLeftChild)
parent.left = successor ;
else
parent.right = successor ;
successor.left = current.left ;
}
//continue....
綜合上述，給出delete()方法的代碼：
//刪除某個節(jié)點
public boolean delete(int key)
{
//先找到需要刪除的節(jié)點
Node current = root ;
Node parent = root ;
boolean isLeftChild = false ;
while(current.iData != key)//顯然，當current.iData == key 時，current 就是要找的節(jié)點
{
parent = current ;
if(key < current.iData)
{
isLeftChild = true ;
current = current.left ;
}
else
{
isLeftChild = false ;
current = current.right ;
}
if(current == null)//找不到key時返回false
return false ;
}
//分情況考慮刪除的節(jié)點
//刪除的節(jié)點為葉節(jié)點時
if(current.left == null && current.right == null)
{
if(current == root)
root = null ;
else
if(isLeftChild)
parent.left = null ;
else
parent.right = null ;
}
//刪除的節(jié)點有一個子節(jié)點
else
if(current.right == null)//刪除的節(jié)點只有一個左子節(jié)點時
{
if(current == root)//要刪除的節(jié)點為根節(jié)點
root = current.left ;
else
if(isLeftChild)//要刪除的節(jié)點是一個左子節(jié)點
parent.left = current.left ;
else
parent.right = current.left ;//要刪除的節(jié)點是一個右子節(jié)點
}
else
if(current.left == null)//刪除的節(jié)點只有一個右子節(jié)點時
{
if(current == root)//要刪除的節(jié)點為根節(jié)點
root = current.right ;
else
if(isLeftChild)//要刪除的節(jié)點是一個左子節(jié)點
parent.left = current.right ;
else
parent.right = current.right ;//要刪除的節(jié)點是一個右子節(jié)點
}
//刪除的節(jié)點有兩個子節(jié)點
else
{
Node successor = getSuccessor(current) ;//找到后繼節(jié)點
if(current == root)
root = successor ;
else
if(isLeftChild)
parent.left = successor ;
else
parent.right = successor ;
successor.left = current.left ;
}
return true ;
}
進一步考慮：
刪除那么復(fù)雜，那刪除是必要的嗎?我們可以給每個節(jié)點定義一個標志，該標志用于記錄該節(jié)點是否已經(jīng)刪除了，顯示樹時，先判斷該節(jié)點是否已經(jīng)刪除，如果沒有，則顯示。
這樣的結(jié)果是，節(jié)點其實是沒有刪除的，這樣顯然逃避責(zé)任了。當樹中沒有那么多的刪除操作時，這也不失為一種好方法，例如：
已經(jīng)離職的員工的檔案要永久地保存在員工的記錄中。
以上所述是小編給大家介紹的Java數(shù)據(jù)結(jié)構(gòu)與算法之樹(動力節(jié)點java學(xué)院整理)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
相關(guān)文章
這篇文章主要介紹了SpringBoot使用JPA實現(xiàn)查詢部分字段方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
Java強制類型轉(zhuǎn)換原理詳解(父類轉(zhuǎn)子類、子類轉(zhuǎn)父類)
這篇文章主要給大家介紹了關(guān)于Java強制類型轉(zhuǎn)換原理(父類轉(zhuǎn)子類、子類轉(zhuǎn)父類)的相關(guān)資料,所謂的強制類型轉(zhuǎn)換,其實是自動類型轉(zhuǎn)換的逆過程,在數(shù)據(jù)類型兼容的情況下,將容量大的數(shù)據(jù)類型轉(zhuǎn)換為容量小的數(shù)據(jù)類型,需要的朋友可以參考下2023-12-12
這篇文章主要給大家介紹了關(guān)于JAVA中Collections.sort()方法使用的相關(guān)資料,Java中Collections.sort()方法是用來對List類型進行排序的,文中通過代碼將使用的方法介紹的非常詳細,需要的朋友可以參考下2024-05-05
這篇文章主要介紹了Mybatis批量插入和批量更新失敗問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-08-08
這篇文章主要介紹了淺談自定義注解在Spring中的應(yīng)用，具有一定借鑒價值，需要的朋友可以參考下。2017-12-12
Mybatis CachingExecutor二級緩存使用示例詳解
這篇文章主要介紹了?Mybatis的CachingExecutor與二級緩存使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-09-09
MyBatis實現(xiàn)表連接查詢寫法(三種對應(yīng)關(guān)系)的方法總結(jié)
這篇文章主要介紹了MyBatis實現(xiàn)表連接查詢寫法(一對一關(guān)系、一對多關(guān)系、多對多關(guān)系)的方法，文中的示例代碼講解詳細，感興趣的可以了解一下2023-01-01
這篇文章主要介紹了springboot如何獲取接口下所有實現(xiàn)類問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-09-09
這篇文章主要介紹了Java中間消息件ActiveMQ使用實例,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-11-11
原來的版本是2.3.x，由于安全原因需要升級到2.5.2。但是在升級過程中遇到各種各樣的問題，下面小編給大家?guī)砹藄truts升級到2.5.2遇到的問題及解決方案，需要的朋友參考下吧2016-11-11