广东建设人才网站,app制作软件手机版免费下载,装饰画,制作一个公司网页多少钱今天开始二叉树的学习。
关于二叉树的理论基础#xff0c;可以参考#xff1a;
链接: 二叉树理论基础 目录 二叉树的递归遍历写递归的思路二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历 二叉树的迭代遍历二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历 二叉树的统…今天开始二叉树的学习。
关于二叉树的理论基础可以参考
链接: 二叉树理论基础 目录 二叉树的递归遍历写递归的思路二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历 二叉树的迭代遍历二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历 二叉树的统一迭代二叉树的中序遍历二叉树的前序遍历二叉树的后序遍历 总结 二叉树的递归遍历
写递归的思路
每次写递归按照这个步骤来写 确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对。 确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
拿下面三题来练手
二叉树的前序遍历
链接: 二叉树的前序遍历
确定递归函数的参数和返回值 因为要打印出前序遍历节点的数值所以参数里需要传入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 re;traversal(root, res);return res;}
};二叉树的中序遍历
链接: 二叉树的中序遍历 跟前序遍历大差不差更改下位置即可后序遍历也是一样的道理
class Solution {
public:void traversal(TreeNode* cur, vectorint vec) {if (cur nullptr)return;traversal(cur-left, vec); //左vec.push_back(cur-val); //中traversal(cur-right, vec); //右}vectorint inorderTraversal(TreeNode* root) {vectorint res;traversal(root,res);return res;}
};二叉树的后序遍历
链接: 二叉树的后序遍历
class Solution {
public:void traversal(TreeNode* cur, vectorint vec) {if (cur nullptr)return;traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右vec.push_back(cur-val); // 中}vectorint postorderTraversal(TreeNode* root) {vectorint res;traversal(root, res);return res;}
};二叉树的迭代遍历
递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中所以可以使用栈即非递归的方式来没实现二叉树的前中后序遍历。
二叉树的前序遍历
处理将元素放进res数组中访问遍历节点
前序遍历是中左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。
这样的顺序因为这样出栈的时候才是中左右的顺序。 注代码中空结点不入栈
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint res;if (root NULL) return res;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();res.push_back(node-val);if (node-right) st.push(node-right); // 右空结点不入栈if (node-left) st.push(node-left); // 左空结点不入栈}return res;}
};二叉树的中序遍历
此时不是想改一点前序遍历代码顺序就把中序遍历搞出来。
前序遍历的顺序是中左右先访问的元素是中间结点要处理的元素也是中间结点所以刚刚才能写出相对简洁的代码因为要访问的元素和要处理的元素顺序是一致的都是中间结点。
中序遍历是左中右先访问的是二叉树顶部的结点然后一层一层向下访问直到到达树左面的最底部再开始处理结点(也就是在把节点的数值放进res数组中)这就造成了处理顺序和访问顺序是不一致的。
在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问结点栈则用来处理节点上的元素
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针来访问结点访问到最底层st.push(cur); // 将访问的结点放进栈cur cur-left; // 左} else {cur st.top(); // 从栈里弹出的数据就是要处理的数据放进res数组里的数据st.pop();res.push_back(cur-val); // 中cur cur-right; // 右}}return res;}
};二叉树的后序遍历
后序遍历是左右中只需要调整一下前序遍历的代码顺序就变成中右左的遍历顺序然后在反转res数组输出的结果顺序就是左右中了。
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint res;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top();st.pop();res.push_back(node-val);if (node-left) st.push(node-left); // 相对于前序遍历这更改一下入栈顺序 空结点不入栈if (node-right) st.push(node-right); // 空结点不入栈}reverse(res.begin(), res.end()); // 将结果反转之后就是左右中的顺序了return res;}
};
二叉树的统一迭代
将二叉树前后中序遍历的迭代法实现风格统一即前序遍历 改变代码顺序就可以实现中序 和 后序
迭代法实现的前中后序风格也不是那么统一除了前序和后序有关联中序完全就是另一个风格一会用栈遍历一会又用指针来遍历。
在刚刚迭代法遍历的讲解说了使用栈的话无法同时解决访问节点遍历结点和处理结点将元素放进结果数组不一致的情况。
那我们就将访问的结点放入栈中把要处理的结点也放入栈中但是要做标记。
如何标记就是要处理的节点放入栈之后紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
二叉树的中序遍历
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop(); // 将该节点弹出避免重复操作下面再将右中左结点添加到栈中if (node-right) st.push(node-right); // 添加右结点空节点不入栈st.push(node); // 添加中结点st.push(NULL); // 中结点访问过但是还没有处理加入空结点做为标记。if (node-left) st.push(node-left); // 添加左节点空结点不入栈} else { // 只有遇到空结点的时候才将下一个结点放进结果数组st.pop(); // 将结点弹出node st.top(); // 重新取出栈中元素st.pop();res.push_back(node-val); // 加入到结果数组}}return res;}
};二叉树的前序遍历
和中序遍历相比仅仅改变了两行代码的顺序
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左st.push(node); // 中st.push(NULL);} else {st.pop();node st.top();st.pop();res.push_back(node-val);}}return res;}
};二叉树的后序遍历
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();st.push(node); // 中st.push(NULL);if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左} else {st.pop();node st.top();st.pop();res.push_back(node-val);}}return res;}
};总结
使用其中一种方法即可个人认为递归法最容易理解且代码量少。 迭代法太麻烦了光理解就花了我不少时间更别说实现代码了。。。
参考文档 链接: 二叉树的递归遍历 链接: 二叉树的迭代遍历 链接: 二叉树的统一迭代
