树的基础知识

树的概念

树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

层次结构

家族树示例：王二麻子的孩子和孙子们

家族树示例：王小草的父母和祖父母

示例：大学组织结构图

树的术语

前面的每个图都是树的示例。树（tree）是一组由边（edge）相连的节点（node），边表示节点间的关系。节点按层（level）组织，层表示节点的层次。最上层的单节点称为根（root）。

树中每个后继层中的节点是前一层中节点的孩子（children）。有孩子的节点称为其孩子的父节点（parent）。如下图所示，节点A是节点B、C、D和E的父节点。因为这些孩子有相同的父节点，所以它们称为兄弟（sibling）。它们也称为节点A的后代（descendant），而节点A是它们的祖先（ancestor）。节点P是节点A的后代，而A是P的祖先。注意，节点P没有孩子。这样的节点称为叶子（leaf）。

不是叶节点的节点--即有孩子的节点--称为内部节点（interior）或非叶节点（nonleaf）。这样的节点也是父节点。

根节点或树根（root）

树定点的节点称之为根节点，也叫树根

节点（Node）

树种的每个元素都称为节点

子树（SubTree）

除根节点外，其他节点也可以分为多个树的集合，叫做子树，上图中F节点和N、O、P节点共同构成一颗子树，节点B的子树。

节点的度

一个节点之间含有的子树的个数，称之为节点的度。上图中D节点的度为3，E节点的度为2，Q、R、S节点的度为0

叶子节点、叶节点、终端节点

度为0的节点叫做叶子节点，也叫叶节点、终端节点。其实就是没有字节点的节点，或者说没有子树的节点。

父节点、双亲节点

兄弟节点

树的度

一棵树中最大节点的度称之为树的度，即树种哪个节点的子节点最多，那么这个节点的度也就是树的度。

节点的层次

从根这一层开始，根算1层，根的子节点算2层，一直到最下面一层

树的高度、深度

树的深度是从根节点开始、自顶向下逐层累加（根节点的高度是1）助记：深度从上到下

树的高度是从叶节点开始、自底向上逐层累加（叶节点的高度是1）助记：高度由下向上

虽然树的高度和深度一样，但是具体到某个节点上，其高度和深度通常是不一样的。

堂兄弟节点

节点的祖先

节点的子孙

森林

由m棵不相交的树组成的集合，叫做森林

二叉树

二叉树中的每个节点最多有两个孩子。它们称为左孩子（left child）和右孩子（right child）

如图 a 所示：节点B、D、F都是左孩子，二节点C、E、G都是右孩子。该二叉树的根有两颗子树。左子树（left subtree）的根是B，而右子树（right subtree）的根是C。

二叉树中的每颗子树还是二叉树。

满二叉树和完全二叉树

满二叉树：高度为h的二叉树中，若其所有的也节点都在h层上且每个非叶节点都有两个孩子，则树称为满的。如图a) 既为一颗满二叉树。

完全二叉树：如果二叉树中出最后一层外的所有层都含有最多的节点，最后一层的节点从左至右填充，则树是完全的。如图b)即为一颗完全二叉树

注：满二叉树中的所有叶节点都在同一层中，且每个非叶节点都有两个孩子。完全二叉树中，到倒数第二层都是满的，且最后一层的叶节点从左至右填充。

平衡二叉树

若二叉树中每个节点有两颗高度完全相等的子树，则树称为完全平衡树（Completely balanced）。

如图a所示的满树是完全平衡树。如果树中的每个节点的子树的高度差不大于1，则树称为高度平衡的，或简称为平衡的。

满树或完全树的高度。

二叉树的遍历二叉树示例表达式树决策树二叉查找树堆一般树示例解析树游戏树