树简介

树简介

树跟数组、链表、堆栈一样，是一种数据结构。它由有限个节点，组成具有层次关系的集合

• 节点的度：一个节点含有的子节点个数称为该节点的度；
• 树的度：一棵树中，最大节点的度称为树的度；
• 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 叶子节点：节点的度为0(也就是没有子节点的节点)；
• 深度：对于任意节点n，n的深度为从根到n的唯一路径长，根节点的深度为0；
• 高度：对于任意节点n，n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0

特点

• 每个节点要么没有子节点要么只有有限个子节点；
• 有一个特殊的节点，它没有父节点，称为根节点；
• 每一个非根节点有且只有一个父节点；
• 树里面没有环路

树的表示方式

父节点表示法

private Node<T>[] nodes; 
/**
 * 使用数组存储
 * @param <T>
 */
static class Node<T>{
    private T data;
    // 记录父节点所在数组的索引位置
    private int parent;
}

这种方式可以快速的找到父节点，但是想要找某个节点的所有子节点需要遍历整个树才可以

孩子链表表示法

每个非叶子节点通过一个链表来记录它所有的子节点

private Node<T>[] nodes; 
static class Node<T>{
    T data;
    ChildNode<T> firstChild; // 指向第一个孩子节点
}

static class ChildNode<T>{
    T data;
    ChildNode<T> nextSibling; // 指向下一个节点
}

这种方式可以快速找到它的所有子节点，但是找到某个节点的父节点需要遍历整个节点数组

分类

按照有序性，可以分为有序树和无序树：

• 无序树：树中任意节点的子节点之间没有顺序关系
• 有序树：树中任意节点的子节点之间有顺序关系

按照节点包含子树个数，可以分为B树和二叉树。