java使用归并删除法删除二叉树中节点的方法

本文实例讲述了java使用归并删除法删除二叉树中节点的方法。分享给大家供大家参考。具体分析如下：

实现的思想很简单：

first：找到要删除的节点
second：如果删除的节点没有右子树那么左子树链到父节点
third：如果删除的节点没有左子树那么右子树链到父节点
forth：如果删除的节点又左右孩子，那么可以归并删除节点后的子树：方法有两种一种是用删除节点的左子树的最右节点，指向删除节点的右子树，另一种是用删除节点的用字数的最左节点指向删除节点的左子树。

Java 实现如下：

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程序设计有所帮助。

赞 (0)

相关推荐

  • java 数据结构二叉树的实现代码

    1. 二叉树接口 public interface BinaryTreeInterface<T> { public T getRootData(); public int getHeight(); public int getNumberOfRoot(); public void clear(); public void setTree(T rootData); // 用rootData设置树 public void setTree(T rootData,BinaryTreeInterface

  • java 完全二叉树的构建与四种遍历方法示例

    java 完全二叉树的构建与四种遍历方法示例

    本来就是基础知识,不能丢的太干净,今天竟然花了那么长的时间才写出来,记一下. 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素检查是其是

  • JAVA 实现二叉树（链式存储结构）

    JAVA 实现二叉树（链式存储结构）

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • Java的二叉树排序以及遍历文件展示文本格式的文件树

    Java二叉树排序算法 排序二叉树的描述也是一个递归的描述, 所以排序二叉树的构造自然也用递归的: 排序二叉树的3个特征: 1:当前node的所有左孩子的值都小于当前node的值: 2:当前node的所有右孩子的值都大于当前node的值: 3:孩子节点也满足以上两点 package test.sort; public class BinaryNode { private int value;//current value private BinaryNode lChild;//left chil

  • 图解二叉树的三种遍历方式及java实现代码

    图解二叉树的三种遍历方式及java实现代码

    二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子. 1.二叉树节点 作为图的特殊形式,二叉树的基本组成单元是节点与边:作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用. 如下,给出了二叉树节点的数据结构图示和相关代码: // 定义节点类: private static class BinNode { private Object element; private BinNode lChild;// 定义指向

  • Java完全二叉树的创建与四种遍历方法分析

    Java完全二叉树的创建与四种遍历方法分析

    本文实例讲述了Java完全二叉树的创建与四种遍历方法.分享给大家供大家参考,具体如下: 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素

  • java实现二叉树的创建及5种遍历方法(总结)

    用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式: package myTest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class myClass { public static void main(

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

  • 详解java实现遍历二叉树的三种情况

    遍历二叉树,从上往下遍历.但是同层节点可以从左向右遍历,也可以从右向左遍历(也就是之字型遍历),其中,都需要队列进行实现.只是按照之字型稍微麻烦一些. (1)从上往下打印出二叉树的每个节点,同层节点从左至右打印. 需要一个队列,队列里面放节点(从根节点开始),然后依次进行打印. import java.util.ArrayList; import java.util.Queue; import java.util.LinkedList; class TreeNode{ int val = 0;

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • Java实现求二叉树的深度和宽度

    这个是常见的对二叉树的操作.总结一下: 设节点的数据结构,如下: 复制代码 代码如下: class TreeNode {     char val;     TreeNode left = null;     TreeNode right = null; TreeNode(char _val) {         this.val = _val;     } } 1.二叉树深度 这个可以使用递归,分别求出左子树的深度.右子树的深度,两个深度的较大值+1即可. 复制代码 代码如下: // 获取最大

随机推荐