第6章树和二叉树_数据结构VIP免费

第5章树第6章树6.1树的概念及操作6.2二叉树6.2.1二叉树的概念及操作6.2.2二叉树的性质6.2.3二叉树的存储结构6.3二叉树的遍历6.4线索二叉树6.5树和森林6.5.1树的存储结构6.5.2森林、树、二叉树的相互转换6.5.3树和森林的遍历6.6哈夫曼树及其应用6.6.1最优二叉树(哈夫曼树)6.6.2哈夫曼编码*6.7算法设计举例主要内容知识点树和二叉树定义二叉树的性质，存储结构二叉树的遍历及遍历算法的应用**线索二叉树二叉树和树及森林的关系Huffman树与Huffman编码重点难点二叉树的性质及应用二叉树的遍历算法及应用**线索二叉树的算法Huffman树的构造方法树的算法树例与特征社会的组织结构家族的族谱计算机中的目录组织描述层次结构，是一种一对多的逻辑关系树的定义树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。（注：有人定义树不能为空）有且仅有一个称为根的结点（Root）；n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树(SubTree)FGIJABCEDH树的定义树的递归定义的各子树T1,T2,…,Tm的相对次序是重要的，即树是有序的。树定义(图示)ACBGFEHIJDMKLAT1T2T3树的抽象数据类型的定义ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下定义的二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root},则存在D-{root}的一个划分D1，D2,…,Dm（m>0）,对任意jk(1j,km)有DjDk=,且对任意的i(1im),存在唯一数据元素xiDi,H;（3）对应于D-{root}的划分，H-{,…}有唯一的一个划分H1,H2,…,Hm(m>0),对任意jk(1j,km)有HjHk=,且对任意i(1im)，Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为根root的子树。（转下页）Tree();~Tree();BuildRoot(constT&value);//建立树的根结点positionFirstChild(positionp);//返回p第一个子女地址,无子女返回0positionNextSibling(positionp);//返回p下一兄弟地址,若无下一兄弟返回0positionParent(positionp);//返回p双亲结点地址,若p为根返回0TgetData(positionp);//返回结点p中存放的值boolInsertChild(positionp,T&value);//在结点p下插入值为value的新子女,若插//入失败,函数返回false,否则返回true树的抽象数据类型(续)boolDeleteChild(positionp,inti);//删除结点p的第i个子女及其全部子孙结//点,若删除失败,则返回false,否则返回truevoidDeleteSubTree(positiont);//删除以t为根结点的子树boolIsEmpty();//判树空否,若空则返回true,否则返回falsevoidTraversal(void(*visit)(positionp));//遍历以p为根的子树}ADTTree树的抽象数据类型(续)树的其它表示方式凹入表示嵌套集合广义表A(B(E,F),C,D(G(J),H,I))AEFBIJGHCDABEFCDGJHIFGIJABCEDH结点：一个数据元素及若干指向其子树的分支；结点的度：结点拥有的子树的数目。树的度：树内各结点的度的最大值；叶子（终端结点）：度为0的结点；分支结点（非终端结点）：度不为0的结点；除根结点外，也称内部结点；孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；其父结点是兄弟的结点互称堂兄。树的概念概念祖先：从根结点到该结点所经分支上的所有结点。子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。层次：结点在树结构中的层（一般定义根为1层）。深度：树中结点的最大层次称为树的深度。有序树：结点的子树在树中的位置固定，不能互换，称有序树。无序树：子树在树中的位置可以互换。树的度：结点度的最大值森林：m(m≥0)棵互不相交的树的集合。概念示例结点结点的度(Degree)叶子（Leaf)或终端结点分支结点或非终端结点树的度层次(Level)树的深度(Depth)孩子（child)双亲（Parent)兄弟(Sibling)祖先子孙ACBGFEHIJDMKL树的示例...