溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了利用Java如何實(shí)現(xiàn)一個樹算法，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。
為什么使用樹：
樹結(jié)合了兩種數(shù)據(jù)結(jié)構(gòu)的有點(diǎn)：一種是有序數(shù)組，樹在查找數(shù)據(jù)項(xiàng)的速度和在有序數(shù)組中查找一樣快；另一種是鏈表，樹在插入數(shù)據(jù)和刪除數(shù)據(jù)項(xiàng)的速度和鏈表一樣。既然這樣，就要好好去學(xué)了....
(最主要討論的是二叉樹中的二叉搜索樹，即一個節(jié)點(diǎn)的左子節(jié)點(diǎn)關(guān)鍵值小于這個節(jié)點(diǎn)，右子節(jié)點(diǎn)的關(guān)鍵值大于這個節(jié)點(diǎn))
設(shè)計前的思考：
樹——>元素（節(jié)點(diǎn)）
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é)點(diǎn)
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é)點(diǎn)
inOrder(localRoot.right) ;//調(diào)用自身來遍歷右子樹
}
}查找某個節(jié)點(diǎn)：
//查找某個節(jié)點(diǎn)
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é)點(diǎn)
最小值：不斷地尋找左子節(jié)點(diǎn)
//查找關(guān)鍵字最小的節(jié)點(diǎn)
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é)點(diǎn)：
思考：
1).先找到要刪除的節(jié)點(diǎn)：
public boolean delete(int key)
{
//先找到需要刪除的節(jié)點(diǎn)
Node current = root ;
Node parent = root ;
boolean isLeftChild = false ;
while(current.iData != key)//顯然，當(dāng)current.iData == key 時，current 就是要找的節(jié)點(diǎn)
{
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é)點(diǎn)是怎樣的節(jié)點(diǎn)，經(jīng)分析，有三種情況：葉節(jié)點(diǎn)、有一個節(jié)點(diǎn)的節(jié)點(diǎn)、有兩個節(jié)點(diǎn)的節(jié)點(diǎn)
A).如果刪除的是一個葉子節(jié)點(diǎn)，直接刪除即可
//接上................
//分情況考慮刪除的節(jié)點(diǎn)
//刪除的節(jié)點(diǎn)為葉節(jié)點(diǎn)時
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é)點(diǎn)有一個節(jié)點(diǎn)時：分兩種情況，刪除的節(jié)點(diǎn)只有一個左子節(jié)點(diǎn)，或者只有一個右子節(jié)點(diǎn)
//接上.......
//刪除的節(jié)點(diǎn)有一個子節(jié)點(diǎn)
else
if(current.right == null)//刪除的節(jié)點(diǎn)只有一個左子節(jié)點(diǎn)時
{
if(current == root)//要刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)
root = current.left ;
else
if(isLeftChild)//要刪除的節(jié)點(diǎn)是一個左子節(jié)點(diǎn)
parent.left = current.left ;
else
parent.right = current.left ;//要刪除的節(jié)點(diǎn)是一個右子節(jié)點(diǎn)
}
else
if(current.left == null)//刪除的節(jié)點(diǎn)只有一個右子節(jié)點(diǎn)時
{
if(current == root)//要刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)
root = current.right ;
else
if(isLeftChild)//要刪除的節(jié)點(diǎn)是一個左子節(jié)點(diǎn)
parent.left = current.right ;
else
parent.right = current.right ;//要刪除的節(jié)點(diǎn)是一個右子節(jié)點(diǎn)
}
//continue.......c).如果刪除的節(jié)點(diǎn)有兩個節(jié)點(diǎn)時：
這種情況就比較復(fù)雜，需要去尋找一個節(jié)點(diǎn)去替代要刪除的節(jié)點(diǎn)。這個節(jié)點(diǎn)應(yīng)該是什么節(jié)點(diǎn)呢？
據(jù)書本介紹，最合適的節(jié)點(diǎn)是后繼節(jié)點(diǎn)，即比要刪除的節(jié)點(diǎn)的關(guān)鍵值次高的節(jié)點(diǎn)是它的后繼節(jié)點(diǎn)。
說得簡單一些，后繼節(jié)點(diǎn)就是比要刪除的節(jié)點(diǎn)的關(guān)鍵值要大的節(jié)點(diǎn)集合中的最小值。
以上面的為例，40的后繼節(jié)點(diǎn)為74,10的后繼節(jié)點(diǎn)是13,19的后繼節(jié)點(diǎn)時26
以下是尋找后繼節(jié)點(diǎn)的代碼：
//返回后繼節(jié)點(diǎn)
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode ;//后繼節(jié)點(diǎn)的父節(jié)點(diǎn)
Node successor = delNode ;//后繼節(jié)點(diǎn)
Node current = delNode.right ;//移動到位置節(jié)點(diǎn)位置
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é)點(diǎn)，接著就要討論如何用后繼節(jié)點(diǎn)替代藥刪除的節(jié)點(diǎn)
a)如果后繼節(jié)點(diǎn)是剛好是要刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)（此時可以知道，這個右子節(jié)點(diǎn)沒有左子點(diǎn)，如果有，就不該這個右子節(jié)點(diǎn)為后繼節(jié)點(diǎn)）
//要刪除的節(jié)點(diǎn)為左子節(jié)點(diǎn)時 parent.left = successor ; successor.left = current.left ; //要刪除的節(jié)點(diǎn)是右子節(jié)點(diǎn)時 parent.right = successor ; successor.left = current.left ;
b)如果后繼節(jié)點(diǎn)為要刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)的左后代：
//假如要刪除的節(jié)點(diǎn)為右子節(jié)點(diǎn) successorParent.left = successor.right ;//第一步 successor.right = current.right ;//第二步 parent.right = successor ; successor.left = current.left ; //假設(shè)要刪除的節(jié)點(diǎn)為左子節(jié)點(diǎn) successorParent.left = successor.right ; successor.right = current.right ; parent.left = successor ; successor.left = current.left ;
注意：第一步和第二步在getSuccessor()方法的最后的if語句中完成
以下是刪除的節(jié)點(diǎn)有連個節(jié)點(diǎn)的代碼：
//接上
//刪除的節(jié)點(diǎn)有兩個子節(jié)點(diǎn)
else
{
Node successor = getSuccessor(current) ;//找到后繼節(jié)點(diǎn)
if(current == root)
root = successor ;
else
if(isLeftChild)
parent.left = successor ;
else
parent.right = successor ;
successor.left = current.left ;
}
//continue....綜合上述，給出delete()方法的代碼：
//刪除某個節(jié)點(diǎn)
public boolean delete(int key)
{
//先找到需要刪除的節(jié)點(diǎn)
Node current = root ;
Node parent = root ;
boolean isLeftChild = false ;
while(current.iData != key)//顯然，當(dāng)current.iData == key 時，current 就是要找的節(jié)點(diǎn)
{
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é)點(diǎn)
//刪除的節(jié)點(diǎn)為葉節(jié)點(diǎn)時
if(current.left == null && current.right == null)
{
if(current == root)
root = null ;
else
if(isLeftChild)
parent.left = null ;
else
parent.right = null ;
}
//刪除的節(jié)點(diǎn)有一個子節(jié)點(diǎn)
else
if(current.right == null)//刪除的節(jié)點(diǎn)只有一個左子節(jié)點(diǎn)時
{
if(current == root)//要刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)
root = current.left ;
else
if(isLeftChild)//要刪除的節(jié)點(diǎn)是一個左子節(jié)點(diǎn)
parent.left = current.left ;
else
parent.right = current.left ;//要刪除的節(jié)點(diǎn)是一個右子節(jié)點(diǎn)
}
else
if(current.left == null)//刪除的節(jié)點(diǎn)只有一個右子節(jié)點(diǎn)時
{
if(current == root)//要刪除的節(jié)點(diǎn)為根節(jié)點(diǎn)
root = current.right ;
else
if(isLeftChild)//要刪除的節(jié)點(diǎn)是一個左子節(jié)點(diǎn)
parent.left = current.right ;
else
parent.right = current.right ;//要刪除的節(jié)點(diǎn)是一個右子節(jié)點(diǎn)
}
//刪除的節(jié)點(diǎn)有兩個子節(jié)點(diǎn)
else
{
Node successor = getSuccessor(current) ;//找到后繼節(jié)點(diǎn)
if(current == root)
root = successor ;
else
if(isLeftChild)
parent.left = successor ;
else
parent.right = successor ;
successor.left = current.left ;
}
return true ;
}進(jìn)一步考慮：
刪除那么復(fù)雜，那刪除是必要的嗎?我們可以給每個節(jié)點(diǎn)定義一個標(biāo)志，該標(biāo)志用于記錄該節(jié)點(diǎn)是否已經(jīng)刪除了，顯示樹時，先判斷該節(jié)點(diǎn)是否已經(jīng)刪除，如果沒有，則顯示。
這樣的結(jié)果是，節(jié)點(diǎn)其實(shí)是沒有刪除的，這樣顯然逃避責(zé)任了。當(dāng)樹中沒有那么多的刪除操作時，這也不失為一種好方法，例如：
已經(jīng)離職的員工的檔案要永久地保存在員工的記錄中。
上述內(nèi)容就是利用Java如何實(shí)現(xiàn)一個樹算法，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼