【算法学习笔记】二叉树理论基础——关于二叉树的基础知识

二叉树的种类1.满二叉树每一层都是满的2.完全二叉树除了最底层每一层都是满的并且最底层从左到右连续3.二叉搜索树遵循每个子树的左节点一定比右节点小。对于树的结构没有特别要求。搜索的时间复杂度为ologn。4.平衡二叉搜索树在满足二叉搜索树的前提下左右子树的高度差的绝对值不超过1。图1、2是图3不是。map、multimap、set、multiset的底层实现都是平衡二叉搜索树搜索的时间复杂度为ologn。存储方式1.链式存储父节点分别用左右指针指向左子节点和右子节点。2. 线式存储对于每一个节点有一个地址我们可以用数组来储存。地址为i的节点他的左子节点为i*2右子节点为i*2 1。二叉树遍历因为只是理论基础所以没有过于深入的知识0.基础概念1. 前序遍历根 → 左 → 右顺序先访问根节点然后递归遍历左子树最后递归遍历右子树。示例对如下二叉树1/ \2 3/ \4 5前序遍历结果[1, 2, 4, 5, 3]2. 中序遍历左 → 根 → 右顺序先遍历左子树然后访问根节点最后遍历右子树。示例同上树中序遍历结果[4, 2, 5, 1, 3]3. 后序遍历左 → 右 → 根顺序先遍历左子树然后遍历右子树最后访问根节点。示例同上树后序遍历结果[4, 5, 2, 3, 1]4.总结我们可以发现不管哪种遍历方式左节点一定在右节点方式__序遍历方式代表着根节点相对左右节点的位置1.深度优先搜索在一个方向上优先搜索到尽头然后再换其他方向再进行搜索。一般使用栈、者遍历和迭代法。【算法学习笔记】二叉树的前中后序遍历——递归的简单应用-CSDN博客【算法学习笔记】迭代法遍历二叉树——用栈来模拟递归-CSDN博客2.广度优先搜索层序搜索每一层每一层地搜搜完一层再搜下一层【算法学习笔记】二叉树的层序遍历——广度优先搜索在二叉树中的应用-CSDN博客