《Tree 的基本概念》

发表于 2024-05-19 分类于算法与数据结构， Tree 阅读次数：本文字数： 1.6k 阅读时长 ≈ 6 分钟

《算法与数据结构：Tree 的基本概念》

树的基本概念

树（Tree）结构简介

树是一种层级数据结构，非常适合用来表示具有层级关系或者需要快速搜索操作的数据集合。它由节点 Nodes 组成，这些节点通过边 Edges 相连。一个树结构有以下特点：

树与子树：树是一个有限集合，子树则是该集合的子集。就像套娃一样，一棵树下面还包含着其子树。比如，树 T1 的子树为树 T2、T3、T4，树 T2 的子树为 T5、T6。上图中还有许多子树没有标记出来。
结点 (Node)：一个结点包括一个数据元素和若干指向其子树分支。比如，在树 T1 中，结点 A 包括一个数据元素 A 和三个指向其子树的分支。上图中共有 18 个结点。
根结点 (Root)：一颗树只有一个树根，这是常识。在数据结构中，“树根” 即根节点。比如，结点 A 是树 T1 的根结点；结点 C 是树 T1 的子结点，是树 T3 的根结点。
度 (Degree)：一个结点拥有的子树数。比如，结点 A 的度为 3，结点 G 的度为 2，结点 H 的度为 1。
叶子 (Leaf)/ 终端结点：度为 0 的结点被称为叶子结点，很形象。比如对于树 T1 来说，结点 F、K、L、M、N、O、P、Q、R 均为叶子节点。
分支结点 / 非终端结点：和叶子结点相对，即度不为 0 的结点。
内部结点：顾名思义在树内部的结点，即不是根结点和叶子结点的结点。
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。如上图，A 是 B 的父节点。
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。如上图，B 是 A 的孩子节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点。如上图，B、C 是兄弟节点。
堂兄弟节点：双亲在同一层的节点互为堂兄弟节点。如上图，E、F、G、H 互为堂兄弟节点。
节点的祖先：从根到该节点所经分支上的所有节点。如上图，A 是所有节点的祖先。
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图，所有节点都是 A 的子孙。
层次 (Level)：从根结点开始，根为第一层，根的孩子为第二层，依次往下。比如，结点 K 在树 T1 中的层次为 4。
深度 (Depth)/ 高度：指树的最大层次。比如，树 T1 的高度为 4 。
有序树: 树中任意节点的子结点之间有顺序关系，这种树称为有序树。
无序树 : 树中任意节点的子结点之间没有顺序关系，这种树称为无序树，也称为自由树 。
森林：由 m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除，则该树就变成了一片森林，森林中的树由原来根节点的各棵子树构成。

树的类型

二叉树（Binary Tree）：每个节点最多有两个子节点。
二叉搜索树（Binary Search Tree, BST）：左子节点总是小于或等于父节点，右子节点总是大于或等于父节点。
平衡二叉树（AVL Tree）：任何两个子树的高度差不超过一。
红黑树（Red-Black Tree）：一种自平衡二叉搜索树。
B 树和 B + 树：常用于数据库和文件系统。

树概念图

二叉树

二叉树的基本结构

class Node<E> {
    E key;
    Node<E> left, right;
    
    public Node(E item) {
        key = item;
        left = right = null;
    }
}

二叉树的定义

二叉树的前提是一棵树，满足上述对树的定义。
二叉树节点最多有两个子节点，分别是左子节点和右子节点

各种类型的二叉树

满二叉树

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

满二叉树

完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

完全二叉树

斜二叉树

这个很好理解，斜二叉树就是斜的二叉树，所有的节点只有左子树的称为左斜树，所有节点只有右子树的二叉树称为右斜树。

斜二叉树

二叉树的存储

二叉树多采用两种方法进行存储，基于数组的顺序存储法和基于指针的二叉链式存储。

基于数组的顺序存储

左孩子节点:
$$
leftchild = parent\ast2+1
$$
右孩子节点:
$$
rightchild = parent\ast2+2
$$
父亲节点:
$$
parent = （child -1）\div 2
$$

基于指针的链表存储

static class Node<K, V> {
    public K key;
    public V value;
    public Node<K, V> left, right;

    public Node(K key, V value, Node<K, V> left, Node<K, V> right) {
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node(K key, V value) {
        this(key, value, null, null);
    }
}