题目（好像以前没加）

二叉树与哈希表

作业

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 treeget_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）

目录

二叉树与哈希表

作业

1.二叉树前序遍历结果

2.将多叉树转二叉树

3.线性哈希表

重要概念回顾

1.前序

2.前序与后序

3.后序+中序求前序思路

4.线性哈希表

---

序号	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为止