齐林书院

手机浏览器扫描二维码访问

第382章 红杏（第2页）

存储下三角形（包括对角线）中的元素。

设用一维数组（向量）sa[0…n（n+1）2]存

储n阶对称矩阵，如图所示。

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

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

树型结构是一类非常重要的非线性结构。

树型结构:分支关系

一对多

层次结构

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

历算法。

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

1.树的定义

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

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

2若n＞1时，其余的结点被分为m（m＞0）个互不相交的子集t1，t2，t3…tm，其中每个

子集本身又是一棵树，称其为根的子树。

这是树的递归定义，即用树来定义树，而只有一个

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

2.树的基本术语

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

（2）结点的度（degree）、树的度：结点所拥有的子树的棵数称为结点的度。

树中结点度的最

大值称为树的度。

图（b）中结点A的度是3，结点b的度是2，结点m的度是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层。

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