1 二叉树

二叉树（Binary Tree）是n （n>=0）个节点的有限集合，该集合可以为空集（称为空二叉树），或者由一个根节点和两个互不相交的，分别称为根节点的左子树和右子树的二叉树组成。
特点：
(1) 每个节点最多有两个子树，所以二叉树不存在度大于2的节点（结点的度：结点拥有的子树的数目），可以没有子树或者一个子树。
(2) 左子树和右子树有顺序，次序不能任意颠倒。
(3) 即使树种某节点只有一颗子树，也要区分是左子树还是右子树。

2 二叉搜索树（Binary Search Tree）

二叉搜索树是二叉树的一种,是应用非常广泛的一种二叉树,英文筒称为BST,又被称为:二叉查找树、二叉排序树。
特点：
(1) 任意一个节点的值都大于其左子树所有节点的值。
(2) 任意一个节点的值都小于其右子树所有节点的值。
(3) 它的左右子树也是一棵二叉搜索树。
(4) 二叉搜索树可以大大提高搜索数据的效率
(5) 二叉搜索树存储的元素必须具备可比较性

3 实现

3.1 接口

package com.structure.tree; /**  * @Description:  * @Author: zhurongsheng  * @Date: 2020/4/27 00:09  */ public interface BinaryTree { /**      * 获取节点数量      */ int size(); /**      * 是否为空      */ boolean isEmpty(); /**      * 清空      */ void clear(); /**      * 添加节点      */ void add(Integer element); /**      * 删除节点      */ void remove(Integer element); /**      * 包含节点      */ boolean contains(Integer element); /**      * 前序      */ void preOrderTraversal(); /**      * 中序      */ void inOrderTraversal(); /**      * 后序      */ void postOrderTraversal(); /**      * 层序      */ void levelOrderTraversal(); /**      * 二叉树高度      */     Integer height(); /**      *  完全二叉树      */     Boolean isComplete(); } 

3.2 BinarySearchTree

package com.structure.tree; import org.omg.CORBA.NO_IMPLEMENT; import java.util.LinkedList; /**  * @Description:  * @Author: zhurongsheng  * @Date: 2020/4/26 23:46  */ public class BinarySearchTree implements BinaryTree { /**      * 节点数量      */ protected int size = 0; /**      * 根节点      */ protected Node root; @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void clear() { if (root != null) {             LinkedList<Node> nodes = new LinkedList<>();             nodes.push(root); while (!nodes.isEmpty()) {                 Node node = nodes.pop(); if (node.left != null) {                     nodes.addLast(node.left); } if (node.right != null) {                     nodes.addLast(node.right); }                 node.right = null;                 node.left = null;                 node.parent = null;                 node.element = null; } } } private void checkElementIsNull(Integer element) { if (element == null) { throw new IllegalArgumentException("element must not be null"); } } protected void addRoot(Integer element) { checkElementIsNull(element);         root = new Node(element, null, null, null);         size++; } protected static class Node {         Integer element;         Node left;         Node right;         Node parent; Node(Integer element, Node parent, Node left, Node right) { this.element = element; this.parent = parent; this.left = left; this.right = right; } } @Override public void inOrderTraversal() { inOrderTraversal(root); } private void inOrderTraversal(Node node) { if (node == null) { return; } inOrderTraversal(node.left);         System.out.println(node.element); inOrderTraversal(node.right); } @Override public void preOrderTraversal() { preOrderTraversal(root); } private void preOrderTraversal(Node node) { if (node == null) { return; }         System.out.println(node.element); preOrderTraversal(node.left); preOrderTraversal(node.right); } @Override public void postOrderTraversal() { postOrderTraversal(root); } @Override public void levelOrderTraversal() {         LinkedList<Node> nodes = new LinkedList<>();         nodes.push(root); while (!nodes.isEmpty()) {             Node node = nodes.pollFirst(); if (node != null) { if (node.left != null) {                     nodes.addLast(node.left); } if (node.right != null) {                     nodes.addLast(node.right); }                 System.out.println(node.element); } } } @Override public Integer height() { return height(root); } /**      * 判断是否为完全二叉树采用层序遍历：      * node.left!=null && node.right!=null 将node.left node.right按顺序入队伍      * node.left==null && node.right!=null return false      * node.left!=null && node.right==null 剩下节点必须为叶子节点      * node.left==null && node.right==null 剩下节点必须为叶子节点      */ @Override public Boolean isComplete() { if (root == null) { return false; }         LinkedList<Node> nodes = new LinkedList<>();         nodes.addLast(root); boolean leaf = false; while (!nodes.isEmpty()) {             Node node = nodes.pollFirst(); if (node == null) { return false; } if (leaf && !isLeaf(node)) { return false; } if (hasTwoChild(node)) {                 nodes.addLast(node.left);                 nodes.addLast(node.right); } else if (node.left == null && node.right != null) { return false; } else {                 leaf = true; if (node.left != null) {                     nodes.addLast(node.left); } } } return true; } private Boolean isLeaf(Node node) { if (node == null) { return false; } return node.left == null && node.right == null; } private Boolean hasTwoChild(Node node) { if (node == null) { return false; } return node.left != null && node.right != null; } private Integer height(Node node) { if (node == null) { return 0; } return Math.max(height(node.left), height(node.left)) + 1; } private void postOrderTraversal(Node node) { if (node == null) { return; } postOrderTraversal(node.left); postOrderTraversal(node.right);         System.out.println(node.element); } @Override public void add(Integer element) { //添加头节点 if (root == null) { addRoot(element); return; } //添加叶子节点,找父节点         Node node = root;         Node parentNode; int cmp; do {             cmp = element - node.element;             parentNode = node; if (cmp > 0) {                 node = node.right; } else {                 node = node.left; } } while (node != null); //循环结束后，parentNode是父节点         Node newNode = new Node(element, parentNode, null, null); if (cmp > 0) {             parentNode.right = newNode; } else {             parentNode.left = newNode; }         size++; } /**      * 1 叶子节点直接删除      * 2 度为1的节点，修改当前节点父节点、子节点的指针。      * 3 度为2的节点，用前驱（后继）节点的值代替当前root的值，然后删除前驱（后继）节点。      */ @Override public void remove(Integer element) {         Node node = node(element); if (node == null) { return; } remove(node); } private Node node(Integer element) {         Node node = root; while (node != null) { if (element > node.element) {                 node = node.right; } else if (element < node.element) {                 node = node.left; } else { return node; } } return null; } private void remove(Node node) { if (hasTwoChild(node)) { //找到前驱节点             Node predecessor = predecessor(node.left); //用前驱节点的值进行覆盖根节点的值             node.element = predecessor.element; //更改node指针为node的前驱节点，直接删除node             node = predecessor; } //如果是叶子节点 if (isLeaf(node)) { //根节点 if (node.parent == null) {                 root = null; } else { if (node.parent.left == node) {                     node.parent.left = null; } else {                     node.parent.right = null; } } } else {             Node replacement = node.left != null ? node.left : node.right;             replacement.parent = node.parent; if (node.parent == null) { //根节点                 root = replacement; } else if (node.parent.left == node) {                 node.parent.left = replacement; } else if (node.parent.right == node) {                 node.parent.right = replacement; } }         node.parent = null;         node.element = null;         size--; } private Node predecessor(Node node) { if (node != null && node.right != null) { return predecessor(node.right); } else { return node; } } @Override public boolean contains(Integer element) {         Node node = root; if (node != null) { do { if (element > node.element) {                     node = node.right; } else if (element < node.element) {                     node = node.left; } else { return true; } } while (node != null); } return false; } }