数据结构详细教案——树与二叉树资料

第0页数据结构教案第六章树与二叉树数据结构教案第6章树与二叉树第1页目录6.1树的定义和基本术语.............................................................................................................16.2二叉树.....................................................................................................................................26.2.1二叉树的定义..............................................................................................................26.2.2二叉树的性质..............................................................................................................46.2.3二叉树的存储结构......................................................................................................56.3树和森林.................................................................................................................................66.4二叉树的先|中|后序遍历算法................................................................................................76.5先|后|中序遍历的应用扩展....................................................................................................96.5.1基于先序遍历的二叉树(二叉链)的创建....................................................................96.5.2统计二叉树中叶子结点的数目..................................................................................96.5.3求二叉树的高度........................................................................................................106.5.4释放二叉树的所有结点空间....................................................................................116.5.5删除并释放二叉树中以元素值为x的结点作为根的各子树.................................126.5.6求位于二叉树先序序列中第k个位置的结点的值.................................................126.5.7线索二叉树................................................................................................................136.5.8树和森林的遍历........................................................................................................146.6二叉树的层次遍历...............................................................................................................166.7判断一棵二叉树是否为完全二叉树...................................................................................166.8哈夫曼树及其应用...............................................................................................................186.8.1最优二叉树(哈夫曼树)..............................................................................................186.8.2哈夫曼编码................................................................................................................196.9遍历二叉树的非递归算法...................................................................................................196.9.1先序非递归算法........................................................................................................196.9.2中序非递归算法........................................................................................................206.9.3后序非递归算法........................................................................................................21数据结构教案第6章树与二叉树第1页1第6章二叉树和树6.1树的定义和基本术语1、树的递归定义1）结点数n=0时，是空树2）结点数n0时有且仅有一个根结点、m个互不相交的有限结点集——m棵子树2、基本术语结点：叶子(终端结点)、根、内部结点（非终端结点、分支结点）；树的规模：结点的度、树的度、结点的层次、树的高度(深度)结点间的关系：双亲(1)—孩子(m)，祖先—子孙，兄弟，堂兄弟兄弟间是否存在次序：无序树、有序树去掉根结点非空树森林引入一个根结点3、树的抽象数据类型定义树特有的操作：查找：双亲、最左的孩子、右兄弟结点的度不定，给出这两种操作可以查找到一个结点的全部孩子插入、删除：孩子遍历：存在一对多的关系，给出一种有规律的方法遍历(有且仅访问一次)树中的结点ADTTree{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Ф，则存在D-{root}的一个划分D1,D2,…,Dm(m0)（Di表示构成第i棵子树的结点集），对任意j≠k(1≤j,k≤m)有Dj∩Dk=Ф，且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di,有root,xi∈H（H表示结点之间的父子关系）；(3)对应于D-{root}的划分，H-{root,x1,…,root,xm}有唯一的一个划分H1,H2,…,Hm(m0)（Hi表示第i棵子树中的父子关系），对任意j≠k(1≤j,k≤m)有Hj∩Hk=Ф，且对任意i(1≤i≤m)，Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。基本操作：InitTree(&T)操作结果：构造空树TDestroyTree(&T)初始条件：树T已存在操作结果：销毁树TClearTree(&T)初始条件：树T已存在操作结果：将树T清为空树数据结构教案第6章树与二叉树第2页2TreeEmpty(T)初始条件：树T已存在操作结果：若T为空树，则返回TRUE，否则返回FALSETreeDepth(T)初始条件：树T已存在操作结果：返回树T的深度Root(T)初始条件：树T已存在操作结果：返回T的根Value(T,cur_e)初始条件：树T已存在，cur_e是T中某个结点操作结果：返回cur_e的值Assign(T,&cur_e,value)初始条件：树T已存在，cur_e是T中某个结点操作结果：结点cur_e赋值为valueParent(T,cur_e)初始条件：树T已存在，cur_e是T中某个结点操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”LeftChild(T,cur_e)初始条件：树T已存在，cur_e是T中某个结点操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”RightSibling(T,cur_e)初始条件：树T已存在，cur_e是T中某个结点操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”InsertChild(&T,p,i,c)初始条件：树T已存在，p指向T中某个结点，1≤i≤p所指结点的度+1，非空树c与T不相交操作结果：插入c为T中p所指结点的第i棵子树。DeleteChild(&T,p,i)初始条件：树T已存在,p指向T中某个结点，1≤i≤p所指结点的度操作结果：删除T中p所指结点的第i棵子树。TraverseTree(T,visit())初始条件：树T已存在，visit是对结点操作的应用函数操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败}ADTTree6.2二叉树一般树的度不定，直接考虑其操作比较困难，故首先考虑度为二的树。这里引入二叉树。6.2.1二叉树的定义1、二叉树的特殊性·0≤度≤2·子树有左右之分（子树的个数=1或2时）注意：0≤度≤2的有序树≠二叉树当某个结点只有一棵子树时，不存在序的概念2、二叉树的抽象数据类型定义数据结构教案第6章树与二叉树第3页3二叉树相对树的特殊性：最左的孩子、右兄弟左孩子、右孩子遍历的规律性：L(左子树)、D(根)、R(右子树)的排列上限定为L在R前访问(有对称关系的，只须考虑其中的一种)ADTBinaryTree{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Ф，则存在D-{root}的一个划分DL,DR（左、右子树的结点集），且DL∩DR=Ф；(3)若DL≠Ф，则DL中存在唯一元素xL,有root,xL∈H（H表示结点之间的父子关系），且存在DL上的关系HLH；若DR≠Ф，则DR中存在唯