Java數(shù)據(jù)結(jié)構(gòu)與算法之樹(shù)(動(dòng)力節(jié)點(diǎn)java學(xué)院整理)

更新時(shí)間：2017年04月11日 17:28:41 投稿：mrr

這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)與算法之樹(shù)的相關(guān)知識(shí)，最主要的是二叉樹(shù)中的二叉搜索樹(shù)，需要的朋友可以參考下

為什么使用樹(shù)：

樹(shù)結(jié)合了兩種數(shù)據(jù)結(jié)構(gòu)的有點(diǎn)：一種是有序數(shù)組，樹(shù)在查找數(shù)據(jù)項(xiàng)的速度和在有序數(shù)組中查找一樣快；另一種是鏈表，樹(shù)在插入數(shù)據(jù)和刪除數(shù)據(jù)項(xiàng)的速度和鏈表一樣。既然這樣，就要好好去學(xué)了....
(最主要討論的是二叉樹(shù)中的二叉搜索樹(shù)，即一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)關(guān)鍵值小于這個(gè)節(jié)點(diǎn)，右子節(jié)點(diǎn)的關(guān)鍵值大于這個(gè)節(jié)點(diǎn))

設(shè)計(jì)前的思考：

樹(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 ;//樹(shù)根
 //方法
 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 ;
 }
 }
 }
 }
 }

遍歷樹(shù)：

//中序遍歷方法
 public void inOrder(Node localRoot)
 {
 if(localRoot != null)
 {
 inOrder(localRoot.left) ;//調(diào)用自身來(lái)遍歷左子樹(shù)
 localRoot.displayNode() ;//訪問(wèn)這個(gè)節(jié)點(diǎn)
 inOrder(localRoot.right) ;//調(diào)用自身來(lái)遍歷右子樹(shù)
 }
 }

查找某個(gè)節(jié)點(diǎn)：

//查找某個(gè)節(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 ;
 }

查找樹(shù)中關(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 ;
 }
 }

刪除某個(gè)節(jié)點(diǎn)：

思考：

1).先找到要?jiǎng)h除的節(jié)點(diǎn)：

public boolean delete(int key)
 {
 //先找到需要?jiǎng)h除的節(jié)點(diǎn)
 Node current = root ;
 Node parent = root ;
 boolean isLeftChild = false ;
 while(current.iData != key)//顯然，當(dāng)current.iData == key 時(shí)，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時(shí)返回false
 return false ;
 }
 //continue ........
 }

2).再考慮要?jiǎng)h除的節(jié)點(diǎn)是怎樣的節(jié)點(diǎn)，經(jīng)分析，有三種情況：葉節(jié)點(diǎn)、有一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)、有兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)

A).如果刪除的是一個(gè)葉子節(jié)點(diǎn)，直接刪除即可

//接上................
 //分情況考慮刪除的節(jié)點(diǎn)
 //刪除的節(jié)點(diǎn)為葉節(jié)點(diǎn)時(shí)
 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)有一個(gè)節(jié)點(diǎn)時(shí)：分兩種情況，刪除的節(jié)點(diǎn)只有一個(gè)左子節(jié)點(diǎn)，或者只有一個(gè)右子節(jié)點(diǎn)

//接上.......
//刪除的節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
 else
 if(current.right == null)//刪除的節(jié)點(diǎn)只有一個(gè)左子節(jié)點(diǎn)時(shí)
 {
 if(current == root)//要?jiǎng)h除的節(jié)點(diǎn)為根節(jié)點(diǎn)
 root = current.left ;
 else
 if(isLeftChild)//要?jiǎng)h除的節(jié)點(diǎn)是一個(gè)左子節(jié)點(diǎn)
 parent.left = current.left ;
 else
 parent.right = current.left ;//要?jiǎng)h除的節(jié)點(diǎn)是一個(gè)右子節(jié)點(diǎn)
 }
 else
 if(current.left == null)//刪除的節(jié)點(diǎn)只有一個(gè)右子節(jié)點(diǎn)時(shí)
 {
 if(current == root)//要?jiǎng)h除的節(jié)點(diǎn)為根節(jié)點(diǎn)
 root = current.right ;
 else
 if(isLeftChild)//要?jiǎng)h除的節(jié)點(diǎn)是一個(gè)左子節(jié)點(diǎn)
 parent.left = current.right ;
 else
 parent.right = current.right ;//要?jiǎng)h除的節(jié)點(diǎn)是一個(gè)右子節(jié)點(diǎn)
 }
//continue.......

c).如果刪除的節(jié)點(diǎn)有兩個(gè)節(jié)點(diǎn)時(shí)：

這種情況就比較復(fù)雜，需要去尋找一個(gè)節(jié)點(diǎn)去替代要?jiǎng)h除的節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)應(yīng)該是什么節(jié)點(diǎn)呢？

據(jù)書(shū)本介紹，最合適的節(jié)點(diǎn)是后繼節(jié)點(diǎn)，即比要?jiǎng)h除的節(jié)點(diǎn)的關(guān)鍵值次高的節(jié)點(diǎn)是它的后繼節(jié)點(diǎn)。

說(shuō)得簡(jiǎn)單一些，后繼節(jié)點(diǎn)就是比要?jiǎng)h除的節(jié)點(diǎn)的關(guān)鍵值要大的節(jié)點(diǎn)集合中的最小值。

以上面的為例，40的后繼節(jié)點(diǎn)為74,10的后繼節(jié)點(diǎn)是13,19的后繼節(jié)點(diǎn)時(shí)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 ;//移動(dòng)到位置節(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ǎng)h除節(jié)點(diǎn)的右子節(jié)點(diǎn)（此時(shí)可以知道，這個(gè)右子節(jié)點(diǎn)沒(méi)有左子點(diǎn)，如果有，就不該這個(gè)右子節(jié)點(diǎn)為后繼節(jié)點(diǎn)）

//要?jiǎng)h除的節(jié)點(diǎn)為左子節(jié)點(diǎn)時(shí)
parent.left = successor ;
successor.left = current.left ;
//要?jiǎng)h除的節(jié)點(diǎn)是右子節(jié)點(diǎn)時(shí)
parent.right = successor ;
successor.left = current.left ;

b)如果后繼節(jié)點(diǎn)為要?jiǎng)h除節(jié)點(diǎn)的右子節(jié)點(diǎn)的左后代：

//假如要?jiǎng)h除的節(jié)點(diǎn)為右子節(jié)點(diǎn)
successorParent.left = successor.right ;//第一步
successor.right = current.right ;//第二步
parent.right = successor ;
successor.left = current.left ;
//假設(shè)要?jiǎng)h除的節(jié)點(diǎn)為左子節(jié)點(diǎn)
successorParent.left = successor.right ;
successor.right = current.right ;
parent.left = successor ;
successor.left = current.left ;

注意：第一步和第二步在getSuccessor()方法的最后的if語(yǔ)句中完成

以下是刪除的節(jié)點(diǎn)有連個(gè)節(jié)點(diǎn)的代碼：

//接上 
 //刪除的節(jié)點(diǎn)有兩個(gè)子節(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()方法的代碼：

//刪除某個(gè)節(jié)點(diǎn)
 public boolean delete(int key)
 {
 //先找到需要?jiǎng)h除的節(jié)點(diǎn)
 Node current = root ;
 Node parent = root ;
 boolean isLeftChild = false ;
 while(current.iData != key)//顯然，當(dāng)current.iData == key 時(shí)，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時(shí)返回false
 return false ;
 }
 //分情況考慮刪除的節(jié)點(diǎn)
 //刪除的節(jié)點(diǎn)為葉節(jié)點(diǎn)時(shí)
 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)有一個(gè)子節(jié)點(diǎn)
 else
 if(current.right == null)//刪除的節(jié)點(diǎn)只有一個(gè)左子節(jié)點(diǎn)時(shí)
 {
 if(current == root)//要?jiǎng)h除的節(jié)點(diǎn)為根節(jié)點(diǎn)
 root = current.left ;
 else
 if(isLeftChild)//要?jiǎng)h除的節(jié)點(diǎn)是一個(gè)左子節(jié)點(diǎn)
 parent.left = current.left ;
 else
 parent.right = current.left ;//要?jiǎng)h除的節(jié)點(diǎn)是一個(gè)右子節(jié)點(diǎn)
 }
 else
 if(current.left == null)//刪除的節(jié)點(diǎn)只有一個(gè)右子節(jié)點(diǎn)時(shí)
 {
 if(current == root)//要?jiǎng)h除的節(jié)點(diǎn)為根節(jié)點(diǎn)
 root = current.right ;
 else
 if(isLeftChild)//要?jiǎng)h除的節(jié)點(diǎn)是一個(gè)左子節(jié)點(diǎn)
 parent.left = current.right ;
 else
 parent.right = current.right ;//要?jiǎng)h除的節(jié)點(diǎn)是一個(gè)右子節(jié)點(diǎn)
 }
 //刪除的節(jié)點(diǎn)有兩個(gè)子節(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ù)雜，那刪除是必要的嗎?我們可以給每個(gè)節(jié)點(diǎn)定義一個(gè)標(biāo)志，該標(biāo)志用于記錄該節(jié)點(diǎn)是否已經(jīng)刪除了，顯示樹(shù)時(shí)，先判斷該節(jié)點(diǎn)是否已經(jīng)刪除，如果沒(méi)有，則顯示。

這樣的結(jié)果是，節(jié)點(diǎn)其實(shí)是沒(méi)有刪除的，這樣顯然逃避責(zé)任了。當(dāng)樹(shù)中沒(méi)有那么多的刪除操作時(shí)，這也不失為一種好方法，例如：

已經(jīng)離職的員工的檔案要永久地保存在員工的記錄中。

以上所述是小編給大家介紹的Java數(shù)據(jù)結(jié)構(gòu)與算法之樹(shù)(動(dòng)力節(jié)點(diǎn)java學(xué)院整理)，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

您可能感興趣的文章: