基本概念

树(Tree) 是一种非线性的分层数据结构,由节点(Node)和边(Edge)组成,满足以下条件:

  1. 根节点(Root):存在且唯一一个没有父节点的节点,作为树的起点。
  2. 父子关系:除根节点外,每个节点有且仅有一个父节点。
  3. 连通性:所有节点均通过边连通,即从根节点出发可通过路径到达任意节点。
  4. 无环性:树中不存在环路,即没有从任一节点出发并沿边返回自身的路径。
  5. 层次结构:节点按父子关系形成分层结构,根节点位于第一层,其子节点位于第二层,依此类推。

叶节点(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)

标签: 算法基础

添加新评论