1 祖先、后代#

从一棵树$T$的根节点$r$到任意节点$x$的唯一简单路径上的任意节点$y$称为节点$x$的祖先，反之，如果$y$是$x$的祖先，则$x$是$y$的后代。

显然，一个节点与自身互为祖先和后代。

如果$x$是$y$的后代，且$x\ne y$，则称$x$是$y$的真后代，$y$是$x$的真祖先。

2 父节点、子节点、兄弟节点#

设从一棵树$T$的根节点$r$到任意节点$x$的唯一简单路径上最后一条边是$(y,x)$，则$y$是$x$的父节点，也叫双亲，$x$是$y$的子节点，也叫孩子，如果两个节点有相同的父节点，则它们是兄弟节点。

根是树中唯一没有父节点的节点。

3 叶子节点，内部节点#

一个没有子节点的节点称为叶子节点，非叶子节点为内部节点。

4 度#

有根树$T$中一个节点$x$的子节点数目为$x$的度。

NOTE

与图/自由树不同，有根树中除根节点外均有且只有一条连向父节点的边，故有根树中的度仅考虑连向子节点的边，而不是所有边

显然，叶子节点就是度为$0$的节点。

5 深度、高度、层#

有根树$T$中从根节点$r$到节点$x$的一条简单路径长度即为$x$的深度，从$x$到叶子节点的最长简单路径上边的数目即为$x$的高度，树的一个层包含了同一深度的所有节点。树的高度是指树中节点的最大深度。

根节点的深度为$0$，叶子节点的高度为$0$。

6 子树#

由有根树$T$中一个节点$x$的所有后代构成的节点称为以$x$为根的子树

1.左孩子、右孩子#

若一个节点左子树非空，则左子树的根为该节点的左孩子，若一个节点右子树非空，则右子树的根为该节点的右孩子。

二叉树不仅仅是度不超过$2$的有序树的，对于只有一个孩子的节点，区分左孩子和右孩子是必要的。

2.真二叉树#

除叶子节点外的节点度均为$2$的二叉树。

3.满二叉树#

所有叶子节点深度相同，且所有内部节点度为$2$的二叉树。

IMPORTANT

满二叉树（Full Binary Tree）国内外定义存在不同，国外说的满二叉树一般指国内说的真二叉树。

4.完全二叉树#

除最后一层，每一层节点数均达到最大值的二叉树。

5.位置树#

在一棵位置树中，节点的孩子被标记为不同的正整数，不同于有序树，如果没有孩子被标记为整数$i$，则该节点的第$i$个孩子缺失。

6.$k$叉树#

若对于位置树的每个节点，所有标记大于$k$的孩子均缺失，则称这棵树为**$k$叉树**。

二叉树是$k=2$的$k$叉树。

同理可推出真$k$叉树、满$k$叉树和完全$k$叉树的定义。