DAY9 代码随想录读书笔记——二叉树，满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树，遍历方式，递归算法的三个要素
二叉树的种类（4种：满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树）1．满二叉树如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。
这棵二叉树的深度为k（从1开始计算），有2k-1个节点。2．完全二叉树完全二叉树：除了底层节点可能没填满，其余每层的节点数都达到最大值，并且底层的节点都集中在该层最左边的若干位置。若底层为第h层，则该层包含1～2h-1个节点。一个典型的完全二叉树的例子如下图所示。
注意，最后一棵二叉树不是完全二叉树。3．二叉搜索树前面介绍的二叉树中的节点都没有数值，而二叉搜索树是有数值的。二叉搜索树是一个有序树，满足如下规则：若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值。若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值。它的左、右子树也分别为二叉排序树。
下面这两棵树都是二叉搜索树。
4．平衡二叉搜索树平衡二叉搜索树又称为AVL（Adelson-Velsky and Landis）树，它是一棵空树，或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
最后一棵二叉树不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。C++中map、set、multimap、multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作的时间复杂度是O(logn)，而unordered_map、unordered_set、unordered_map、unordered_map的底层实现是哈希表。在使用自己熟悉的编程语言实现算法时，一定要知道常用的容器底层都是如何实现的，最基本的就是map、set等，否则很难分析自己写的代码的性能。遍历方式二叉树主要有两种遍历方式：（1）深度优先遍历：先往深处遍历，遇到叶子节点时再往回遍历。（2）广度优先遍历：一层一层地遍历。以上是图论中最基本的两种遍历方式，将深度优先遍历和广度优先遍历进一步拓展，有如下遍历方式：深度优先遍历
— 前序遍历（递归法、迭代法）。— 中序遍历（递归法、迭代法）。— 后序遍历（递归法、迭代法）。广度优先遍历
— 层次遍历（迭代法）。在深度优先遍历中，前、中、后指的就是中间节点的遍历顺序，只要记住前序、中序、后序指的是中间节点的位置即可。通过如下中间节点的顺序就可以发现，中间节点的顺序就是所谓的遍历方式：前序遍历：中→左→右。中序遍历：左→中→右。后序遍历：左→右→中。
下面看一下自己理解的前序、中序、后序有没有问题。
下面确定递归算法的三个要素。每次写递归算法时都基于下面的“三部曲”，可以写出正确的递归算法。
（1）确定递归函数的参数和返回值。确定哪些参数在递归过程中需要处理就在递归函数中加上这些参数，并且明确每次递归的返回值是什么，进而确定递归函数的返回类型。（2）确定终止条件。写完递归算法，程序运行的时候经常会遇到栈溢出的错误，原因是没写终止条件或者终止条件写得不对。操作系统也是用一个栈的结构保存每一层递归的信息的，如果递归没有终止，那么操作系统的内存栈必然会溢出。（3）确定单层递归的逻辑。
确定每一层递归需要处理的信息。在这里会重复调用函数本身来实现递归的过程。
下面以前序遍历为例。
（1）确定递归函数的参数和返回值。因为要打印出前序遍历节点的数值，所以参数中需要传入数组（C++中使用vector）来存放节点的数值，除了这一点，就不需要再处理其他数据了，也不需要有返回值，所以递归函数的返回类型就是void，代码如下：
（2）确定终止条件。在递归的过程中，如何确定递归结束了呢？当当前遍历到的节点为空时，说明本层递归就要结束了。如果当前遍历的这个节点为空，则直接返回，代码如下：
（3）确定单层递归的逻辑。前序遍历是中→左→右的顺序，所以单层递归的逻辑就是先取中节点的数值，再处理左子树和右子树，代码如下：
完整代码如下：
TO BE CONTINUTED
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/95640.html
