数据结构课件CD 第06章　树和二叉树.ppt

《数据结构课件CD 第06章　树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章　树和二叉树数据结构主讲教师：周时阳本章主要介绍串，它属于线性结构，是数据元素的内部结构确定为符号的特殊线性表。讨论串的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析。重点研究串的概念、基本运算、顺序结构和链式存储结构及其主要运算的实现算法及其效率分析。内容摘要2重点讲解6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5树与等价问题6.6哈夫曼树及其应用小结36.1.1树的逻辑结构定义及术语树(Tree)是n(n≥0)个结点的有限集T，并且当n＞0时满足下列条件

2、：（1）有且仅有一个特定的称为根(Root)的结点；（2）当n＞1时，其余结点可以划分为m(m＞0)个互不相交的有限集T1、T2、…、Tm，每个集Ti(1≤i≤m)均为树，且称为树T的子树(SubTree)。特别地，不含任何结点(即n＝0)的树，称为空树。6.1树的定义和基本术语提示：这是一个递归定义数据逻辑结构＝(D,R)，这里，D=T，R=?树T的根与其子树的根构成“前驱后继”关系！数据元素4举例：T＝｛A，B，C，D，E，F，G，H，I，J，K，L，M｝T_root＝AT1＝｛B，E，F，K，L｝T2＝｛C，G｝T3＝｛D，H，I，J，M｝T

3、1_root＝BT1_1＝｛E，K，L｝T1_2＝｛F｝T1_1_root＝ET1_1_1＝｛K｝T1_1_2＝｛L｝T2_root＝CT2_1＝｛G｝T3_root＝DT3_1＝｛H，M｝T3_2＝｛I｝T3_3＝｛J｝T3_1_root＝HT3_1_1＝｛M｝ABCDEFGHIJMKLT:ABCDEFGHIJMKLT:T1:T2:T3:T1、T2和T1是T的子树！5ABCDEFGHIJMKLT:结点——数据元素。分支——结点指向其子树根结点的关系。结点的度——结点的分支数。树的度——树中结点的度的最大数。叶子(或终端结点)——度为0的结点。非叶

4、子(或非终端结点或分支结点)——度为非0的结点。6ABCDEFGHIJMKLT:结点与其子树的根，分别称为双亲和孩子。同一双亲的孩子之间互称兄弟。兄弟的孩子相对于其双亲称为子孙。树根称为树中结点的祖先。结点层次——⑴树根的层次为1，⑵假设结点层次为i，其孩子的层次为i+1。树的深度(或高度)——树中结点的最大层数。7如果树中每个结点的子树从左至右认为是有序的，则称该树为有序树，否则称为无序树。度数为n有序树称为n叉树，度数为n的无序树称为n元树。m(m≥0)棵互不相交的树的集合称为森林。ABCDEFGT1:ABCDFEGT2:树T1和树T2是同一棵

5、树吗？T1＝T2?86.1.2树的基本运算（1）创建树IntTree(&T)创建1个空树T。（2）销毁树DestroyTree(&T)（3）构造树CreatTree(&T，deinition)（4）置空树ClearTree(&T)将树T置为空树。（5）判空树TreeEmpty(T)（6）求树的深度TreeDepth(T)（7）获得树根Root(T)（8）获取结点Value(T，cur_e，&e)将树中结点cur_e存入e单元中。9（9）数据赋值Assign(T，cur_e，value)将结点value，赋值于树T的结点cur_e中。（10）获得双亲

6、Parent(T，cur_e)返回树T中结点cur_e的双亲结点。（11）获得最左孩子LeftChild(T，cur_e)返回树T中结点cur_e的最左孩子。（12）获得右兄弟RightSibling(T，cur_e)返回树T中结点cur_e的右兄弟。（13）插入子树InsertChild(&T，&p，i，c)将树c插入到树T中p指向结点的第i个子树之前。（14）删除子树DeleteChild(&T，&p，i)删除树T中p指向结点的第i个子树。（15）遍历树TraverseTree(T，visit())106.2.1二叉树的定义6.2二叉树每个结点

7、之多有两棵子树的有序树，称为二叉树。二叉树中任何结点的第1个子树称为其左子树，左子树的根称为该结点的左孩子；二叉树中任何结点的第2个子树称为其右子树，左子树的根称为该结点的右孩子。二叉树的基本形态11（1）创建二叉树IntBiTree(&T)创建1个空二叉树T。（2）销毁二叉树DestroyBiTree(&T)（3）构造二叉树CreatBiTree(&T，definition)（4）置空二叉树ClearBiTree(&T)将二叉树T置为空二叉树。（5）判空二叉树BiTreeEmpty(T)（6）求二叉树的深度BiTreeDepth(T)（7）获得二

8、叉树根Root(T)（8）获取结点Value(T，cur_e，&e)将二叉树中结点cur_e存入e单元中。基本运算12（9