14数据结构之三

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

1、数据结构之二树型结构四、二叉树的遍历二叉树遍历的定义   按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。2.二叉树遍历的顺序   如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、LRD、DLR、DRL、RDL、RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。以下遍历以该树为例前序遍历规则如下：   若二叉树为空，则退出。否则    ⑴访问处理根

2、结点；    ⑵前序遍历左子树；    ⑶前序遍历右子树；如上图的前序遍历结果为abdehicfg中序遍历规则如下：   若二叉树为空，则退出；否则   ⑴中序遍历左子树；   ⑵访问处理根结点；   ⑶中序遍历右子树；如上图的中序遍历结果为dbheiafcg后序遍历规则如下：   若二叉树为空，则退出；否则   ⑴后序遍历左子树；   ⑵后序遍历右子树；   ⑶访问处理根结点；如上图的后序遍历结果为dhiebfgca普通树的遍历先根次序遍历树规则：若树为空，则退出；否则先根访问树的根结点，然后先根遍历根

3、的每棵子树。后根次序遍历树规则：若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。后根遍历次序为whdexafbsmonijtucr先根遍历次序为rawxdhebfcstimonju五、根据两种遍历顺序确定树结构由两种顺序确定树结构遍历二叉树有三种规则：   前序遍历：根—左子树—右子树；   中序遍历：左子树—根—右子树；   后序遍历：左子树—右子树—根；   由于前序遍历的第一个字符和后序遍历的最后一个字符为根，中序遍历中位于根左方的子串和位于根右方的子串分别反映了左子树和右子树的结构，因此二叉树的

4、形态可以由其中序与后序或者前序与中序唯一确定。但无法反映左子树和右子树结构的前序遍历与后序遍历却不能做到这一点，因此这两个遍历顺序可对应多种二叉树的形态。试题1.二叉树T，已知其先根遍历是1243576（数字为结点的编号，以下同），后根遍历是4275631，则该二叉树的可能的中根遍历是（）。A.4217536B.2417536C.4217563D.24157362.已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA，则该二叉树的先序遍历的顺序为什么？六、二叉排序

5、树所谓二叉排序树是指具有下列性质的非空二叉树   ⑴若根结点的左子树不空，则左子树的所有结点值均小于根结点值；   ⑵若根结点的右子树不空，则右子树的所有结点值均不小于根结点值；   ⑶根结的左右树也分别为二叉排序树；   显然，对二叉排序树进行中序遍历，可得出结点值递增的排序序列。例：638192457631425879七、最优二叉树(哈夫曼树)概念在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使

6、（Wk—第k个叶结点的权值；Pk—第k个叶结点的带权路径长度）达到最小。哈夫曼树的应用哈夫曼编码发明Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。编码过程例：编码字符组成a    b    c    d     e     f频度（单位：次）45   13  12  16    9    5efefcefcbefcbdefcbdaefcbda0111110000字符编码a0b110c1110d10e11110f111

7、11每个编码都不是另一个的前缀。试题最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。A)（00，01，10，11）B)（0，1，00，11）C)（0，10，110，111）D)（1，01，000，001）用二叉树来表示表达式对于表达式a+b*c/(d-e)-f*g有如下二叉树：如果按照中序遍历此二叉树，得到的中序序列就是a+b*c/d-e-f*g如果改用先序序列遍历，就将得到-+a/*bc-de*fg而后序遍历将得到

8、abc*de-/+fg*-从表达式来看，以上三个序列恰好为表达式的中缀表示，前缀表示（波兰式）和后缀表示（逆波兰式）。bc*de-/*fga+-试题表达式a*(b+c)-d的后缀表达式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd