树和二叉树第六章讲解.ppt

第六章 树和二叉树; 6.1 树的定义和基本术语;A;ADT Tree { 数据对象D:D是具有相同特性的数据元素的集合. 数据关系R: 若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R={H}, H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在 关系H下无前驱； ; (2)若D-{root}=φ，则存在D-{root}的一个划分D1 D2,…, Dn(m0),对任意j=k(1=j,k=m)有Dj∩ Dk=φ,且对 任意的i(1=i=m),唯一存在数据元素xi ∈Di，有 root, xi∈H; ⑶对应于D-{root}的划分，H-{root, xi,…,root, xn}有唯一的一个划分H1, H2,…, Hn(m0),对任意的j=k(1=j,k=m)有Hj ∩Hk=φ，且对任意i(1=i=m), Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。 ; 基本操作P: InitTree(T); 操作结果：构造空树T DestroyTree(T); 初始条件：树T存在 操作结果：销毁树T;CreatTree(T,definition); 初始条件：definition给出树T的定义 操作结果：按definition树构造树T ClearTree(T) 初始条件：数T存在 操作结果：将树T清为空树 TreeEmpty(T); 初始条件：树T存在 操作结果：若T为空树，则返回TRUE，否则FALSE ;TreeDepth(T); 初始条件：树T存在 操作结果：返回T的深度 Root(T); 初始条件：树T 存在 操作结果：返回T的根 Value(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点 操作结果：返回cur_e的值 ;Assign(T,cur_e,value); 初始条件：树T存在，cur_e是T中某个结点 操作结果：结点cur_e赋值 为value Parent(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空” LeftChild(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空” ;RightSibling(T,cur_e); 初始条件：树T存在，cur_e是T中某个结点 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则 函数值为 “空” InsertChild(T,P,i,c); 初始条件：树T存在，P指向T中某个结点，1=i=P所指结点的度+1,非空树c 与T不相交 操作结果：插入c为T中p指结点第i棵子树 ;DeleteChild(T,P,i); 初始条件：树T存在,p指向T中某个结点，1=i=P指结点的度 操作结果：删除T中P所指结点的第i棵子树 TraverseTree(T,Visit()); 初始条件：树T存在,Visit是对结点操作的应用函数 操作结果：按某种次序树对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败 }ADT Tree ;树的逻辑表示形式 (a)树型结构 (b)嵌套集合 (c)广义表 (d)凹入表(目录表示法) ;;度：结点拥有的子树数称为结点的度 叶子（终端结点）：度为0的结点 非终端结点（分支结点）：度不为0的结点 树的度是树内各结点的度的最大值 结点的子树的根称为该结点的孩子 该结点称为孩子的双亲(parent) 深度：树中结点的最大层次 ;A;有序树：将树中结点的各子树看成从左到右是有次序的（不能互换），称该树为有序树。 无序树：将树中结点的各子树看成从左到右是无次序的（不能互换），称该树为无序树。 森林：是m(m=0)棵互不相交的树的集合; 6.2 二叉树;Φ; InitBiTree(T); 操作结果：构造空二叉树T DestroyBiTree(T); 初始条件：二叉树T存在 操作结果：销毁二叉树T;CreatBiTree(T,definition); 初始条件：definition给出二叉树T的定义 操作结果：按definition树构造二叉树T ClearBiTree(T) 初始条件：二叉树T存在 操作结果：将二叉树T清为空树 BiTreeEmpty(T); 初始条件：二叉树T存在 操作结果：若T为空二叉树，则返回TRUE，否则FALSE ;BiTreeDepth(T); 初始条件：二叉树T存在 操作结果