快捷導(dǎo)航

java使用歸并刪除法刪除二叉樹中節(jié)點的方法

更新時間：2015年05月30日 15:57:34 作者：hitxueliang

這篇文章主要介紹了java使用歸并刪除法刪除二叉樹中節(jié)點的方法,實例分析了java二叉樹算法的相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了java使用歸并刪除法刪除二叉樹中節(jié)點的方法。分享給大家供大家參考。具體分析如下：

實現(xiàn)的思想很簡單：

first：找到要刪除的節(jié)點
second：如果刪除的節(jié)點沒有右子樹那么左子樹鏈到父節(jié)點
third：如果刪除的節(jié)點沒有左子樹那么右子樹鏈到父節(jié)點
forth：如果刪除的節(jié)點又左右孩子，那么可以歸并刪除節(jié)點后的子樹：方法有兩種一種是用刪除節(jié)點的左子樹的最右節(jié)點，指向刪除節(jié)點的右子樹，另一種是用刪除節(jié)點的用字?jǐn)?shù)的最左節(jié)點指向刪除節(jié)點的左子樹。

Java 實現(xiàn)如下：

public void deleteByMerging(int el)
{
IntBSTNode tmp,node,p=root,prev=null;
/*find the node to be deleted*/
while(p!=null&&p.key!=el)
{
prev=p;
if(p.key<el)
p=p.right;
else p=p.left;
}
/*find end*/
node=p;
if(p!=null&&p.key==el)
{
if(node.right==null)
//node has no right child then its left child (if any) is attached to 
node=node.left;
//its parent
  else if(node.left==null)
  //node has no left child then its right child (if any) is attched to
  node=node.right
  //its parent
else{
tmp=node.left;  
while(tmp.right!=null)
tmp=tmp.right;
//find the rightmost node of the left subtree
tem.right=node.right;
//establish the link between the rightmost node of the left subtree and the right subtree
node=node.left;
}
if(p==root)
{
root=node;
}
else if (prev.left==p)
{
prev.left=node;
}
else prev.right=node
}
else if(root!=null)
  {
System.out.println("the node is not in the tree");
}
else System.out.println("The tree is empty");
}

希望本文所述對大家的java程序設(shè)計有所幫助。

您可能感興趣的文章:

相關(guān)文章

前置++和后置++ 運算的詳解及實例代碼
這篇文章主要介紹了前置++和后置++ 的相關(guān)資料,并附示例代碼，幫助大家學(xué)習(xí)參考，需要的朋友可以參考下
2016-09-09
Java中動態(tài)規(guī)則的實現(xiàn)方式示例詳解
這篇文章主要介紹了Java中動態(tài)規(guī)則的實現(xiàn)方式,本文通過實例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2020-08-08
SpringMVC的處理器攔截器HandlerInterceptor詳解
這篇文章主要介紹了SpringMVC的處理器攔截器HandlerInterceptor詳解,SpringWebMVC的處理器攔截器,類似于Servlet開發(fā)中的過濾器Filter,用于處理器進(jìn)行預(yù)處理和后處理,需要的朋友可以參考下
2024-01-01
部署springboot打包不打包配置文件,配置文件為外部配置文件使用詳解
在Spring Boot項目中,將配置文件排除在jar包之外,通過外部配置文件來管理不同環(huán)境的配置,可以實現(xiàn)靈活的配置管理,在pom.xml文件中添加相關(guān)配置,打包時忽略指定文件,運行時在jar包同級目錄下創(chuàng)建config文件夾,將配置文件放入其中即可
2025-02-02
Java中Json解析的方法分析
這篇文章主要介紹了Java中Json解析的方法,結(jié)合實例形式分析了java針對json格式數(shù)據(jù)的解析實現(xiàn)步驟與相關(guān)操作技巧,需要的朋友可以參考下
2017-05-05
JAVA中阻止類的繼承(官方和非官方)
在面向?qū)ο蟮睦碚撝? 有一些方案要求你用一個辦法來聲明一個不可繼承的類。一般而言，如果類提供的功能不應(yīng)該被改變，或者更恰當(dāng)?shù)恼f，是被覆蓋（override）的時候才會出現(xiàn)這種情況。在這篇文章里，我討論在JAVA語言中的實現(xiàn)辦法--官方和非官方的辦法
2014-01-01
java 獲取數(shù)據(jù)庫連接的實現(xiàn)代碼
本篇文章是對在java中獲取數(shù)據(jù)庫連接的實現(xiàn)代碼進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
2013-05-05
SpringBoot之核心依賴和自動配置方式
這篇文章主要介紹了SpringBoot之核心依賴和自動配置方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-06-06
Java中Optional.of()方法及源碼解析(非常詳細(xì)!)
這篇文章主要給大家介紹了關(guān)于Java中Optional.of()方法及源碼解析的相關(guān)資料,Java中java.util .Optional類的of()方法用于獲得該Optional類中具有指定類型的指定值的一個實例,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
2024-06-06
淺談java繼承中是否創(chuàng)建父類對象
下面小編就為大家?guī)硪黄獪\談java繼承中是否創(chuàng)建父類對象。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2017-06-06