题目（好像以前没加）
二叉树与哈希表
作业
1.二叉树前序遍历结果
二叉树结构为
代码实现中序+后序推理前序表达式
#include <iostream> #include <stack> #include <string> #include <vector> #include <deque> // BDCEAFHG std::deque<char> mid_order = {'B','D','C','E','A','F','H','G'}; // DECBHGFA std::deque<char> back_order = {'D','E','C','B','H','G','F','A'}; std::string mid = "BDCEAFHG"; std::string back = "DECBHGFA"; void get_res(std::string mid, std::string back) { if(mid.empty()) { return; } char root = back.back(); std::cout <<root; int root_index = mid.find(root),length = mid.length(); // mid , left is 0-ind, right is ind-end // back, left is 0-ind, right is ind-end-1 // left sub tree get_res(mid.substr(0,root_index),back.substr(0,root_index)); // right subtree // get_res(mid.substr(root_index+1,length-1),back.substr(root_index,length-1)); get_res(mid.substr(root_index+1,length-1),back.substr(root_index,length-root_index-1)); } int main() { get_res(mid,back); return 0; }运行结果
ABCDEFGH（符合推导的二叉树结构）
2.将多叉树转二叉树
3.线性哈希表
H(k)=INT(k/13),序列为（08, 14,23,30,68,92,42,55,76,10）
目录
| 序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Key | 08 | 14 | 23 | 30 | 42 | 68 | 55 | 92 | 76 | 10 | |||
| 冲突 | 0 | 0 | 1 | 1 | 1 | 0 | 2 | 0 | 3 | 9 |
平均查找次数=(1*4+2*3+3*1+4*1+10*1)/10=2.7
重要概念回顾
1.前序
前是指的“更新（更子节点）”的方向，对于数组而言，i的前序位置指的i+1
2.前序与后序
前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据
3.后序+中序求前序思路
后序得到根节点，将中序的输出分为左右子树，再在后序的子树找根节点。依次循环
4.线性哈希表
按照key的顺序依次带入哈希函数，得到序号值，看看是否在该序号下已有其他key，若有，就让key值+1（记得取模，毕竟长度有限），直到序号下没有key为止