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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

阿墨呦 2018-09-26 20:31:00 浏览435
展开阅读全文

呦西,又是一天。

先来盘开胃菜:

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错误造成损失(风险损失)

网友评论

登录后评论
0/500
评论
阿墨呦
+ 关注