软件设计师备考知识06--树

简介: 呦西,又是一天。 先来盘开胃菜: call by value(值传递)/call by reference(引用传递) 1)往方法内传入int等基本类型变量,得到一个拷贝副本(形参),不影响原变量 2)往方法内传入一个类对象,如StringBuffer...
+关注继续查看

呦西,又是一天。

先来盘开胃菜:

call by value(值传递)/call by reference(引用传递)

1)往方法内传入int等基本类型变量,得到一个拷贝副本(形参),不影响原变量

2)往方法内传入一个类对象,如StringBuffer,拷贝一个副本,此时形参与实参指向同一地址,用形参内方法修改形参内容,实参一起变化

吃了菜再来一棵树歇会(图片来源:二叉树的四种遍历方法笔记

1)树的类型

  1)满二叉树:2^k-1

  2)完全二叉树:除最后一层外,其他层均达到最大个数,深度:[log2n]+1

  3)二叉排序树:左子树节点值小于根节点,右子树节点大于根子树值

  4)平衡二叉树:空树/左子树和右子树的深度之差不超过1,且其左子树和右子树都是平衡二叉树

  5)线索二叉树:加上线索(指向节点前趋、后继的指针)的二叉树

例如:

img_c316801a3b4e66bc7576624e00b3a61e.png

6)最优二叉树(图片来源:哈夫曼树与哈夫曼编码):(哈夫曼树):权值为w1,w2,....wn的n个结点的二叉树中带全路径长度(所有叶子节点带权路径长度之和)最短的树:

构造方法:循环(升序排列,取出最小左左右子树,放入其和至排序中)

带权路径长度:(3+4+5)*3+(1+2)*4=49

img_abc664ae28a5a8b20dc0c0b6f52ed894.png
哈夫曼树
img_1987676c76221a47f236dbf0ad7b61df.png
替换权值

编码:例: C 00   E 010   D 011   B 10   A 11 

2)树的遍历

二叉树:时间复杂度O(n)

  1)先序遍历:先访问根节点,再遍历左子树、右子树

img_b037fc1918c557d4bf7ce3cc0a3a188d.jpe
先序遍历

2)中序遍历:先访问左子树,再遍历根节点、右子树

img_586b39a39a9a8413ed4092c13414ee71.png
中序遍历

3)后序遍历:先访问左子树,再遍历右子树、根节点


img_b8c2a57f4008c71a8cad7b2a4bf12a1f.png
后序遍历

树转二叉树


img_89bbbfc9f858777a3d31729f2395d436.png
树转二叉树

总结:

树的先根遍历(先访问根节点再按照从左到右的顺序遍历子树)与二叉树先序遍历一致

树的后根遍历(先按从左到右的顺序访问每一棵子树再遍历根节点)与二叉树中序遍历一致

森林的先序遍历即从左到右对树进行先根遍历

森林的后序遍历即从左到右对树进行后根遍历

img_a57aeb59e1fc392797443f16021e059d.png
森林转二叉树

3)二叉树的存储结构:

顺序存储结构:用一组连续的存储单元存储二叉树中的结点,缺:空间浪费


img_ae8adc5139fa6767d3c5c799e69e51ec.png
二叉树到改造后的完全二叉树
img_a9cefe3b0f18bfa0a5e1f9d1a3fe206e.png
存储状态

链式存储结构:用链表(二叉/三叉链表)来表示一棵二叉树(双亲表示法、孩子表示法、孩子兄弟表示法)

最后来一个甜点:

风险的优先级根据风险暴露设定

风险暴露又称风险曝光度=错误出现率(风险出现率)X错误造成损失(风险损失)

目录
相关文章
|
12天前
|
安全 Java 程序员
金三银四面试题 -java数据结构(二)
金三银四面试题 -java数据结构(二)
16 0
|
12天前
|
存储 安全 Java
金三银四面试题 -java数据结构(一)
金三银四面试题 -java数据结构
8 0
|
2月前
毛概期末考试要点总结
毛概期末考试要点总结
23 0
|
4月前
|
存储 Linux
还在担心期末挂科吗? 期末必备复习资料-----“树“的概念
还在担心期末挂科吗? 期末必备复习资料-----“树“的概念
54 0
|
8月前
|
存储 SQL 调度
江苏大学 数据库系统原理 考研复试/期末考试 概念题要点整理
江苏大学 数据库系统原理 考研复试/期末考试 概念题要点整理
118 0
江苏大学 数据库系统原理 考研复试/期末考试 概念题要点整理
|
9月前
毕业两年了,又重学了一遍二叉树遍历的三种方式
毕业两年了,又重学了一遍二叉树遍历的三种方式
81 0
毕业两年了,又重学了一遍二叉树遍历的三种方式
|
算法
软考中级软件设计师自我总结知识分享--数据结构(下)
该系列文章全篇文字在10w+,全文都是自己备考中的干货,软考涉及很多计算机基础,数据结构,算法分析,编程思想,开发流程等等,不仅适合参加软考的人学习,也适合扩宽自己知识视野的人去学习,每一篇都将会把重点加粗处理,特别是易错点,考试常考平时也容易记错,请一定仔细看
58 0
|
算法
软考中级软件设计师自我总结知识分享--数据结构(上)
该系列文章全篇文字在10w+,全文都是自己备考中的干货,软考涉及很多计算机基础,数据结构,算法分析,编程思想,开发流程等等,不仅适合参加软考的人学习,也适合扩宽自己知识视野的人去学习,每一篇都将会把重点加粗处理,特别是易错点,考试常考平时也容易记错,请一定仔细看
76 0
|
算法
软考中级软件设计师自我总结知识分享--算法与分析
该系列文章全篇文字在10w+,全文都是自己备考中的干货,软考涉及很多计算机基础,数据结构,算法分析,编程思想,开发流程等等,不仅适合参加软考的人学习,也适合扩宽自己知识视野的人去学习,每一篇都将会把重点加粗处理,特别是易错点,考试常考平时也容易记错,请一定仔细看!
180 0
|
算法
算法竞赛题解:校门外的树
NOIP2005 普及组:校门外的树
131 0
相关实验场景
更多
推荐文章
更多