4. 数据结构里的二叉树

树的基本概念解析

树这一数据结构所呈现出的逻辑形态属于非线性类型，如图所示。

如图所示，这是一棵典型的树结构，它由多个结点（如A、B、C等）构成，整体上是由若干互不重叠的子树组成。例如，由B、E、F、K、L这五个结点构成的部分便是一棵独立的子树。而每棵子树本身同样具备树的结构特征，均由唯一的根结点以及若干互不相交的子树构成。由此可见，树的定义具有递归性质 ，即在定义过程中再次引用了树本身的定义。需要特别说明的是，树中的结点数量可以为零，在这种情况下，该结构被称为一棵空树，属于一种特殊情形。

树的一些基本术语

结点 : A、B、C等均属于结点，结点不仅包含数据元素，同时还包括指向子树的分支。例如，A结点不仅包含数据元素A，同时也具有3个指向子树的指针。
结点的度 : 指某个结点所拥有的子树数量或分支的数量。例如，A结点拥有3棵子树，因此其度为3。
树的度 : 树中所有结点度的最大值即为该树的度。如示例中各结点的最大度为3（A和D），最小为0（F、G.1.3.K、L、M等），因此整棵树的度为3。

叶子结点 : 又称