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程序設計有所幫助。
相關文章
今天在寫代碼的時候需要用到一個生成指定范圍隨機數(shù)的函數(shù)，百度了一下，發(fā)現(xiàn)了很多種方法，這里簡單為大家整理一下，方便需要的朋友2017-08-08
這篇文章主要介紹了Java的string類為什么是不可變的，總結了三個答案,需要的朋友可以參考下2014-04-04
這篇文章主要介紹了Java?多線程并發(fā)LockSupport,LockSupport?類是用于創(chuàng)建鎖和其他同步類的基本線程阻塞原語,更多相關內容需要得小伙伴可以參考一下下面文章內容2022-06-06
最小生成樹（Minimum Spanning Tree）：在連通圖的所有生成樹中，所有邊的權值和最小的生成樹，稱為最小生成樹。這篇文章主要介紹了求最小生成樹的兩種方法：Prim算法和Kruskal算法，需要的可以參考一下2022-01-01
這篇文章主要給大家介紹了關于Java如何優(yōu)雅的實現(xiàn)微信登錄注冊的相關資料,文中通過實例代碼介紹的非常詳細,對大家學習或者使用java具有一定的參考學習價值,需要的朋友可以參考下2022-02-02
這篇文章主要介紹了如何基于回調實現(xiàn)Java的異步調用,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-06-06
Spring MVC是Spring Framework的一部分，是基于Java實現(xiàn)MVC的輕量級Web框架。本文將通過一些簡單示例帶大家掌握SpringMVC的配置與使用，感興趣的可以了解一下2022-11-11
這篇文章主要介紹了JAVA語言編程格式高級規(guī)范,需要的朋友可以參考下2015-05-05
解決springboot錯誤:找不到或無法加載主類(配置編碼或者Maven)
這篇文章主要介紹了解決springboot錯誤:找不到或無法加載主類(配置編碼或者Maven)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
這篇文章主要介紹了hadoop上傳文件功能實例代碼,需要的朋友可以參考下2017-09-09