ji-ben-gai-nian.md

基本概念

树的定义

树是一种非线性数据结构。如图所示就是一颗树，它是由若干结点（类似于A，B，C）等的集合，是有唯一的根结点A和若干颗不相交的子树（如E，I，J，P，Q就是一颗子树）组成的。

{% hint style="info" %} 树的结点数可以为0，此时这棵树是一颗空树。 {% endhint %}

基本术语

结点

A，B，C等都是结点，结点不仅包含数据元素，而且包含指向子树的指针。

结点的度

结点拥有分支的个数或子树的个数。例如A结点有6个分支，故A结点的度为6。

树的度

树中各结点度的最大值。上图中结点度最大为6，最小为0，所以树的度为6。

叶子结点

也叫做终端结点，指度为0的点。例如B，C，H等

孩子结点

结点的子树的根。如A的孩子为C，D，E。

双亲结点

与孩子结点相对应。C，D，E的双亲是A。

兄弟结点

同一个双亲的孩子之间称为兄弟结点。如C，D，E就是兄弟结点。

树的层次

从根开始，根为第一层，根的孩子为第二层，根的孩子的孩子为第三层以此类推。

树的高度/深度

树中结点的最大层次。例如图中的树共有四层，所以高度为4。

例子

比如下面这幅图，A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点，也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点，比如图中的 G、H、I、J、K、L 都是叶子节点。