树 (Tree)

定义

一种非线性的数据结构。在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 $n$ （ $n > 0$ ）个有限节点组成一个具有层次关系的集合。

把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

根节点（又称头节点, root）：最上面的节点，根节点是唯一没有父节点的节点。

孩子（children）节点和父节点（Parent）：节点A的指针指向的节点们，被成为这个节点A的孩子节点(可能会有节点没有孩子节点)。反过来，A称为其孩子节点的父节点。

兄弟节点（sibling）：若两个节点的父节点是同一个，则称这两个节点为兄弟节点

叶子节点（leaf）：没有==~~孩子节点~~==的节点被称为叶子节点，其他节点成为内部节点（internal node）

祖先节点（ancestor）和子孙节点（descendent）：如果从A节点能链接到B节点，则A为B的祖先节点，B为A的子孙节点。

子树（sub-tree）：涉及到了树的递归，可以这样说，一棵树是由根节点和他的子树构成以上图1节点为例，有左右两个子树(深红色和黄色)。

有N个节点的树，一定有N-1条边。

宽度 Width：某一层的宽度表示该层中含有的节点的个数。树的宽度为所有层中最大的宽度。

深度 Depth：节点X的深度定义为从根节点走到节点X经过边的个数。

高度 Height：节点X的高度定义为从节点X到所有叶子节点中经过的最长路径（边的个数）。树的高度为根节点的高度。 |300

Note

只有一个节点的树，其高度为 $0$ 空树指的是没有节点的树，称它的高度为 $- 1$

注意区分深度和高度两个定义

常用来存储和组织具有层级结构的数据，是一种非线性的数据结构。

二叉树（Binary Tree）：一个树中的节点最多含有两个孩子节点的树，称为二叉树。