二叉搜索树

一、操作:

  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 条评论
登录 后参与评论

相关文章

来自专栏Felix的技术分享

C++与汇编小结

41040
来自专栏老马说编程

(38) 剖析ArrayList / 计算机程序的思维逻辑

从本节开始,我们探讨Java中的容器类,所谓容器,顾名思义就是容纳其他数据的,计算机课程中有一门课叫数据结构,可以粗略对应于Java中的容器类,我们不会介绍所有...

22850
来自专栏微信公众号:Java团长

Java HashMap的工作原理

面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下...

6620
来自专栏desperate633

LeetCode 349. Intersection of Two Arrays题目代码代码

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].

6310
来自专栏软件工程师成长笔记

Map集合按照ASCII码从小到大(字典序)排序--JAVA

1K20
来自专栏小二的折腾日记

LeetCode-15-3Sum&&4Sum

同之前的2sum差不多,计算两个的和的方式是:为了避免重复,重新用一个set容器,解决重复的问题。但是这里的情况是,重复的一个数字是可以出现的,而且是三个数字相...

9210
来自专栏Linux驱动

6.QT-简易计算器实现(详解)

38450
来自专栏DT乱“码”

实现MD5加密

/**  * 实现MD5加密  *  */ public class MD5 {  /**   * 获取加密后的字符串   * @param ...

24690
来自专栏Android机动车

RxJava从入门到不离不弃(三)——转换操作符

所有这些Operators都作用于一个可观测序列,然后变换它发射的值,最后用一种新的形式返回它们。概念实在是不好理解,下面我们结合实际的例子一一介绍。

8630
来自专栏猿人谷

对称字符串的最大长度

题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。 思路...

25580

扫码关注云+社区

领取腾讯云代金券