21 / 02 / 24

Java 数据结构丨树

基本概念

这里说的树不是日常生活中所见的木本植物，而是一种非线性数据结构，把它叫做“树”是因为它看起来像一棵颠倒的树，也就是说它是根朝上，而叶朝下的。

在生活中，有很多逻辑关系并不是简单的线性关系，在实际场景中，常常存在着一对多、多对多的情况。例如，企业的上下级关系、家谱族谱图（Family tree），字典的目录，计算机文件目录......

树(tree)，是包含 n(n ≥ 1)个节点，(n -1) 条边的有限集（注意：当 n=0 时，树是空树）。在任意一个非空树中，它具有以下的特点：

  1. 有且仅有一个特定的点称为根节点；

  2. 当 n ＞ 1 时，除根结点之外，的其余数据元素被分为 m(m ≥ 0)个互不相交的有限集，其中每一个集合本身也是一棵树，被称作原树的子树(subtree)。 如果要把一个节点和边的集合定义为树，那么从根节点到其他任意一个节点都必须 有且只有一条 路径。

树的常用术语

  1. 根节点（root）：最顶层的节点，或者说，没有父节点的节点；

  2. 父节点（parent）：若一个节点含有子节点，则这个节点称为其子节点的父节点；

  3. 子节点（child）：一个节点含有的子树的根节点称为该节点的子节点；

  4. 兄弟节点（sibling）：具有相同父节点的节点互称为兄弟节点；

  5. 叶节点（leaf）：度为 0 的节点，或者说，没有子节点的点；

  6. 节点的度：一个节点含有的子树的个数称为该节点的度；

  7. 节点的层次：从根节点开始定义起，根节点为第 1 层，它的子节点为第 2 层，以此类推；

  8. 树的度：一棵树中，最大的结点的度称为树的度；

  9. 树的高度或深度：树的最大层次数；

  10. ...

树的种类

  1. 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；

  2. 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

  3. 二叉树：每个节点最多含有两个子树的树称为二叉树；

    • 完全二叉树：对于一颗二叉树，假设其深度为d（d > 1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；

    • 满二叉树：所有叶节点都在最底层的完全二叉树；

    • 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

    • 排序二叉树（Binary Search Tree）：也称二叉搜索树、二叉查找树、有序二叉树；

    • 霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

    • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。

二叉树

  1. 二叉树（Binary Tree）：是每个节点 最多只有两个 分支（可能只有一个，或者没有）的有序树。它的两个分支，被称作“左子树（left child）”，“右子树（right child）”，左子树和右子树又同样都是二叉树。二叉树的分支具有左右次序，不能随意颠倒。

  2. 满二叉树（Full Binary Tree）：一棵深度为 k，且有 (2 k − 1) 个节点的二叉树。

  3. 完全二叉树（Complete Binary Tree）：在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树。

满二叉树要求所有分支都是满的，而完全二叉树只需要保证最后一个节点之前的节点都齐全即可。 二叉树作为典型的有序树，许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树的实现

二叉树的每一个节点都包含三个成员变量：存储数据的变量 val、左子节点 left、右子节点 right。

class TreeNode {
    // 节点值
    int val;
    // 左子节点
    TreeNode left;
    // 右子节点
    TreeNode right;
    TreeNode(int x) { val = x; }
}

二叉树属于逻辑结构，也可以使用数组和链表实现。

当使用数组实现时，按照层级顺序把二叉树的节点放进数组中对应的位置上，如果某一个节点没有左子节点或右子节点，那么数组对应的位置也会空缺，所以对于一个稀疏的二叉树来说，用数组实现是非常浪费空间的；满二叉树紧凑排列才能不浪费空间。\r\n假设某节点的索引值为 i，那么它左子节点的索引是 (2 i + 1)，它右子节点的索引是 (2 i + 2)，而它的父节点（如果有）索引则为 (i - 1)/2 。

当使用链表实现时，需要指向子节点的指针，所以实例化每个节点后，需要构建各节点的引用指向。使用链表能避免数组存储浪费空间的问题，算法和结构相对简单，但使用二叉链表，由于缺乏父链的指引，在找回父节点时需要重新扫描树得知父节点的节点地址。

// 实例化节点，n1为根节点
TreeNode n1 = new TreeNode(9);
TreeNode n2 = new TreeNode(6);
TreeNode n3 = new TreeNode(8);
TreeNode n4 = new TreeNode(3);
TreeNode n5 = new TreeNode(4);

// 构建引用指向
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

二叉搜索树

在树中查找数据项的速度和在有序数组中查找一样快，并且插入、删除数据项的速度和链表的一样快。基于这个特点，二叉树最主要的应用在于查找操作和维持相对顺序这两个方面。 在查找操作方面，二叉搜索树更合适。它具有以下性质：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均 ＜ 它的根节点的值；

  2. 若任意节点的右子树不空，则右子树上所有节点的值均 ≥ 它的根节点的值；

  3. 任意节点的左、右子树也分别为二叉查找树；

对于一个节点分布相对均衡的二叉搜索树来说，如果节点总数为 N，那么搜索节点的时间复杂度是 O(log N)，更准确来说，是 O(log2 N)，最坏情况下为 O(N)（数列有序时，树退化成线性表），但也有在二叉搜索树基础上改良的平衡树，如 AVL 树，红黑树，可以使树的高度总是得到平衡，时间复杂度在最坏情况下也能达到 O(log N)。

基本操作

// 节点类
class Node{
    public int iData;
    public Node leftChild;
    public Node rightChild;

    public void display(){
        System.out.print('【');
        System.out.print(iData);
        System.out.print(',');
        System.out.print('】');
    }
}

// 树类
class Tree{
    // 根节点
    private Node root;
    public Tree(){ root = null; }

    // 搜索节点
    public Node find(int key){
        Node current = root;
        while(current.iData != key){
            if (key < current.iData){
                current = current.leftChild;
            }else {
                current = current.rightChild;
            }
            if (current == null){
                return null;
            }
        }
        return current;
    }
    // 插入节点：必须确定新节点的插入位置
    public void insert(int key){
        Node newNode = new Node();
        newNode.iData = key;
        if (root == null){
            root = newNode;
        }else{
            Node current = root;
            Node parent;
            while(true){
                parent = current;
                if (key < current.iData){
                    current = current.leftChild;
                    if (current == null){
                        parent.leftChild = newNode;
                        return ;
                    }
                }else {
                    current = current.rightChild;
                    if (current == null){
                        parent.rightChild = newNode;
                        return ;
                    }
                }
            }
        }
    }
    // 删除节点
    public boolean delete(int key){
        Node current = root;
        Node parent = root;
        boolean isLeftChild = true;

        while(current.iData != key){
            parent = current;
            if (key < current.iData){
                isLeftChild = true;
                current = current.leftChild;
            }else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null){
                return false;
            }
            // 删除没有子节点的节点
            if (current.leftChild == null && current.rightChild == null){
                // 清空根节点
                if (current == root){
                    root = null;
                }
                // 清空父节点的左叶节点
                else if (isLeftChild){
                    parent.leftChild = null;
                }
                // 清空父节点的右叶节点
                else{
                    parent.rightChild = null;
                }
            }
            // 删除只有一个子节点的节点
            else if (current.rightChild == null){
                // 取代根节点
                if (current == root){
                    root = current.leftChild;
                }
                //
                else if (isLeftChild){
                    parent.leftChild = current.leftChild;
                }
                //
                else{
                    parent.rightChild = current.leftChild;
                }
            }
            // 删除有两个子节点的节点：后续节点接上
            else{
                Node successor = getSuccessor(current);
                if (current == root){
                    root = successor;
                }else if (isLeftChild){
                    parent.leftChild = successor;
                }else {
                    parent.rightChild = successor;
                }
                successor.leftChild = current.leftChild;
            }
        }
        return true;
    }
    // 找删除节点delNode的后续节点
    private Node getSuccessor(Node delNode){
        Node successorParent = delNode;
        Node successor = delNode;
        // delNode的右子节点
        Node current = delNode.rightChild;
        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        if (successor != delNode.rightChild){
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }

二叉树的遍历

遍历意味着按照某种特定顺序访问树中所有的节点，但是遍历本身是一种线性操作，而二叉树是非线性数据结构，如何将非线性关联的节点转化为线性的序列输出呢？

从宏观的角度来看，二叉树的遍历分为：

  1. 深度优先遍历 -- 前序遍历、中序遍历、后序遍历；

  2. 广度优先遍历 -- 层序遍历。

// 前序遍历
public static void preOrder(Node t) {
    if (t == null) {
        return;
    }
    System.out.print(t.iData + " ");
    preOrder(t.leftChild);
    preOrder(t.rightChild);
}

// 中序遍历
public static void inOrder(Node t) {
    if (t == null) {
        return;
    }
    inOrder(t.leftChild);
    System.out.print(t.iData + " ");
    inOrder(t.rightChild);
}


// 后序遍历
public static void postOrder(Node t) {
    if (t == null) {
        return;
    }
    postOrder(t.leftChild);
    postOrder(t.rightChild);
    System.out.print(t.iData + " ");
}

如果要使用非递归的方式实现深度优先遍历，那么需要使用数据结构 栈 实现，以前序为例：

public static void preOrder2(Node t){
    Stack<Node> stack = new Stack<>();
    Node n = t;
    while (n != null || !stack.isEmpty()){
        // 迭代访问节点t的左子节点，入栈
        while (n != null){
            System.out.print(n.iData);
            stack.push(n);
            n = n.leftChild;
        }
        // 如果没有左子节点，就弹出，访问右子节点
        if (!stack.isEmpty()){
            n = stack.pop();
            n = n.rightChild;
        }
    }
}

层序遍历：

// 使用数组队列实现
public static void levelOrder(Node root) {
    Queue<Node> q1 = new ArrayDeque<>();
    if (root == null) {
        return;
    }
    if (root != null) {
        q1.add(root);
    }
    while (!q1.isEmpty()) {
        Node n1 = q1.poll();
        if (n1.leftChild != null) {
            q1.add(n1.leftChild);
        }
        if (n1.rightChild != null) {
            q1.add(n1.rightChild);
        }
        System.out.print(n1.iData + " ");
    }
    System.out.println();
}

// 使用链表队列实现
public static void levelOrder2(Node root) {
    Queue<Node> q2 = new LinkedList<>();
    if (root == null) {
        return;
    }
    if (root != null) {
        q2.offer(root);
    }
    while (!q2.isEmpty()){
        Node n2 = q2.poll();
        System.out.print(n2.iData + " ");
        if (n2.leftChild != null){
            q2.offer(n2.leftChild);
        }
        if (n2.rightChild != null){
            q2.offer(n2.rightChild);
        }
    }
    System.out.println();
}

优劣

在操作系统源程序中，被用来构造文件系统。Windows 和 Linux 等文件管理系统都是树型结构。在编译系统中，如 C 编译器源代码中，二叉树的中序遍历形式被用来存放 C 语言中的表达式。其次二叉树本身的应用也非常多，如哈夫曼二叉树用于 JPEG 编解码系统（压缩与解压缩过程）的源代码中，甚至于编写处理器的指令也可以用二叉树构成变长指令系统，另外二叉排序树被用于数据的排序和快速查找。

由于二叉树结构包括天然递归结构、与二分思想完美契合的特性，使得二叉树及其各种变种结构极其适合在各种场景下进行高效的查找操作，N 个节点的二叉查找树，最好情况下查找时间为 O(logN)，最坏情况下为 O(N)。

参考

  1. 二叉树——前序遍历、中序遍历、后序遍历、层序遍历详解(递归非递归) - bigsai - 博客园 ( cnblogs.com)

  2. 【数据结构与算法】一起搞定面试中的二叉树（一） ( qq.com)

  3. 94. 二叉树的中序遍历 - 力扣（LeetCode）

Data Structure
Java