第六章 树和二叉树
第一节 树的类型定义
• A 为“根”
• T1、T2 和 T3 都是一棵树，称为 A 的子树。
• 称根和子树根之间的连线为“分支”
• 结点分支的个数定义为“结点的度”，如结点 B 的度为 2，D 的度为 3。
• 树中所有结点度的最大值定义为“树的度”。
• 称度为零的结点为“叶子”
或“终端结点”
• 所有度不为零的结点
被称作"分支结点"
基本定义
• 森林为 m(m≥0) 棵互不相交的树的集合。
• 树的深度定义为树中叶子结点所在最大层次数。
• 称根结点为子树根的"双亲"。
• 称子树根为根结点的"孩子“
• 根的所有子树根互为“兄弟”。
• 有序树、无序树 如果树中
每棵子树从左向右的排列拥有
一定的顺序，不得互换，则称
为有序树，否则称为无序树。
树的抽象数据类型：
• ADT Tree {
数据对象：D 是具有相同特性的数据元素的集合。
数据关系：
若 D 为空集，则称为空树；
若 D 中仅含一个数据元素，则关系 R 为空集；
否则 R={H}，
(1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱；
(2) 当 n>1 时，其余数据元素可分为 m(m>0) 个互不相交的(非空)有限集 T1,T2,…,Tm, 其
中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根
root 的后继，即 <root,xi> H,i=1,2,…,m。
• 基本操作：
{结构初始化}
InitTree(&T);
操作结果：构造空树 T。
CreateTree(&T,definition);
初始条件：definition 给出树 T 的定义。
