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 哈夫曼树与哈夫曼编码
数据对象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 例如: