树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)