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