精华内容
下载资源
问答
  • 下篇:平衡二叉树二叉查找树二叉查找树(Binary Search Tree),或者是一颗空树,或者是具有下列性质的二叉树:1、若它的左子树不空,则其左子树上的所有结点的值均小于它根结点的值;2、若它的右子树不空,则其右子树...

    下篇:平衡二叉树

    二叉查找树

    二叉查找树(Binary Search Tree),或者是一颗空树,或者是具有下列性质的二叉树:

    1、若它的左子树不空,则其左子树上的所有结点的值均小于它根结点的值;

    2、若它的右子树不空,则其右子树上的所有结点的值均大于它根结点的值;

    3、它的左、右子树也分别为二叉查找树。

    2cfa203590e0ebac7e74649a0b386e9b.png

    二叉查找树是基于二叉树的,其结点数据结构定义为如下: /**结点数据结构*/ static class BinaryNode { T data; BinaryNode left; BinaryNode right; public BinaryNode(T data) { this(data,null,null); } public BinaryNode( T data, BinaryNode left, BinaryNode right) { this.data =data; this.left = left; this.right =right; } public BinaryNode() { data =null; this.left = left; this.right =right; } }

    现在明白了什么是二叉查找树,那么二叉查找书的基本操作又是如何来实现的呢?

    查找操作

    在二叉查找树中查找x的过程如下:

    1、若二叉树是空树,则查找失败。

    2、若x等于根结点的数据,则查找成功,否则。

    3、若x小于根结点的数据,则递归查找其左子树,否则。

    4、递归查找其右子树。

    根据上述的步骤,写出其查找操作的代码:

    /**查找指定的元素,默认从 * 根结点出开始查询*/ public boolean contains(T t) { return contains(t, rootTree); } /**从某个结点出开始查找元素*/ public boolean contains(T t, BinaryNode node) { if(node==null) return false;//结点为空,查找失败 int result = t.compareTo(node.data); if(result>0) return contains(t,node.right);//递归查询右子树 else if(result<0) return contains(t, node.left);//递归查询左子树 else return true; } /** 这里我提供一个对二叉树最大值 最小值的搜索*/ /**找到二叉查找树中的最小值*/ public T findMin() { if(isEmpty()) { System.out.println("二叉树为空"); return null; }else return findMin(rootTree).data; } /**找到二叉查找树中的最大值*/ public T findMax() { if(isEmpty()) { System.out.println("二叉树为空"); return null; }else return findMax(rootTree).data; } /**查询出最小元素所在的结点*/ public BinaryNode findMin(BinaryNode node) { if(node==null) return null; else if(node.left==null) return node; return findMin(node.left);//递归查找 } /**查询出最大元素所在的结点*/ public BinaryNode findMax(BinaryNode node) { if(node!=null) { while(node.right!=null) node=node.right; } return node; }

    插入操作

    二叉树查找树b插入操作x的过程如下:

    1、若b是空树,则直接将插入的结点作为根结点插入。

    2、x等于b的根结点的数据的值,则直接返回,否则。

    3、若x小于b的根结点的数据的值,则将x要插入的结点的位置改变为b的左子树,否则。

    4、将x要出入的结点的位置改变为b的右子树。

    代码实现如下:

    /**插入元素*/ public void insert(T t) { rootTree = insert(t, rootTree); } /**在某个位置开始判断插入元素*/ public BinaryNode insert(T t,BinaryNode node) { if(node==null) { //新构造一个二叉查找树 return new BinaryNode(t, null, null); } int result = t.compareTo(node.data); if(result<0) node.left= insert(t,node.left); else if(result>0) node.right= insert(t,node.right); else ;//doNothing return node; }

    删除操作

    对于二叉查找树的删除操作(这里根据值删除,而非结点)分三种情况:

    不过在此之前,我们应该确保根据给定的值找到了要删除的结点,如若没找到该结点

    不会执行删除操作!

    下面三种情况假设已经找到了要删除的结点。

    1、如果结点为叶子结点(没有左、右子树),此时删除该结点不会玻化树的结构

    直接删除即可,并修改其父结点指向它的引用为null.如下图:

    8e877ddefa15dbf4e179ee10f1e01591.png

    2、如果其结点只包含左子树,或者右子树的话,此时直接删除该结点,并将其左子树

    或者右子树设置为其父结点的左子树或者右子树即可,此操作不会破坏树结构。

    110ce76e7fd222ea059ca38b39c7d7f0.png

    3、 当结点的左右子树都不空的时候,一般的删除策略是用其右子树的最小数据

    (容易找到)代替要删除的结点数据并递归删除该结点(此时为null),因为

    右子树的最小结点不可能有左孩子,所以第二次删除较为容易。

    z的左子树和右子树均不空。找到z的后继y,因为y一定没有左子树,所以可以删除y,

    并让y的父亲节点成为y的右子树的父亲节点,并用y的值代替z的值.如图:

    041f3c92d28381c50b499804937b2c45.png

    删除操作源码:

    /**删除元素*/ public void remove(T t) { rootTree = remove(t,rootTree); } /**在某个位置开始判断删除某个结点*/    public BinaryNode remove(T t,BinaryNode node)    {        if(node == null)            return node;//没有找到,doNothing        int result = t.compareTo(node.data);        if(result>0)            node.right = remove(t,node.right);        else if(result<0)            node.left = remove(t,node.left);        else if(node.left!=null&&node.right!=null)        {            node.data = findMin(node.right).data;            node.right = remove(node.data,node.right);        }        else            node = (node.left!=null)?node.left:node.right;        return node;                }

    完整源码 package com.kiritor; /** * Java实现二叉查找树 * @author Kiritor * @param */ public class BinarySearchTree> { /**结点数据结构*/ static class BinaryNode { T data; BinaryNode left; BinaryNode right; public BinaryNode(T data) { this(data,null,null); } public BinaryNode( T data, BinaryNode left, BinaryNode right) { this.data =data; this.left = left; this.right =right; } public BinaryNode() { data =null; this.left = left; this.right =right; } } private BinaryNode rootTree; /**构造一颗空的二叉查找树*/ public BinarySearchTree() { rootTree = null; } /**清空二叉查找树*/ public void clear() { rootTree = null; } /**判断是否为空*/ public boolean isEmpty() { return rootTree == null; } /**查找指定的元素,默认从 * 根结点出开始查询*/ public boolean contains(T t) { return contains(t, rootTree); } /**找到二叉查找树中的最小值*/ public T findMin() { if(isEmpty()) { System.out.println("二叉树为空"); return null; }else return findMin(rootTree).data; } /**找到二叉查找树中的最大值*/ public T findMax() { if(isEmpty()) { System.out.println("二叉树为空"); return null; }else return findMax(rootTree).data; } /**插入元素*/ public void insert(T t) { rootTree = insert(t, rootTree); } /**删除元素*/ public void remove(T t) { rootTree = remove(t,rootTree); } /**打印二叉查找树*/ public void printTree() { } /**从某个结点出开始查找元素*/ public boolean contains(T t, BinaryNode node) { if(node==null) return false; int result = t.compareTo(node.data); if(result>0) return contains(t,node.right); else if(result<0) return contains(t, node.left); else return true; } /**查询出最小元素所在的结点*/ public BinaryNode findMin(BinaryNode node) { if(node==null) return null; else if(node.left==null) return node; return findMin(node.left);//递归查找 } /**查询出最大元素所在的结点*/ public BinaryNode findMax(BinaryNode node) { if(node!=null) { while(node.right!=null) node=node.right; } return node; } /**在某个位置开始判断插入元素*/ public BinaryNode insert(T t,BinaryNode node) { if(node==null) { //新构造一个二叉查找树 return new BinaryNode(t, null, null); } int result = t.compareTo(node.data); if(result<0) node.left= insert(t,node.left); else if(result>0) node.right= insert(t,node.right); else ;//doNothing return node; } /**在某个位置开始判断删除某个结点*/ public BinaryNode remove(T t,BinaryNode node) { if(node == null) return node;//没有找到,doNothing int result = t.compareTo(node.data); if(result>0) node.right = remove(t,node.right); else if(result<0) node.left = remove(t,node.left); else if(node.left!=null&&node.right!=null) { node.data = findMin(node.right).data; node.right = remove(node.data,node.right); } else node = (node.left!=null)?node.left:node.right; return node; } public BinaryNode init() { BinaryNode node3 = new BinaryNode(3); BinaryNode node1 = new BinaryNode(1); BinaryNode node4 = new BinaryNode(4,node3,null); BinaryNode node2 = new BinaryNode(2,node1,node4); BinaryNode node8 = new BinaryNode(8); BinaryNode root = new BinaryNode(6,node2,node8); return root; } public void preOrder(BinaryNode node) { if (node != null) { System.out.print(node.data); preOrder(node.left); preOrder(node.right); } } /*简单测试*/  public static void main(String[] args) { BinarySearchTree searchTree = new BinarySearchTree<>(); BinaryNode node= searchTree.init(); searchTree.rootTree=node; searchTree.preOrder(searchTree.rootTree); searchTree.remove(4); searchTree.preOrder(searchTree.rootTree); } }

    展开全文
  • Java-二叉树删除节点

    2020-10-21 22:20:22
    思路分析 首先先处理: 考虑如果树是空树root,如果只有一个root节点,则等价二叉树置空 然后进行下列操作: 1.因为我们的二叉树是单向的,所以我们...4.如果第二步和第三步没有删除节点,那我们就向左子树进行递归 5

    思路分析

    首先先处理:
    考虑如果树是空树root,如果只有一个root节点,则等价二叉树置空
    然后进行下列操作:
    1.因为我们的二叉树是单向的,所以我们判断当前节点的子节点是不是需要删除的节点,而不能判断当前节点是不是需要删除的节点
    2.如果当前节点的左子节点不为空,并且左子节点就是要删除的节点,就将this.left=null,并返回
    3.如果当前节点的右子节点不为空,并且右子节点就是要删除的节点,就将this.right=null,并返回
    4.如果第二步和第三步没有删除节点,那我们就向左子树进行递归
    5.如果第四步也没有删除节点,则应当向右子树进行递归

    代码实现

    //递归删除节点
    	public void delNode(int no) {
    		if(this.left!=null&&this.left.no==no) {
    			this.left=null;
    			return;
    		}
    		if(this.right!=null&&this.right.no==no) {
    			this.right=null;
    			return;
    		}
    		if(this.left!=null) {
    			this.left.delNode(no);
    			return;
    		}
    		if(this.right!=null) {
    			this.right.delNode(no);
    			return;
    		}
    	}
    
    //删除节点
    	public void delNode(int no) {
    		if(root!=null) {
    			//如果只有一个root节点,要立即判断root是否为要删除的节点
    			if(root.getNo()==no) {
    				root=null;
    			}else {
    				root.delNode(no);
    			}
    		}else {
    			System.out.println("空树, 不能删除");
    		}
    		
    	}
    
    展开全文
  • 本人用JAVA写的二叉排序树,有二叉树插入节点、删除节点、修改节点等操作,其中还写了一个字符串比较(字母模式比较,数值模式比较)另外不附有源码
  • 创建Node节点 public class Node { int value; Node left; Node right; public Node(int value) { ... * @param value 希望删除节点 * @return 如果找到返回该节点,否则返回null */ public Node search

    创建Node节点

    public class Node {
        int value;
        Node left;
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        //查找要删除的节点
    
        /**
         * @param value 希望删除的节点
         * @return 如果找到返回该节点,否则返回null
         */
        public Node search(int value) {
            if (value == this.value) {//找到就是该节点
                return this;
            } else if (value < this.value) {//如果查找的值小于当前节点,向左子树递归查找
                //如果左子节点为空
                if (this.left == null) {
                    return null;
                }
                return this.left.search(value);
    
            } else {//如果查找的值不小于当前节点,向右子树递归查找
                if (this.right == null) {
                    return null;
                }
                return this.right.search(value);
            }
        }
    
        //查找要删除节点的父节点
    
        /**
         * @param value 要找到的节点值
         * @return 返回的是要删除节点的父节点,如果没有就返回null
         */
        public Node searchParent(int value) {
            //如果当前节点就是要删除的节点的父节点,就返回
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else {
                //如果查找的值小于当前节点的值,并且当前节点的左子节点不为空
                if (value < this.value && this.left != null) {
                    return this.left.searchParent(value);//向左子树递归查找
                } else if (value >= this.value && this.right != null) {
                    return this.right.searchParent(value);
                } else {
                    return null;//没有找到父节点
                }
            }
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        //添加节点方法
        //递归的形式添加节点,注意需要满足二叉树排序树的要求
        public void add(Node node) {
            if (node == null) {
                return;
            }
            //判断传入的节点的值,和当前子树的根节点的关系
            if (node.value < this.value) {
                //如果当前及诶单左子节点为null
                if (this.left == null) {
                    this.left = node;
                } else {
                    //递归的向左子树添加
                    this.left.add(node);
                }
            } else {//添加的节点的值大于当前节点的值
                if (this.right == null) {
                    this.right = node;
                } else {
                    //递归的向右子树添加
                    this.right.add(node);
                }
            }
        }
    
        //中序遍历
        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }
        }
    }
    

    创建二叉排序树

    public class BinarySortTree {
        private Node root;
    
        //查找要删除的节点
        public Node search(int value) {
            if (root == null) {
                return null;
            } else {
                return root.search(value);
            }
        }
    
        //查找父节点
        public Node searchParent(int value) {
            if (root == null) {
                return null;
            } else {
                return root.searchParent(value);
            }
        }
    
        //编写方法
        //1、返回以 node 为根节点的二叉排序树的最小节点的值
        //2、删除node 为根节点的二叉树排序树的最小节点
    
        /**
         * @param node 传入的节点(当做二叉排序树的根节点)
         * @return 返回以node 为根节点的二叉树排序树的最小节点的值
         */
        public int delRightTreeMin(Node node) {
            Node target = node;
            //循环的查找左节点,就会找到最小值
            while (target.left != null) {
                target = target.left;
            }
            //这时,target 指向了最小节点
            //删除最小节点
            delNode(target.value);
            return target.value;
        }
    
        //删除节点
        public void delNode(int value) {
            if (root == null) {
                return;
            } else {
                //1、需求先去找到要删除的节点,targetNode
                Node targetNode = search(value);
                //如果没有找到要删除的节点
                if (targetNode == null) {
                    return;
                }
                //如果我们发现当前这颗二叉树排序树只有一个节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                }
                //找到targetNode的父节点
                Node parent = searchParent(value);
                //如果要删除的节点是叶子节点
                if (targetNode.left == null && targetNode.right == null) {
                    //判断targetNode 是父节点的左子节点,还是右子节点
                    if (parent.left != null && parent.left.value == value) {//左子节点
                        parent.left = null;
                    } else if (parent.right != null && parent.right.value == value) {//右子节点
                        parent.right = null;
                    }
                } else if (targetNode.left != null && targetNode.right != null) {//
                    int minVal = delRightTreeMin(targetNode.right);
                    targetNode.value = minVal;
                } else {//删除只有一颗子树的节点
                    //如果要删除的节点有左子节点
                    if (targetNode.left != null) {
                        if (parent != null) {
                            //如果targetNode 是 parent的左子节点
                            if (parent.left.value == value) {
                                parent.left = targetNode.left;
                            } else {//是 targetNode 是parent的右子节点
                                parent.right = targetNode.left;
                            }
                        } else {
                            root = targetNode.left;
                        }
                    } else {//如果要删除的节点有右子节点
                        if (parent != null) {
                            if (parent.left.value == value) {
                                parent.left = targetNode.right;
                            } else {
                                //如果targetNode 是 parent的右子节点
                                parent.right = targetNode.right;
                            }
                        } else {
                            root = targetNode.right;
                        }
                    }
                }
            }
    
        }
    
        //添加节点的方法
        public void add(Node node) {
            if (root == null) {
                root = node;//如果root为空则直接让root指向node
            } else {
                root.add(node);
            }
        }
    
        //中序遍历
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("二叉树不能为空");
            }
        }
    }
    

    main方法测试:

     public static void main(String[] args) {
            int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
            BinarySortTree binarySortTree = new BinarySortTree();
            //循环的添加节点到二叉排序树
            for (int i = 0; i < arr.length; i++) {
                binarySortTree.add(new Node(arr[i]));
            }
            //中序遍历二叉排序树
            binarySortTree.infixOrder();
            //删除叶子节点
            binarySortTree.delNode(10);
            System.out.println("删除节点后");
            binarySortTree.infixOrder();
        }
    
    展开全文
  • 首先定义结点类 class Node :public class Node {public Node leftchild=null;public Node rightchild=null;...}然后再定义二叉树类 class Btreepublic class Btree{// 删除值为val的节点public void delete(In...

    首先定义结点类 class Node :

    public class Node {

    public Node leftchild=null;

    public Node rightchild=null;

    public Node parent=null;

    }

    然后再定义二叉树类 class Btree

    public class Btree{

    // 删除值为val的节点

    public void delete(Integer val) {

    //先找到值为val的结点,调用函数Search(val)

    Node p = this.Search(val);

    //找到节点后进行删除

    //如果右孩子不为空,那么找到右孩子树中最小的值的结点,与节点的值进行交换,然后后继结点结点的父亲的孩子指向他的右孩子。在此用到了中序后继函数successor

    //(val),下面有定义。

    if (p.rightchild != null) {

    Node succ = this.successor(val);

    Integer i = p.value;

    p.value = succ.value;

    succ.value = i;

    //既然找到后继结点即最小值的结点,那么他就没有左孩子。

    if (succ == succ.parent.leftchild)

    succ.parent.leftchild = succ.rightchild;

    if (succ == succ.parent.rightchild)

    succ.parent.rightchild = succ.rightchild;

    }

    //如果右孩子为空,找其父亲,

    //如果是父亲的左孩子,那么直接让父亲的左孩子指向此节点的左孩子即直接将此节点删除

    //如果是父亲的右孩子,那么直接让父亲的右孩子指向此节点的左孩子即直接将节点删除

    //最后孩子的父亲指向此节点的父亲,实现双向指向

    else {

    if ( p.parent.leftchild==p)

    p.parent.leftchild = p.leftchild;

    if ( p.parent.rightchild==p)

    p.parent.rightchild = p.leftchild;

    p.leftchild.parent = p.parent;

    }

    }

    // 找到此节点,用到递归

    public Node Search(Integer val) {

    return this.search(this.root, val);

    }

    public Node search(Node p, Integer val) {

    if (p == null)

    return null;

    else {

    if (p.value == val) {

    return p;

    }

    else {

    if (p.value < val) {

    return search(p.rightchild, val);

    } else {

    return search(p.leftchild, val);

    }

    }

    }

    }

    // 找到此节点的中序后继,中序后继:就是比此节点大的最小值,在此处用到了min(p.rightchild),下面有定义。顺便说一句:前驱:比此节点小的最大值,其操作和min函数

    //类似

    public Node successor(Integer val) {

    Node p = this.Search(val);

    if (p.rightchild != null) {

    return this.min(p.rightchild);

    }

    else {

    while (p.parent != null) {

    if (p == p.parent.leftchild)

    break;

    p = p.parent;

    }

    return p.parent;

    }

    }

    // 找到后继树中最小的节点

    public Node min(Node r) {

    if (r == null)

    return null;

    else {

    while (r.leftchild != null) {

    r = r.leftchild;

    }

    return r;

    }

    }

    }

    最后是主函数类 class Main

    public class Main {

    public static void main(String[] args) {

    Btree b =new Btree();

    Integer[] data={3,2,5,4,8,7,9};

    for(Integer i=0;i

    b.insert(data[i]);//insert(val)函数详见链接点击打开链接

    }

    b.preTravel();//二叉树的三种遍历,详见链接点击打开链接

    b.inTravel();

    b.postTravel();

    b.delete(8);

    b.preTravel();

    b.inTravel();

    b.postTravel();

    }

    }

    展开全文
  • 二叉树删除节点时,分为两种情况,删除节点为叶子节点与非叶子节点。 首先判断根节点是否要删除的节点。如果是,则将该二叉树变为空树;否则判断左子节点与右子节点是否要删除的节点。 如果是,删除以该节点为根...
  • 一、二叉树删除节点的思路图解 二、二叉树删除节点的示例代码 1、代码 package com.rf.springboot01.dataStructure.tree; /** * @description: 二叉树删除节点示例 * @author: xiaozhi * @create: 2020-08-28 ...
  • 本文实例讲述了java使用归并删除删除二叉树节点的方法。分享给大家供大家参考。具体分析如下:实现的思想很简单:first:找到要删除节点second:如果删除节点没有右子树那么左子树链到父节点third:如果删除...
  • 2、该节点有一个子节点改变父节点的引用,将其直接指向要删除节点的子节点。3、该节点有两个子节点要删除有两个子节点的节点,就需要使用它的中序后继来替代该节点。代码package com.example.deer;public c...
  • 主要介绍了java使用归并删除删除二叉树中节点的方法,实例分析了java二叉树算法的相关操作技巧,需要的朋友可以参考下
  • 只有左子树或右子树,只要将需要删除的节点的父节点指针指向待删除节点的子树。 如果待删除节点有左右子树,我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为...
  • 2、该节点有一个子节点改变父节点的引用,将其直接指向要删除节点的子节点。 3、该节点有两个子节点要删除有两个子节点的节点,就需要使用它的中序后继来替代该节点。 代码package com.example.deer;publi...
  • 而链表添加、删除数据很快,但是查找数据很慢,我们就想啊,有没有一种数据结构取二者之精华,那不就是一个添加,删除,查询都很快的数据结构吗?那用起来多舒服啊!这个取二者之精华的数据结构就是树(tree),而且...
  • 前言 最近面临毕业就业,在复习数据结构与算法,为了更好地掌握,加深印象,所以决定写一些博客来知识复现。 温馨提示:这篇博客可能不适合刚学数据结构的新手。 代码实现 package sjjg; public class ...
  • 删除二叉树节点java代码
  • 二叉树最复杂的步骤即为删除操作,此处只简单介绍一下具体思路:(1)如果待删除节点是一片树叶,那么它可以被立即删除。然后将其父节点的相应子节点(左节点或右节点)至空。(2)如果被删除节点有一个子节点,那么把...
  • 排序二叉树删除指定节点 (一)基本思路 {分3种情况} 情况一:若删除节点为叶子节点,那理论上直接删除就行。但操作上,会找到删除节点的父节点 parent,后判断删除节点是其左子节点还是右子节点,后指针置空即可...
  • 本文概要二叉树简介二叉树的构建二叉树 前序遍历二叉树 中序遍历二叉树 后序遍历查找二叉树最小值查找二叉树最大值删除二叉树最小值删除二叉树最大值判断二叉树是否存在某值求二叉树节点个数求二叉树层级求二叉树第 ...
  • Exception in thread “main” java.lang.NullPointerException(空指针异常) 按照指示,跳到代码146行,发现是在进行递归时没有判断左儿子和右儿子是否为空,如果为空,则会 出现空指针异常。 解决方法: 此时只...
  • 查找二叉树删除节点的操作

    千次阅读 2012-04-18 17:37:56
    对于拥有两颗子树的节点,首先用右子树最小的节点取代源节点,再递归删除此最小节点。 具体代码如下所示: package com.Algorithm.Tree; import java.util.*; import java.io.*; /* * author:Tammy Pi
  • 今天所讲的是二叉树的删除,小伙伴们点进来,肯定是对二叉树有说了解的吧啊,首先学习二叉树删除,建议先了解诶二叉树的建立,遍历,插入和查找,以便小伙伴们能够很好的掌握今天小编所讲的内容,接下来让我们一起来...
  • 删除节点二叉树操作中最复杂的。在删除之前首先要查找要删的节点,找到节点后,这个要删除的节点可能会有三种情况需要考虑。 1.该节点是叶子节点,没有子节点。 要删除叶子节点,只需要改变该节点的父节点的引用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 583
精华内容 233
关键字:

java二叉树删除节点

java 订阅