树1：二叉树基础
基本概念
树（Tree） 是一种非线性的分层数据结构，由节点（Node）和边（Edge）组成，满足以下条件：
- 根节点（Root）：存在且唯一一个没有父节点的节点，作为树的起点。
- 父子关系：除根节点外，每个节点有且仅有一个父节点。
- 连通性：所有节点均通过边连通，即从根节点出发可通过路径到达任意节点。
- 无环性：树中不存在环路，即没有从任一节点出发并沿边返回自身的路径。
- 层次结构：节点按父子关系形成分层结构，根节点位于第一层，其子节点位于第二层，依此类推。
叶节点（Leaf）：没有子节点的节点
子树（Subtree）：以某节点为根，包含其所有后代节点的子结构
度（Degree）：节点的子节点数量；树的度为所有节点度的最大值。
节点的高度（height）：当前节点大到叶子节点的最长路径（边的数量）
节点的深度（depth）：根节点到当前节点的的边的数量
层级（level）：节点的深度 + 1
树高度：从根到最远叶节点的最长路径边数，根节点的高度，树高 = 节点高度 + 节点深度
二叉树
我们使用最多的还是二叉树。二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。
叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。
叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。
二叉树的存储
完全二叉树并没有特别特殊的地方啊，更像是“芸芸众树”中的一种。那我们为什么还要特意把它拎出来讲呢？为什么偏偏把最后一层的叶子节点靠左排列的叫完全二叉树？如果靠右排列就不能叫完全二叉树了吗？这个定义的由来或者说目的在哪里？要理解完全二叉树定义的由来，我们需要先了解，如何表示（或者存储）一棵二叉树？
想要存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。
二叉链式存储法：
每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。
数组顺序存储法：
基于数组的顺序存储法。我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 i = 2 的位置，右子节点存储在 2 i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 i = 2 2 = 4 的位置，右子节点存储在 2 i + 1 = 2 2 + 1 = 5 的位置。
即，如果节点 X 存储在数组中下标为 i 的位置，下标为 2 i 的位置存储的就是左子节点，下标为 2 i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。
如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
堆其实就是一种完全二叉树，最常用的存储方式就是数组。
二叉树的遍历
根据对于当节点遍历顺序的不同，遍历二叉树可分为先序遍历、中序遍历和后续遍历三类。
先序遍历（前序遍历）：即先遍历当前节点，再递归遍历左子树，最后递归遍历右子树。
中序遍历：先遍历左子树，再遍历当前节点，最后遍历右子树。
后续遍历：先遍历左子树，再遍历右子树，最后遍历当前节点。
前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r时间复杂度是O(n)。
二叉搜索树
二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
查找
我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
插入
新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。
删除
二叉查找树的查找、插入操作都比较简单易懂，但是它的删除操作就比较复杂了 。针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。
第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。
第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。
实现
为了更好的实现树结构，定义树接口如下：
package cn.lishiyuan.algorithm.tree;
public interface LeeTree<T extends Comparable<T>> {
int size();
boolean isEmpty();
boolean contains(T element);
T find(T element);
void add(T element);
T remove(T element);
void clear();
}package cn.lishiyuan.algorithm.tree;
import java.util.Objects;
/**
* 二叉搜索树实现
*/
public class BinarySearchTree<T extends Comparable<T>> implements LeeTree<T>{
private Node<T> root;
private int size = 0;
public static class Node<T>{
private T data;
private Node<T> left;
private Node<T> right;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(T element) {
if (element == null){
return false;
}
Node<T> node = findNode(element);
return Objects.nonNull(node);
}
@Override
public T find(T element) {
if (element == null){
return null;
}
Node<T> node = findNode(element);
return node.data;
}
@Override
public void add(T element) {
if (element == null){
throw new NullPointerException();
}
Node<T> node = findNode(element);
// 不支持重复节点
if (Objects.isNull(node)){
node = newNode(element);
if (Objects.isNull(root)){
root = node;
size++;
}else {
Node<T> pnode = root;
// 查找合适的位置
while (true){
// 比当前节点小，向左树查找
if (node.data.compareTo(pnode.data) < 0){
if (pnode.left == null){
pnode.left = node;
size++;
break; }else {
pnode = pnode.left;
}
}else {
if (pnode.right == null){
pnode.right = node;
size++;
break; }else {
pnode = pnode.right;
}
}
}
}
}
}
/**
* 第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。
* 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
* 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。
* 然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。
* @param element
* @return
*/
@Override
public T remove(T element) {
if (element == null){
throw new NullPointerException();
}
// 查找元素
Node<T> node = root;
Node<T> parent = null;
while (node!=null) {
if (node.data.compareTo(element)==0) {
break;
}else if (node.data.compareTo(element) > 0){
// 向右
parent =node;
node= node.right;
}else {
// 向左
parent =node;
node = node.left;
}
}
if(node == null){
// 未找到
return null;
}
// 没有节点,直接删除
if(node.left == null && node.right == null){
if (parent == null){
// 说明是root
root = null;
}else {
if (parent.left == node){
parent.left = null;
}else {
parent.right = null;
}
}
size--;
return node.data;
}
// 左右节点都不为空，要将右子树最小的放到当前位置
if (node.left != null && node.right!=null){
// 右树的的最小节点
Node<T> min = node.right;
Node<T> minParent = node;
while (min.left != null){
min = min.left;
minParent = min;
}
// 交换到当前位置
T data = node.data;
node.data = min.data;
// 删除该最小节点
if (minParent.left == min){
minParent.left = min.right;
}else {
minParent.right = min.right;
}
min.right = null;
size--;
return data;
}
// 只有一个节点
if (parent == null){
// 说明是root
if (node.left != null){
root = node.left;
node.left = null;
}else {
root = node.right;
node.right = null;
}
}else {
if (parent.left == node){
if (node.left != null){
parent.left = node.left;
node.left = null;
}else {
parent.left = node.right;
node.right = null;
}
}else {
if (node.left!=null){
parent.right = node.left;
node.left = null;
}else {
parent.right = node.right;
node.right = null;
}
}
}
size--;
return node.data;
}
protected Node<T> findNode(T data){
if(isEmpty()){
return null;
}
Node<T> node = root;
while (node!=null){
if (data.compareTo(node.data) == 0){
return node;
}else if (data.compareTo(node.data) < 0){
node = node.left;
}else {
node = node.right;
}
}
return null;
}
private Node<T> search(Node<T> node, T data){
if(node == null){
return null;
}
if(node.data.compareTo(data) == 0){
return node;
}else if(node.data.compareTo(data) > 0){
// 左子树查找
return search(node.left,data);
}else{
// 右子树查找
return search(node.right,data);
}
}
private Node<T> newNode(T data){
Node<T> node = new Node<>();
node.data = data;
node.left = null;
node.right = null;
return node;
}
@Override
public void clear() {
root = null;
size = 0;
}
@Override
public String toString() {
if(root == null){
return "[]";
}
// 中序遍历
String str = toString(root);
return "["+str+"]";
}
private String toString(Node<T> node){
if (node == null){
return "";
}
StringBuilder builder = new StringBuilder();
String leftStr = toString(node.left);
if (!leftStr.isEmpty()){
builder.append(leftStr).append(",");
}
String nodeStr = node.data.toString();
builder.append(nodeStr);
String rightStr = toString(node.right);
if (!rightStr.isEmpty()){
builder.append(",").append(rightStr);
}
return builder.toString();
}
}中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。
时间复杂度
最坏时间复杂度出现在二叉树极端不平衡的情况下，这时候二叉树会退化成链表，其时间复杂度是O(n)
最好时间复杂度出现在完全二叉树的情况下，此时时间复杂度是O(logn)
评论已关闭