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