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

呦西,又是一天。

先来盘开胃菜:

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

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

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

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

1)树的类型

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

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

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

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

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

例如:

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

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

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

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

软件设计师备考知识06--树
哈夫曼树
软件设计师备考知识06--树
替换权值

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

2)树的遍历

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

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

软件设计师备考知识06--树
先序遍历

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

软件设计师备考知识06--树
中序遍历

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


软件设计师备考知识06--树
后序遍历

树转二叉树


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

总结:

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

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

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

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

软件设计师备考知识06--树
森林转二叉树

3)二叉树的存储结构:

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


软件设计师备考知识06--树
二叉树到改造后的完全二叉树
软件设计师备考知识06--树
存储状态

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

最后来一个甜点:

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

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

上一篇:一次 HTTP 请求就需要一次 TCP 连接吗?


下一篇:软件设计师备考知识04