Java數(shù)據(jù)結(jié)構與算法之樹(動力節(jié)點java學院整理)
為什么使用樹：
樹結(jié)合了兩種數(shù)據(jù)結(jié)構的有點：一種是有序數(shù)組，樹在查找數(shù)據(jù)項的速度和在有序數(shù)組中查找一樣快；另一種是鏈表，樹在插入數(shù)據(jù)和刪除數(shù)據(jù)項的速度和鏈表一樣。既然這樣，就要好好去學了....
(最主要討論的是二叉樹中的二叉搜索樹，即一個節(jié)點的左子節(jié)點關鍵值小于這個節(jié)點，右子節(jié)點的關鍵值大于這個節(jié)點)
設計前的思考：
樹——>元素（節(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 ;
}
查找樹中關鍵字的最大值和最小值：
最大值：不斷地尋找右子節(jié)點
最小值：不斷地尋找左子節(jié)點
//查找關鍵字最小的節(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é)點時：
這種情況就比較復雜，需要去尋找一個節(jié)點去替代要刪除的節(jié)點。這個節(jié)點應該是什么節(jié)點呢？
據(jù)書本介紹，最合適的節(jié)點是后繼節(jié)點，即比要刪除的節(jié)點的關鍵值次高的節(jié)點是它的后繼節(jié)點。
說得簡單一些，后繼節(jié)點就是比要刪除的節(jié)點的關鍵值要大的節(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 ; //假設要刪除的節(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 ;
}
進一步考慮：
刪除那么復雜，那刪除是必要的嗎?我們可以給每個節(jié)點定義一個標志，該標志用于記錄該節(jié)點是否已經(jīng)刪除了，顯示樹時，先判斷該節(jié)點是否已經(jīng)刪除，如果沒有，則顯示。
這樣的結(jié)果是，節(jié)點其實是沒有刪除的，這樣顯然逃避責任了。當樹中沒有那么多的刪除操作時，這也不失為一種好方法，例如：
已經(jīng)離職的員工的檔案要永久地保存在員工的記錄中。
以上所述是小編給大家介紹的Java數(shù)據(jù)結(jié)構與算法之樹(動力節(jié)點java學院整理)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
相關文章
Java后端WebSocket的Tomcat實現(xiàn)
這篇文章主要介紹了Java后端WebSocket的Tomcat實現(xiàn)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-06-06
4位吸血鬼數(shù)字的java實現(xiàn)思路與實例講解
今天小編就為大家分享一篇關于4位吸血鬼數(shù)字的java實現(xiàn)思路與實例講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03
SpringBoot配置Druid數(shù)據(jù)監(jiān)控代碼實例
這篇文章主要介紹了SpringBoot配置Druid數(shù)據(jù)監(jiān)控代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-06-06
教你用java實現(xiàn)學生成績管理系統(tǒng)(附詳細代碼)
教學管理系統(tǒng)很適合初學者對于所學語言的練習,下面這篇文章主要給大家介紹了關于如何用java實現(xiàn)學生成績管理系統(tǒng)的相關資料,文中給出了詳細的實例代碼,需要的朋友可以參考下2023-06-06
Java中final,finally,finalize三個關鍵字的區(qū)別_動力節(jié)點Java學院整理
這篇文章給大家收集整理了有關java中final,finally,finalize三個關鍵字的區(qū)別介紹，非常不錯，具有參考借鑒價值，需要的的朋友參考下吧2017-04-04
Mybatis-Plus中update()和updateById()將字段更新為null
本文主要介紹了Mybatis-Plus中update()和updateById()將字段更新為null，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-08-08
Java 中的 Object 方法在面試中是一個非常高頻的點，本文主要介紹了Java中Object類常用的12個方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
LongAdder類是JDK1.8新增的一個原子性操作類。AtomicLong通過CAS算法提供了非阻塞的原子性操作,因為非常搞并發(fā)的請求下AtomicLong的性能是不能讓人接受的2021-06-06
在我們?nèi)粘Ｊ褂胘son序列化框架過程中，經(jīng)常會遇到在輸出json字符串時，忽略某些字段，那么在Gson框架中，要想實現(xiàn)這種方式，可以怎么處理呢，本文就來介紹一下2021-10-10
這篇文章主要介紹了springBoot無法解析yml問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06