Page 107 - 高中 信息技术 选择性必修1 数据与数据结构

 4.3 用抽象数据类型表示二叉树

在第一章图1-10和本章图4-6中，数据元素之间是一对多的关系，属于非线性关系。
现实中，除了一对多的关系外，还有多对多的关系，例如第一章图1-11城市间的交通关系
图，以及地图上不同地点之间的道路连接，都属于多对多的关系。具有一对多或多对多特

点的数据结构称为非线性结构。
1．树
树是n（n≥0）个结点的有限集。在任意一棵非空树中：①有且仅有一个特定的称为
根的结点；②当n>1时，其余结点分为m（m>0）棵互不相交的有限子树，每棵子树又是一

棵树。
如图4-7所示，树T由根结点A及两棵子树T1、T2组成。同样，T1中，B是根结点，其

下又可以细分出三棵子树（D、EHI及F）；T2中，C是根结点，其下又可以细分出1棵子树
广东教育出版社
（GJ）。

图4-7 树的结构

2．树的基本概念

（1）结点的度。
每个结点具有的子树数称作结点的度。例如图4-7（a）树T中， B结点的度为3，I结点
的度为0。
（2）分支结点和叶子结点。

在一棵树中，度等于0的结点称作叶子结点。度大于0的结点称为分支结点或非终端结
点。树T中，D、H、I、F、J为叶子结点，A、B、C、E、G为分支结点。
（3）孩子结点、双亲结点、兄弟结点。

在一棵树中，每个结点的子树的根，称为该结点的孩子结点，相应地，该结点被称为
孩子结点的双亲、父亲或父母。具有同一双亲的孩子互称兄弟。在图4-7（a）树T中，结
点B是结点A的孩子结点，结点A是结点B的双亲结点，结点B和C互为兄弟。

（4）树的深度。
从树根开始，根结点为第一层，它的孩子结点为第二层，如此类推。树中所有结点的
最大层数称为树的深度。图4-7（a）树T的深度为4。

99 99

21X2204.indd 99 2019/9/26 13:53:26