二叉搜索树

一、操作:

  1. 判断元素是否存在:递归的在左右子树中查找
  2. 查找最小元素:在左子树中递归或者循环
  3. 查找最大元素:在右子树中递归或循环
  4. 插入:递归的插入,大于则插入在节点的右子树,小于则左子树,等于则是重复节点不作处理
  5. 删除:递归删除( 或者说递归查找需要删除的元素 ),找到该元素后,如果元素有两个子节点那么久找到这个元素的右子树的最小元素代替要删除的元素,然后再删除那个右子树上的最小元素。如果只有一个子节点直接让要被删除的节点赋值上他的子节点。 二、代码
package Tree;

import sun.tools.tree.ThisExpression;

import java.util.Stack;

public class MyBinaryTree {
    public class BinaryNode implements Comparable<Integer> {
        BinaryNode lChild;
        BinaryNode rChild;
        Integer ele;

        BinaryNode(Integer ele) {
            this(ele, null, null);
        }

        BinaryNode(Integer ele, BinaryNode lChild, BinaryNode rChild) {
            this.ele = ele;
            this.lChild = lChild;
            this.rChild = rChild;
        }

        @Override
        public int compareTo(Integer o) {
            return ele - o;
        }
    }

    private BinaryNode root;

    public MyBinaryTree() {
        root = null;
    }

    public MyBinaryTree(Integer ele) {
        root = new BinaryNode(ele, null, null);
    }

    public void makeEmpty() {
        this.root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(Integer node) {
        return contains(node, root);
    }

    public boolean contains(Integer node, BinaryNode root) {
        if (root == null) {
            return false;
        }
        int result = root.ele.compareTo(node);
        if (result > 0) {
            return contains(node, root.lChild);
        } else if (result < 0) {
            return contains(node, root.rChild);
        } else {
            return true;
        }
    }

    public Integer findMin() {
        if (isEmpty()) {
            throw new RuntimeException();
        }
        return (Integer) findMin(root);
    }

    public Integer findMin(BinaryNode root) {
        if (root == null) {
            return null;
        } else if (root.lChild == null) {
            return root.ele;
        } else {
            return findMin(root.lChild);
        }
    }

    public Integer findMax() {
        if (isEmpty()) {
            throw new RuntimeException();
        }
        return (Integer) findMax(root).ele;
    }

    public BinaryNode findMax(BinaryNode root) {
        if (root == null) {
            return null;
        } else if (root.rChild == null) {
            return root;
        } else {
            return findMax(root.rChild);
        }
    }

    public void insert(Integer x) {
        root = insert(x, root);
    }

    public BinaryNode insert(Integer ele, BinaryNode root) {
        if (root == null) {
            return new BinaryNode(ele);
        }
        int result = root.compareTo(ele);
        if (result < 0) {
            root.rChild = insert(ele, root.rChild);
        } else if (result > 0) {
            root.lChild = insert(ele, root.lChild);
        } else ;
        return root;
    }

    public BinaryNode remove(Integer ele) {
        root = remove(ele, root);
        return root;
    }

    public BinaryNode remove(Integer ele, BinaryNode root) {
        if (root == null) {
            return null;
        }
        int result = root.compareTo(ele);
        if (result > 0) {
            root.lChild = remove(ele, root.lChild);
        } else if (result < 0) {
            root.rChild = remove(ele, root.rChild);
        }
        //这个地方就是递归的结束条件  也就是当我们找到了要删除的节点,这时候要分情况如果两个子节点都不空我们需要把右子树的最小值的替换到当前节点然后删除右子树最小节点
        //当有一个或者0个节点的时候我们只需要把左边或者右边挂上去就行
        else if (root.lChild != null && root.rChild != null) {
            root.ele = findMin(root.rChild);
            root.rChild = remove(root.ele, root.rChild);
        } else {
            root = root.lChild == null ? root.rChild : root.lChild;
        }
        return root;
    }

    public void printTree() {
        preOrder(root);
    }

    public void preOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.ele + " ");
        if (root.lChild != null) {
            preOrder(root.lChild);
        }
        if (root.rChild != null) {
            preOrder(root.rChild);
        }
    }

    public void inOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        if (root.lChild != null) {
            inOrder(root.lChild);
        }
        System.out.print(root.ele + " ");
        if (root.rChild != null) {
            inOrder(root.rChild);
        }
    }

    public void subOrder(BinaryNode root) {
        if (root == null) {
            return;
        }
        if (root.lChild != null) {
            inOrder(root.lChild);
        }
        if (root.rChild != null) {
            inOrder(root.rChild);
        }
        System.out.print(root.ele + " ");
    }

    public void preOrder_1(BinaryNode root) {
        Stack<BinaryNode> stack = new Stack<>();
        if (root == null) {
            return;
        }
        // stack.push(root);
        BinaryNode p = root;
        System.out.printf(p.ele + " ");
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                System.out.printf(p.ele + " ");
                stack.push(p);
                p = p.lChild;
            } else {
                p = stack.pop();
                p = p.rChild;
            }
        }
    }

    public void inOrder_1(BinaryNode root) {
        BinaryNode p = root;
        Stack<BinaryNode> stack = new Stack<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.lChild;
            } else {
                p = stack.pop();
                System.out.printf(p.ele + " ");
                p = p.rChild;
            }
        }
    }

    public void subOrder_1(BinaryNode root) {
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        BinaryNode q = null;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.lChild;
            } else {
                p = stack.peek();
                if (p.rChild == null || p.rChild == q) {
                    q = p;
                    p = stack.pop();
                    System.out.printf(p.ele + " ");
                    p = null;
                } else {
                    p = p.rChild;
                }
            }
        }
    }

    public BinaryNode getRoot() {
        return this.root;
    }


}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 优先队列

    优先队列基本介绍 ​ 优先队列又叫做堆,他是一种比较特殊的完全二叉树。所谓完全二叉树就是一层层的堆叠,本层不满就不能堆放下一层。并且优先队列还有一个特点就...

    lwen
  • ConcurrentHashMap 源码分析

    ConcurrentHashMap 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 ...

    lwen
  • 数据结构Stack

    ​ 在很多应用中,我们需要维护多个对象的集合,这种操作非常简单。我们可能想要向集合中 加入某个元素,去掉某个元素,以及遍历 集合中的元素并对他们执行某种操...

    lwen
  • 【leetcode刷题】T112-验证二叉搜索树

    节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

    木又AI帮
  • Flat风格的Qml组合框

    Qt君
  • Linux 命令(83)—— groups 命令

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    Dabelv
  • Leetcode【700、872、897、965、1022】

    1、判断叶子的条件是 root.left == None and root.right == None,返回 [root.val]; 2、还要注意单子树的情况...

    echobingo
  • 二叉树高频题

    Given a binary tree, return the preorder traversal of its nodes' values.

    王脸小
  • 【剑指Offer】二叉树的镜像

    输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]

    小新哟
  • 如何使用CP / SCP / RSYNC在Linux中排除特定目录?

    对于任何系统管理员或一般Linux操作系统用户而言,在服务器之间执行文件复制操作都是一项常见任务。在将文件从一个系统复制到另一个系统时,由于某些特定原因,我们可...

    用户6543014

扫码关注云+社区

领取腾讯云代金券