成都网站的,校园网站建设结论,wordpress分享 赞插件,建筑网课平台哪个好理论基础
满二叉树
满二叉树#xff1a;如果一棵二叉树只有度为0的结点和度为2的结点#xff0c;并且度为0的结点在同一层上#xff0c;则这棵二叉树为满二叉树。
如图所示#xff1a; 这棵二叉树为满二叉树#xff0c;也可以说深度为k#xff0c;有2^k-1个节点的二叉…理论基础
满二叉树
满二叉树如果一棵二叉树只有度为0的结点和度为2的结点并且度为0的结点在同一层上则这棵二叉树为满二叉树。
如图所示 这棵二叉树为满二叉树也可以说深度为k有2^k-1个节点的二叉树。
#完全二叉树
什么是完全二叉树
完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层h从1开始则该层包含 1~ 2^(h-1) 个节点。
大家要自己看完全二叉树的定义很多同学对完全二叉树其实不是真正的懂了。
我来举一个典型的例子如题 相信不少同学最后一个二叉树是不是完全二叉树都中招了。
之前我们刚刚讲过优先级队列其实是一个堆堆就是一棵完全二叉树同时保证父子节点的顺序关系。
#二叉搜索树
前面介绍的树都没有数值的而二叉搜索树是有数值的了二叉搜索树是一个有序树。
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树 #平衡二叉搜索树
平衡二叉搜索树又被称为AVLAdelson-Velsky and Landis树且具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。
如图 最后一棵 不是平衡二叉树因为它的左右两个子树的高度差的绝对值超过了1。
C中map、set、multimapmultiset的底层实现都是平衡二叉搜索树所以map、set的增删操作时间时间复杂度是logn注意我这里没有说unordered_map、unordered_setunordered_map、unordered_set底层实现是哈希表。
所以大家使用自己熟悉的编程语言写算法一定要知道常用的容器底层都是如何实现的最基本的就是map、set等等否则自己写的代码自己对其性能分析都分析不清楚
二叉树的存储方式
二叉树可以链式存储也可以顺序存储。
那么链式存储方式就用指针 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的而链式存储则是通过指针把分布在各个地址的节点串联一起。
链式存储如图 链式存储是大家很熟悉的一种方式那么我们来看看如何顺序存储呢
其实就是用数组来存储二叉树顺序存储的方式如图 用数组来存储二叉树如何遍历的呢
如果父节点的数组下标是 i那么它的左孩子就是 i * 2 1右孩子就是 i * 2 2。
但是用链式表示的二叉树更有利于我们理解所以一般我们都是用链式存储二叉树。
所以大家要了解用数组依然可以表示二叉树。
#二叉树的遍历方式
关于二叉树的遍历方式要知道二叉树遍历的基本方式都有哪些。
一些同学用做了很多二叉树的题目了可能知道前中后序遍历可能知道层序遍历但是却没有框架。
我这里把二叉树的几种遍历方式列出来大家就可以一一串起来了。
二叉树主要有两种遍历方式
深度优先遍历先往深走遇到叶子节点再往回走。广度优先遍历一层一层的去遍历。
这两种遍历是图论中最基本的两种遍历方式后面在介绍图论的时候 还会介绍到。
那么从深度优先遍历和广度优先遍历进一步拓展才有如下遍历方式
深度优先遍历 前序遍历递归法迭代法中序遍历递归法迭代法后序遍历递归法迭代法广度优先遍历 层次遍历迭代法
在深度优先遍历中有三个顺序前中后序遍历 有同学总分不清这三个顺序经常搞混我这里教大家一个技巧。
这里前中后其实指的就是中间节点的遍历顺序只要大家记住 前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序就可以发现中间节点的顺序就是所谓的遍历方式
前序遍历中左右中序遍历左中右后序遍历左右中
大家可以对着如下图看看自己理解的前后中序有没有问题。 最后再说一说二叉树中深度优先和广度优先遍历实现方式我们做二叉树相关题目经常会使用递归的方式来实现深度优先遍历也就是实现前中后序遍历使用递归是比较方便的。
之前我们讲栈与队列的时候就说过栈其实就是递归的一种实现结构也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。
而广度优先遍历的实现一般使用队列来实现这也是队列先进先出的特点所决定的因为需要先进先出的结构才能一层一层的来遍历二叉树。
这里其实我们又了解了栈与队列的一个应用场景了。
具体的实现我们后面都会讲的这里大家先要清楚这些理论基础。
二叉树的定义
刚刚我们说过了二叉树有两种存储方式顺序存储和链式存储顺序存储就是用数组来存这个定义没啥可说的我们来看看链式存储的二叉树节点的定义方式。
C代码如下
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };
大家会发现二叉树的定义 和链表是差不多的相对于链表 二叉树的节点里多了一个指针 有两个指针指向左右孩子。
这里要提醒大家要注意二叉树节点定义的书写方式。
在现场面试的时候 面试官可能要求手写代码所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。
因为我们在刷leetcode的时候节点的定义默认都定义好了真到面试的时候需要自己写节点定义的时候有时候会一脸懵逼
#总结
二叉树是一种基础数据结构在算法面试中都是常客也是众多数据结构的基石。
本篇我们介绍了二叉树的种类、存储方式、遍历方式以及定义比较全面的介绍了二叉树各个方面的重点帮助大家扫一遍
废
二叉树的递归遍历
主要是对递归不成体系没有方法论每次写递归算法 都是靠玄学来写代码代码能不能编过都靠运气。
本篇将介绍前后中序的递归写法一些同学可能会感觉很简单其实不然我们要通过简单题目把方法论确定下来有了方法论后面才能应付复杂的递归。
这里帮助大家确定下来递归算法的三个要素。每次写递归都按照这三要素来写可以保证大家写出正确的递归算法
确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。
确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
好了我们确认了递归的三要素接下来就来练练手
以下以前序遍历为例
确定递归函数的参数和返回值因为要打印出前序遍历节点的数值所以参数里需要传入vector来放节点的数值除了这一点就不需要再处理什么数据了也不需要有返回值所以递归函数返回类型就是void代码如下
void traversal(TreeNode* cur, vectorint vec)
确定终止条件在递归的过程中如何算是递归结束了呢当然是当前遍历的节点是空了那么本层递归就要结束了所以如果当前遍历的这个节点是空就直接return代码如下
if (cur NULL) return;
确定单层递归的逻辑前序遍历是中左右的循序所以在单层递归的逻辑是要先取中节点的数值代码如下
vec.push_back(cur-val); // 中 traversal(cur-left, vec); // 左 traversal(cur-right, vec); // 右
单层递归的逻辑就是按照中左右的顺序来处理的这样二叉树的前序遍历基本就写完了再看一下完整代码
前序遍历
class Solution {
public:void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;vec.push_back(cur-val); // 中traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};那么前序遍历写出来之后中序和后序遍历就不难理解了代码如下
中序遍历
void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec); // 左vec.push_back(cur-val); // 中traversal(cur-right, vec); // 右
}后序遍历
void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右vec.push_back(cur-val); // 中
}二叉树的迭代遍历
#算法公开课
《代码随想录》算法视频公开课 (opens new window)
写出二叉树的非递归遍历很难么前序和后序(opens new window)写出二叉树的非递归遍历很难么中序) (opens new window)相信结合视频在看本篇题解更有助于大家对本题的理解。
看完本篇大家可以使用迭代法再重新解决如下三道leetcode上的题目
144.二叉树的前序遍历(opens new window)94.二叉树的中序遍历(opens new window)145.二叉树的后序遍历(opens new window)
#思路
为什么可以用迭代法非递归的方式来实现二叉树的前后中序遍历呢
我们在栈与队列匹配问题都是栈的强项 (opens new window)中提到了递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。
此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。
#前序遍历迭代法
我们先看一下前序遍历。
前序遍历是中左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。
为什么要先加入 右孩子再加入左孩子呢 因为这样出栈的时候才是中左右的顺序。
动画如下 不难写出如下代码: 注意代码中空节点不入栈
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();result.push_back(node-val);if (node-right) st.push(node-right); // 右空节点不入栈if (node-left) st.push(node-left); // 左空节点不入栈}return result;}
};
此时会发现貌似使用迭代法写出前序遍历并不难确实不难。
此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了
其实还真不行
但接下来再用迭代法写中序遍历的时候会发现套路又不一样了目前的前序遍历的逻辑无法直接应用到中序遍历上。
#中序遍历迭代法
为了解释清楚我说明一下 刚刚在迭代的过程中其实我们有两个操作
处理将元素放进result数组中访问遍历节点
分析一下为什么刚刚写的前序遍历的代码不能和中序遍历通用呢因为前序遍历的顺序是中左右先访问的元素是中间节点要处理的元素也是中间节点所以刚刚才能写出相对简洁的代码因为要访问的元素和要处理的元素顺序是一致的都是中间节点。
那么再看看中序遍历中序遍历是左中右先访问的是二叉树顶部的节点然后一层一层向下访问直到到达树左面的最底部再开始处理节点也就是在把节点的数值放进result数组中这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素。
动画如下 中序遍历可以写出如下代码
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针来访问节点访问到最底层st.push(cur); // 将访问的节点放进栈cur cur-left; // 左} else {cur st.top(); // 从栈里弹出的数据就是要处理的数据放进result数组里的数据st.pop();result.push_back(cur-val); // 中cur cur-right; // 右}}return result;}
};后序遍历迭代法
再来看后序遍历先序遍历是中左右后续遍历是左右中那么我们只需要调整一下先序遍历的代码顺序就变成中右左的遍历顺序然后在反转result数组输出的结果顺序就是左右中了如下图 所以后序遍历只需要前序遍历的代码稍作修改就可以了代码如下
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top();st.pop();result.push_back(node-val);if (node-left) st.push(node-left); // 相对于前序遍历这更改一下入栈顺序 空节点不入栈if (node-right) st.push(node-right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
};总结
此时我们用迭代法写出了二叉树的前后中序遍历大家可以看出前序和中序是完全两种代码风格并不像递归写法那样代码稍做调整就可以实现前后中序。
这是因为前序遍历中访问节点遍历节点和处理节点将元素放进result数组中可以同步处理但是中序就无法做到同步
上面这句话可能一些同学不太理解建议自己亲手用迭代法先写出来前序再试试能不能写出中序就能理解了。
