第六章 树和二叉树
第一节 树的类型定义
• 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 的定义。