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. 树的高度或深度:树的最大层次数;
    ......

树的种类

  • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
  • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;
  • 二叉树:每个节点最多含有两个子树的树称为二叉树;

    • 完全二叉树:对于一颗二叉树,假设其深度为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 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;
        }
    }
}

层序遍历:使用数据结构 队列 实现:

参考

博客园
码农有道
LeetCode:91
打赏
评论区
头像
文章目录