塔里木大学：《数据结构》课程教学课件（PPT讲稿）第六章 树和二叉树

6.1树的类型定义6.2 二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码

6.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林的表示方法 6.7 树和森林的遍历 6.8 哈夫曼树与哈夫曼编码

6.1树的类型定义

6.1 树的类型定义

数据对象D：D是具有相同特性的数据元素的集合数据关系R：若D为空集，则称为空树。否则：(1）在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集Ti,T2，…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根roo的子树

数据对象 D： D是具有相同特性的数据元素的集合。 若D为空集，则称为空树。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1 , T2 , ., Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 数据关系 R：

例如：AcDBJFGHEKLMA( B(E, F(K, L),, C(G), ,(H, I, J(M)树根TiT3T2

A B C D E F G H I J K L M A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) 树根 T1 T2 T3 例如:

基本操作：查找类插入类删除类

基本操作： 查 找 类 插 入 类 删 除 类

查找类：Root(T）//求树的根结点Value(T，cure）//求当前结点的元素值Parent(T,cur e）//求当前结点的双亲结点LeftChild(T，cure）//求当前结点的最左孩子RightSibling(T，cur e）//求当前结点的右兄弟TreeEmpty(T）//判定树是否为空树TreeDepth(T）//求树的深度TraverseTree(T,VisitO）//遍历

Root(T) // 求树的根结点 查找类： Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历

插入类：InitTree（&T）//初始化置空树CreateTree(&T,definition)/按定义构造树Assign(T, cur e, value)//给当前结点赋值InsertChild(&T, &p, i, c)//将以c为根的树插入为结点p的第棵子树U

InitTree(&T) // 初始化置空树 插入类： CreateTree(&T, definition) // 按定义构造树 Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树

删除类：ClearTree(&T）//将树清空DestroyTree(&T）//销毁树的结构DeleteChild(&T, &p, i)//删除结点p的第棵子树U

ClearTree(&T) // 将树清空 删除类： DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树

例如：AcDBJFGHEKLMA( B(E, F(K, L),, C(G), ,(H, I, J(M)树根TiT3T2

A B C D E F G H I J K L M A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) 树根 T1 T2 T3 例如:

树形图表示的例子ABEAKDBHFBEMO行G的oEFRD①HCMLMG工嵌套集合表示法凹入表示法(A(B(E(K,L),F),C(G),D(H(MD),I,J)广义表表示法

树形图表示的例子 A B K E L F H D M J I C G 嵌套集合表示法 A B C D E K L F G H I J M 凹入表示法 （A(B(E(K,L),F),C(G),D(H(M),I,J))) 广义表表示法 A B C D E F G H I J K L M