《数据结构》课程教学资源（PPT课件讲稿）第六章 树与二叉树

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

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)个互 不相交的有限集T1,T2,Tm,其中每一 棵子集本身又是一棵符合本定义的树 称为根roo的子树

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

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

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

查找类 Root(T)∥求树的根结点 Value(T,cure)∥求当前结点的元素值 Parent(T,cure)∥/求当前结点的双亲结点 Leftchild(T,cure)∥求当前结点的最左孩子 Rightsibling(T,cure)∥求当前结点的右兄弟 TreeEmpty(T)∥判定树是否为空树 TreeDepth(T)∥求树的深度 TraverseTree6(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() ) // 遍历

插入类: Intree(&T)∥/初始化置空树 Create Tree(&t, definition) ∥按定义构造树 Assign(t, cur e, value) ∥给当前结点赋值 Insert Child(&t, &p, i, c) ∥将以c为根的树插入为结点p的第课棵子树

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

删除类 ClearTree(&T)∥/将树清空 Destroy Tree(&T)∥0毁树的结构 Delete Child( &T, &p, i ∥删除结点p的第i棵子树

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

例如: A B C E G)(H( A(B(E, F(K,D),C(G),D(,I,J()) 树根 2 T 3

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 例如:

有向树: (1)有确定的根; (2)树根和子树根之间为有向关系。 有序树 子树之间存在确定的次序关系。 无序树 子树之间不存在确定的次序关系

(１) 有确定的根； (２) 树根和子树根之间为有向关系。 有向树： 有序树： 子树之间存在确定的次序关系。 无序树： 子树之间不存在确定的次序关系

对比树型结构和线性结构 的结构特点

对比树型结构和线性结构 的结构特点