本文针对数据结构基础系列(6):树和二叉树第7, 11-15课时
7 二叉树与树、森林之间的转换
11 二叉树遍历非递归算法
12 层次遍历算法
13 二叉树的构造
14 线索二叉树
15 哈夫曼树
【项目1 - 二叉树算法验证】
运行并重复测试教学内容中涉及的算法。改变测试数据进行重复测试的意义在于,可以从更多角度体会算法,以达到逐渐掌握算法的程度。使用你的测试数据,并展示测试结果,观察运行结果,以此来领会算法。
(1)层次遍历算法的验证 [参考链接]
(2)二叉树构造算法的验证 [参考链接]
(3)中序线索化二叉树的算法验证 [参考链接]
(4)哈夫曼编码的算法验证 [参考链接]
【项目2 - 用二叉树求解代数表达式】
用二叉树来表示代数表达式,树的每一个分支节点代表一个运算符,每一个叶子节点代表一个运算数(为简化,只支持二目运算的+、-、*、/,不加括号,运算数也只是一位的数字字符。本项目只考虑输入合乎以上规则的情况)。请设计算法,(1)根据形如“
请利用二叉树算法库。
[参考解答]
纸上谈兵:“知原理”检验题目
[参考解答1] [参考解答2]
0607 设有森林F={T1, T2, T3},如下图所示,请画出所对应的二叉树,再试着还原为森林。
0613 二叉树的构造:已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,请给出该二叉树的树形表示。
0614 线索二叉树:画出下面二叉树的后序线索化树。
0615 哈夫曼树:下表给出的,是某文本档案中的词汇出现的频度。假设文本档案中只有这些词,请给出各个单词的哈夫曼编码,求出平均查找长度。