数据结构二叉树教学学习教案.pptx

文档介绍：会计学
1
数据结构(shù jù jié ɡòu)二叉树教学
第一页，共151页。
树的类型定义
二叉树的类型定义
二叉树的存储(cún chǔ)结构
二叉树的遍历(biàn lì)
线索(xiàn suǒ)二叉树
树和森林的表示方法
树和森林的遍历
哈夫曼树与哈夫曼编码
第1页/共151页
第二页，共151页。

树的类型定义
第2页/共151页
第三页，共151页。
数据(shùjù)对象 D：
D是具有(jùyǒu)相同特性的数据元素的集合。
若D为空集，则称为空树；
否则:
(1) 在D中存在唯一的称为根的数据元素root,
(2) 当n>1时，其余结点可分为m (m>0)个互
不相交的有限集T1, T2, …, Tm, 其中(qízhōng)每一
棵子集本身又是一棵符合本定义的树，
称为根root的子树。
数据关系 R：
第3页/共151页
第四页，共151页。
基本操作：
查 找 类
插 入 类
删 除 类
第4页/共151页
第五页，共151页。
Root(T) // 求树的根结点(jié diǎn)
查找(chá zhǎo)类：
Value(T, cur_e) // 求当前(dāngqián)结点的元素值
Parent(T, cur_e) // 求当前结点的双亲结点
LeftChild(T, cur_e) // 求当前结点的最左孩子
RightSibling(T, cur_e) // 求当前结点的右兄弟
TreeEmpty(T) // 判定树是否为空树
TreeDepth(T) // 求树的深度
TraverseTree( T, Visit() ) // 遍历
第5页/共151页
第六页，共151页。
InitTree(&T) // 初始化置空树
插入(chā rù)类：
CreateTree(&T, definition)
// 按定义(dìngyì)构造树
Assign(T, cur_e, value)
// 给当前(dāngqián)结点赋值
InsertChild(&T, &p, i, c)
// 将以c为根的树插入为结点p的第i棵子树
第6页/共151页
第七页，共151页。
ClearTree(&T) // 将树清空(qīnɡ kōnɡ)
删除(shānchú)类：
DestroyTree(&T) // 销毁(xiāohuǐ)树的结构
DeleteChild(&T, &p, i)
// 删除结点p的第i棵子树
第7页/共151页
第八页，共151页。
A
B
C
D
E
F
G
H
I
J
M
K
L
A( )
T1
T3
T2
树根(shù ɡēn)
例如(lìrú):
B(E, F(K, L)),
C(G),
D(H, I, J(M))
第8页/共151页
第九页，共151页。
(１) 有确定(quèdìng)的根；
(２) 树根和子树根之间为有向关系。
有向树：
有序树：
子树之间存在确定(quèdìng)的次序关系。
无序(wú xù)树：
子树之间不存在确定的次序关系。
第9页/共151页
第十页，共151页。