java模拟二叉树

程序员文章站 2022-06-16 11:10:01

...

java模拟二叉树

首先二叉树应该由0至多个节点组成，节点用于存放自身的数据和连接其他叶子节点。

首先我们先创建BST二叉树类，它应是由0至多个节点组成，size属性表明二叉树内实际元素个数。因为我们二叉树是需要根据值进行排序的，所以需要实现Comparable接口。特别提醒此处的extends是实现接口的作用。泛型E用于表明该节点处的值。

部分代码如下：

public class BST<E extends Comparable<E>> {


    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

其次我们再创建节点类，只用BST类使用，所以我们选择匿名内部类的实现方式。节点中存放的是自身的数据和其下的左右子树。

部分代码：

    private class Node {
        E e;
        Node left;
        Node right;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }

然后我们可以写几个基础方法像外部提供信息。

	//	返回二叉树内的实际元素个数
	public int size() {
        return size;
    }
	// 判断二叉树是否为空
    public boolean isEmpty() {
        return size == 0;
    }

下面我们来实现添加二叉树内的元素，不能插入重复值。

	// 添加元素
	 public void add(E e) {
        root = add(root, e);
    }

	//  这里我们使用递归的写法
    private Node add(Node node, E e) {
       // 收敛条件 递归到最后 新建节点返回作为上一节点的左子树或右子树
        if (node == null) {
        	// 元素个数+1
            size++;
            return new Node(e);
        }
        // 如果要插入的节点小于此节点的值 那么递归到该节点的左子树下
        // 如果要插入的节点大于此节点的值 那么递归到该节点的右子树下
        // 如果要插入的节点等于此节点的值 那么什么都不做 直接返回
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

接下来我们再实现查找元素的方法，如果有返回true ，否则返回false。

   public boolean contains(E e) {
        return contains(root, e);
    }
	
	// 按照我们现在的搜索算法 如果是满二叉树那么 算法复杂度为O(logn)
	// 如果十分极端的情况下，一个二叉树只有左子树或者只有右子树
	// 那么这个二叉树将变成链式结构，算法复杂度为O(n)
   private boolean contains(Node node, E e) {
        // 收敛条件 如果找不到该值 返回false
        if (node == null)
            return false;
        // 收敛 如果二值相等 那么返回true
        if (e.compareTo(node.e) == 0)
            return true;
        // 如果改值小于此处节点值 递归值该左节点下
        else if (e.compareTo(node.e) < 0)
            return contains(node.left, e);
         // 如果改值大于此处节点值 递归值该右节点下
        else
            return contains(node.right, e);

    }

接下来我们再去完成删除元素的方法。
我画个图给大家整理一下思路。
前驱节点是它左子树的最右下节点。
后继节点是它右子树的最左下节点。
java模拟二叉树

在此之前我们先完成两个辅助方法的编写。一是查找该节点下的最小值。二是删除该节点下的最小值。

   // 找到该节点下的最小元素值
   private Node minmum(Node node) {
   		// 收敛条件 如果改节点无左子树了，则其为最小子节点 返回
        if (node.left == null)
            return node;
		// 否则 继续往其左子树下递归
        return minmum(node.left);
    }

    private Node removeMin(Node node) {
        Node root = node;
        // 如果该节点无左子树那么直接删除该节点返回其右子树节点
        if (node.left == null) {
            return node.right;
        }
        // 迭代其下的所有左子树 找到最小的左子树删除
        while (node.left != null) {
            if (node.left.left == null) {
                //将该节点下左子树下的的右子树移至其父节点位置
                node.left = node.left.right;
                size--;
                break;
            }
            // 迭代
            node.left = node.left.left;
        }
        return root;
    }

好了有了这两个辅助方法，我们可以正式的编写二叉树的删除方法了。

    public void remove(E e) {
        root = remove(root, e);
    }

    private Node remove(Node node, E e) {
		// 节点为空 返回空
        if (node == null)
            return null;
		// 如果小于该节点 递归其左子树下
		// 如果大于该节点 递归其右子树下
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else {
			// 如果等于该节点 
			// 左子树为空的情况下 直接返回其右子树
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
	        // 右子树为空的情况下 直接返回其左子树
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //找到后继
            Node successor = minmum(node.right);
            // 后继的右节点 就是删除完node右子树节点最小左子树后的节点
            successor.right = removeMin(node.right);
            // 后继的左节点就是 原先node处的左子树
            successor.left = node.left;
            node.left = null;
            //返回之前的递归调用
            return successor;
        }
    }

如此一来，我们便完成了所有二叉树的添加，删除和查找。

前中后遍历我们下次再继续讲。

完整代码

public class BST<E extends Comparable<E>> {


    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void add(E e) {
        root = add(root, e);
    }

    public Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node node, E e) {
        if (node == null)
            return false;
        if (e.compareTo(node.e) == 0)
            return true;
        else if (e.compareTo(node.e) < 0)
            return contains(node.left, e);
        else
            return contains(node.right, e);

    }

    public void preOder() {
        preOder(root);
    }

    private void preOder(Node node) {
        if (node == null)
            return;
        System.out.println(node.e);
        preOder(node.left);
        preOder(node.right);
    }

    public void remove(E e) {
        root = remove(root, e);
    }

    private Node remove(Node node, E e) {

        if (node == null)
            return null;

        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else {

            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //找到后继
            Node successor = minmum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = null;
            return successor;
        }
    }

    private Node removeMin(Node node) {
        Node root = node;
        // 如果该节点无左子树那么直接删除该节点返回其右子树节点
        if (node.left == null) {
            return node.right;
        }
        // 迭代其下的所有左子树 找到最小的左子树删除
        while (node.left != null) {
            if (node.left.left == null) {
                //将该节点下左子树下的的右子树移至其父节点位置
                node.left = node.left.right;
                size--;
                break;
            }
            // 迭代
            node.left = node.left.left;
        }
        return root;
    }

    private Node minmum(Node node) {
        if (node.left == null)
            return node;

        return minmum(node.left);
    }


    private class Node {
        E e;
        Node left;
        Node right;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }
  
}

java模拟二叉树

java模拟二叉树

首先二叉树应该由0至多个节点组成，节点用于存放自身的数据和连接其他叶子节点。

Java8如何构建一个Stream示例详解

Java中EnumMap代替序数索引代码详解

Java中finally和return的关系实例解析

详细分析Java并发集合ArrayBlockingQueue的用法

IntelliJ IDEA 中使用jRebel进行 Java 热部署教程图解

Java SE Development Kit (JDK7) 介绍与配置方法

MyEclipse8.5导入java项目后会出现红色波浪线怎么办?

Java jdk环境变量配置方法

Android模拟器对应的电脑快捷键说明

我是如何自学Java到找到工作的心得