数据结构树和二叉树

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

1、第6章树陈守孔孟佳娜陈卓第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算法设计举例2主要内容知识点树和二叉树定义二叉树的性质，存储结构二叉树的遍历及遍历算法的应用**线索二叉树二叉树和树及森林的关系Huffman树与Huffman编码重点难点二叉树的性质及应用二叉树

2、的遍历算法及应用**线索二叉树的算法Huffman树的构造方法树的算法3树例与特征社会的组织结构家族的族谱计算机中的目录组织描述层次结构，是一种一对多的逻辑关系4树的定义树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。（注：有人定义树不能为空）有且仅有一个称为根的结点（Root）；n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树(SubTree)FGIJABCEDH5树的定义树的递归定义的各子树T1,T2,…,Tm的相对次序是重要的，即树是有序的。6树定义T1T2T

3、37树的抽象数据类型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-{,

4、…}有唯一的一个划分H1,H2,…,Hm(m>0),对任意jk(1j,km)有HjHk=,且对任意i(1im)，Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为根root的子树。（转下页）8TreeInit(T);TreeChild(T,x,i);Treebuild(T,F);TreeClear(T);Traverse(T);TreeRoot(T);TreeParent(T,x);TreeRightBrother(T,x);TreeLeftBrother(T,x);TreeInsert(T

5、,y,i,x);}ADTTree树的抽象数据类型9树的其它表示方式凹入表示嵌套集合广义表A(B(E,F),C,D(G(J),H,I))AEFBIJGHCDABEFCDGJHIFGIJABCEDH10结点：一个数据元素及若干指向其子树的分支；结点的度：结点拥有的子树的数目。树的度：树内各结点的度的最大值；叶子（终端结点）：度为0的结点；分支结点（非终端结点）：度不为0的结点；除根结点外，也称内部结点；孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；其父结点是兄弟的结点互称堂兄。树的概

6、念11概念祖先：从根结点到该结点所经分支上的所有结点。子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。层次：结点在树结构中的层（一般定义根为1层）。深度：树中结点的最大层次称为树的深度。有序树：结点的子树在树中的位置固定，不能互换，称有序树。无序树：子树在树中的位置可以互换。森林：m(m≥0)棵互不相交的树的集合。12概念示例结点结点的度(Degree)叶子（Leaf)或终端结点分支结点或非终端结点树的度层次(Level)树的深度(Depth)孩子（child)双亲（Parent)兄弟(Sibling)祖先子孙树的示例13二叉树的概

7、念二叉树(BinaryTree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树特征：每个结点最多只有两棵子树子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清左右子树。14二叉树的抽象数据类型ADTBinTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=，则R=，称二叉树为空二叉树；若D，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root},则存在D-{r

8、oot}={D1,Dr},且D1Dr；（3）若D1，则D1中存在唯一的元素x1,H,且存在D1上的关系H1H；若Dr,则Dr中存在唯一的元素x