北航计算机软件技术基础课程作业笔记【4】

news/2024/12/13 16:19:19/

题目(好像以前没加)

二叉树与哈希表

作业

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.线性哈希表


序号0123456789101112
Key08142330426855927610
冲突0011102039

平均查找次数=(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为止


http://www.ppmy.cn/news/1434593.html

相关文章

Laravel 6 - 第十五章 验证器

​ 文章目录 Laravel 6 - 第一章 简介 Laravel 6 - 第二章 项目搭建 Laravel 6 - 第三章 文件夹结构 Laravel 6 - 第四章 生命周期 Laravel 6 - 第五章 控制反转和依赖注入 Laravel 6 - 第六章 服务容器 Laravel 6 - 第七章 服务提供者 Laravel 6 - 第八章 门面 Laravel 6 - …

webview的使用方法和后退键的处理

WebView是一个能够显示网页内容的控件&#xff0c;通常用于Android或iOS应用程序中嵌入网页。下面我将分别说明WebView在Android和iOS中的使用方法&#xff0c;以及如何处理后退键。 Android中的WebView使用方法 添加WebView到布局文件中 在你的布局XML文件中添加WebView控件…

Linux 的情况下实现贪吃蛇 -- 第二十八天

1.keypad(stdsrc,1) 参数表示是否接收&#xff0c;1表示接收指令 2.思路&#xff1a;初始化initNcurses()&#xff0c; 封装地图函数实现地图gamePic&#xff08;&#xff09; 分三部分实现&#xff1a;2.1: 在第0行&#xff1a;打印 "--"," | "和&q…

【JavaScript编程实操14】DOM实操_回到顶部

前言 本次主要是针对Javascript阶段的DOM实操方面的练习&#xff0c;本次主要实现当页面内容过多时&#xff0c;可以点击按钮&#xff0c;快速回到页面顶部的效果。这次的实现逻辑比较简单&#xff0c;主要是应用函数实现页面的回到顶部功能&#xff0c;this.scrollTo(0, 0)可以…

完美解决多种情况下的 java.lang.NullPointerException 的异常

文章目录 1. 复现错误2. 分析问题3. 解决问题1. 复现错误 在工作中,经常会遇见java.lang.NullPointerException的异常,这种异常千奇百怪,但明确一点的是:它是空指针异常,也称之为NPE异常,如下代码所示: @Setter @Getter @Accessors(chain = true) public class Student…

10.Java集合汇总

文章目录 1. Java集合概述1.1 Java集合框架概述1.2 Collection接口继承树1.3 Map接口继承树 2. Collection接口2.1 Collection接口方法 3 Iterator迭代器接口3.1 Iterator接口的方法3.2 foreach循环 4 List接口4.1 List接口方法4.1 ArrayList4.2 LinkedList4.3 Vector4.4 面试题…

【vim】折叠代码

目录 简介操作创建折叠删除折叠打开或关闭折叠在折叠间移动简介 Vim编辑器中可以使用 foldmethod 选项设置折叠方法。 将 foldmethod 设置为 manual 以外的值时,将删除所有折叠并创建新折叠。切换到 manual 方法不会删除现有的折叠。由此可以先用自动定义折叠,然后手动更改它…

redmibook 14 2020 安装 ubuntu

1. 参考博客 # Ubuntu20.10系统安装 -- 小米redmibook pro14 https://zhuanlan.zhihu.com/p/616543561# ubuntu18.04 wifi 问题 https://blog.csdn.net/u012748494/article/details/105421656/# 笔记本电脑安装了Ubuntu系统设置关盖/合盖不挂起/不睡眠 https://blog.csdn.net/…