网站怎么做留言板块,招标网招标信息,延安免费做网站公司,wordpress主题沐风文章目录 1、树结构2、二叉树3、二叉树的遍历4、堆结构#xff08;Heap#xff09;5、堆化6、图 1、树结构
节点、根节点、叶子节点#xff1a; 高度、深度、层三者的示意图#xff1a; 2、二叉树
相比其他树#xff0c;二叉树即每个节点最多两个孩子#xff08;两个分… 文章目录 1、树结构2、二叉树3、二叉树的遍历4、堆结构Heap5、堆化6、图 1、树结构
节点、根节点、叶子节点 高度、深度、层三者的示意图 2、二叉树
相比其他树二叉树即每个节点最多两个孩子两个分支
如下图满二叉树一定是完全二叉树完全二叉树却不一定是满二叉树 补充上面对满二叉树的定义不准确满二叉树还要满足所有的叶子节点在同一层 以上这个虽然满足除了叶子节点每个节点都有两个孩子但不满足所有叶子节点都在同一层因此不是满二叉树。
3、二叉树的遍历
前序遍历即根节点在前前左右中序遍历即根节点在中左中右后序遍历即根节点在后左右后
如下整个树看成三块A、A的左子树、A的右子树在两块子树里继续按中序的左根右遍历结果就是D ⇒ B ⇒ E ⇒ A ⇒ F ⇒ C ⇒ G 同理如果下面还有那就继续分 一句话从根节点入手把整个树看成左、根、右三大块按左根右中序遍历左右每块子树里按子树的根节点继续分成左、根、右三大块每块子树里依旧按照左根右中序遍历 4、堆结构Heap
堆即一种二叉树完全二叉树。前面提到完全二叉树即从上到下、从左到右依次填满的二叉树即可以左上有节点而右下无节点图A、B但
不能同一层左边无节点但右边有节点图C这样不满足从左到右不是完全二叉树不能同一层左边有节点但右边无节点但下一层左边又有节点图D这样不满足从上到下不是完全二叉树 堆有两个特点
首先得是一个完全二叉树其次每个节点 其所有孩子节点 最大堆或 每个节点 其所有孩子节点 最小堆
对最大堆堆顶元素是整个堆的最大值对最小堆堆顶元素是整个堆的最小值 堆的时间复杂度 比如删除一个最小堆的根节点 干掉1以后把右下角的7放上来先保持完全二叉树的结构 再向下比较把7放到该放的位置。这是个最小堆因此先将7和最小的孩子节点2交换 又发现7比孩子节点4和5打因此再把7和最小的孩子节点4交换删除完成 5、堆化
堆化即把一组无序的数加到堆里去。可先把一组数转成完全二叉树再将完全二叉树调整为最大堆或者最小堆。
如下一个数组转为一个完全二叉树其结果是唯一的遍历数组从上到下、从左到右的摆放即0号元素当根节点后面两个1、2号元素当根节点的左右子节点3、4、5、6号元素分别当1、2号元素所在节点的左右子节点 将这个二叉树转为最小堆核心思想是把每个节点和其孩子节点进行对比看每个节点是否满足值小于等于任何它的一个子节点不满足时则把该节点和其最小的孩子节点交换。 因为叶子节点没有子节点所以从倒数第二层开始看9和7两个节点9符合条件均小于其两个子节点7则不符因此7和5交换 交换完成再往上看上一层10 5 也 10 9选更小的5这个节点交换 同理换完后第二层不再满足最小堆需要再交换10 8 也有 10 7选最小的7这个节点进行交换。
6、图
和树的父子关系相比图则类似邻居关系。对于图有一个度的概念degree如下顶点上有两条边与其相连该顶点的度为2 分类 前面提到了顶点的度对于有向图则是
入度指向该顶点的边的数量出度从该顶点出发的边的数量
如下丁节点入度为2出度为0 再说权重图如下求杭州到北京的最短路径
