于访问，必须找出矩阵 A 中的元素的下标值（i,j）和向

    

    量 sa[k]的下标值 k 之间的对应关系。

    

    树型结构是一类非常重要的非线性结构。树型结构: 分支关系

    

    一对多

    

    层次结构

    

    本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树的概念、术语，二叉树的遍

    

    历算法。树和二叉树的各种存结构以及建立在各种存储结构上的操作及应用等。

    

    1.树的定义

    

    树(tree)是 n(n≧0)个结点的有限集合 t，若 n=0 时称为空树，否则：

    

    1 有且只有一个特殊的称为树的根(Root)结点；

    

    2 若 n＞1 时，其余的结点被分为 (＞0)个互不相交的子集 t1, t2, t3…t，其中每个

    

    子集本身又是一棵树，称其为根的子树。这是树的递归定义，即用树来定义树，而只有一个

    

    结点的树必定仅由根组成，如图所示。

    

    2.树的基本术语

    

    (1) 结点(node)：一个数据元素及其若干指向其子树的分支。

    

    (2) 结点的度(degree) 、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最

    

    大值称为树的度。

    

    图(b)中结点 A 的度是 3 ，结点 b 的度是 2 ，结点的度是 0，树的度是 3

    

    (3)孩子结点、双亲结点、兄弟结点

    

    一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子

    

    结点的双亲结点(parent)或父结点。

    

    如图 b 中结点 b 、c、d 是结点 A 的子结点，而结点 A 是结点 b 、c、d 的父结点；

    

    结点 E 、F 是结点 b 的子结点，结点 b 是结点 E 、F 的父结点。

    

    同一双亲结点的所有子结点互称为兄弟结点。

    

    如图 b 中结点 b 、c、d 是兄弟结点；

    

    结点 E 、F 是兄弟结点。

    

    (4) 层次、堂兄弟结点

    

    规定树中根结点的层次为 1，其余结点的层次等于其双亲结点的层次加 1。

    

    若某结点在第 l(l≧1)层，则其子结点在第 l+1 层。

    

    双亲结点在同一层上的所有结点互称为堂兄弟结点。