数据结构实践项目——树和二叉树(2)

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构实践项目——树和二叉树(2)

贺利坚 2015-11-01 16:19:00 浏览1120
展开阅读全文

本文针对数据结构基础系列(6):树和二叉树第7, 11-15课时

7 二叉树与树、森林之间的转换
11 二叉树遍历非递归算法
12 层次遍历算法
13 二叉树的构造
14 线索二叉树
15 哈夫曼树

【项目1 - 二叉树算法验证】

  运行并重复测试教学内容中涉及的算法。改变测试数据进行重复测试的意义在于,可以从更多角度体会算法,以达到逐渐掌握算法的程度。使用你的测试数据,并展示测试结果,观察运行结果,以此来领会算法。
(1)层次遍历算法的验证 [参考链接]
(2)二叉树构造算法的验证 [参考链接]
(3)中序线索化二叉树的算法验证 [参考链接]
(4)哈夫曼编码的算法验证 [参考链接]

【项目2 - 用二叉树求解代数表达式】

  用二叉树来表示代数表达式,树的每一个分支节点代表一个运算符,每一个叶子节点代表一个运算数(为简化,只支持二目运算的+、-、*、/,不加括号,运算数也只是一位的数字字符。本项目只考虑输入合乎以上规则的情况)。请设计算法,(1)根据形如“1+234/5”的字符串代表的表达式,构造出对应的二叉树(如图),用后序遍历的思路计算表达式的值时,能体现出先乘除后加减的规则;(2)对构造出的二叉树,计算出表达式的值。
  这里写图片描述
  请利用二叉树算法库
[参考解答]

纸上谈兵:“知原理”检验题目

[参考解答1] [参考解答2]
0607 设有森林F={T1, T2, T3},如下图所示,请画出所对应的二叉树,再试着还原为森林。
这里写图片描述

0613 二叉树的构造:已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,请给出该二叉树的树形表示。

0614 线索二叉树:画出下面二叉树的后序线索化树。
这里写图片描述

0615 哈夫曼树:下表给出的,是某文本档案中的词汇出现的频度。假设文本档案中只有这些词,请给出各个单词的哈夫曼编码,求出平均查找长度。
这里写图片描述

网友评论

登录后评论
0/500
评论
贺利坚
+ 关注