建设银行U盾不自己弹网站了,标点狗logo设计官网,完整网站开发视频教程,创造网站的最简单 软件是哪个前序遍历是一种二叉树的遍历方式#xff0c;其遍历顺序是先访问根节点#xff0c;然后递归地遍历左子树#xff0c;最后递归地遍历右子树。具体来说#xff0c;前序遍历的顺序是根节点-左子树-右子树。
前序遍历到底部为何会返回到顶部是因为在进行递归遍历时其遍历顺序是先访问根节点然后递归地遍历左子树最后递归地遍历右子树。具体来说前序遍历的顺序是根节点-左子树-右子树。
前序遍历到底部为何会返回到顶部是因为在进行递归遍历时每次都会先处理当前节点然后递归地处理它的左子节点和右子节点。当递归到叶子节点时即左右子节点为空时递归调用会返回到上一层继续处理上一层节点的右子节点。这样不断地递归调用直到整个树都被遍历完毕。
这种递归的方式实际上利用了函数调用栈的特性。每次递归调用都会将当前函数的状态保存在栈中包括局部变量、函数参数等信息。当递归调用返回时栈顶的状态会被弹出恢复到上一次调用的状态从而实现了递归的回溯和返回。
总之前序遍历利用递归实现了从树的根节点开始的深度优先遍历遍历到底部并返回到顶部是通过递归调用和函数调用栈来实现的。
函数调用栈Function Call Stack是计算机内存中用于管理函数调用和返回的一种数据结构。它是一种后进先出LIFO的栈结构用于存储函数调用的上下文信息。每当程序调用一个函数时该函数的调用信息包括参数、局部变量、返回地址等都会被压入栈顶形成一个新的栈帧Stack Frame。当函数执行完毕返回时相应的栈帧就会被弹出控制权返回给调用函数。
函数调用栈的主要作用有以下几点
存储函数调用的上下文信息每个栈帧都包含了函数调用所需的所有信息包括参数、局部变量、返回地址等。实现函数的嵌套调用当一个函数内部调用另一个函数时调用信息会被压入栈顶保证了函数调用的嵌套顺序。支持函数的递归调用当一个函数递归地调用自身时每次调用都会创建一个新的栈帧保证了递归调用的正确执行。
-----------
在函数调用 preorderTraversalLeftSubtree(root-left) 中假设 root-left 指向的节点不为空这个函数调用会如何压栈呢
首先当程序执行到这行代码时会将函数调用信息压入函数调用栈。这个函数调用信息包括函数的参数、局部变量和返回地址等。
假设 root-left 指向的节点不为空那么会执行 preorderTraversalLeftSubtree(root-left) 函数。这个函数会继续递归调用 preorderTraversalLeftSubtree 函数传入 root-left 指向的节点作为参数。
这个过程会一直递归下去直到遇到叶子节点即节点的左右子节点均为空。在叶子节点的情况下递归调用会停止函数调用栈不再继续压栈而是开始弹栈。
在弹栈的过程中每个函数调用完成后会将相应的函数调用信息从栈顶弹出控制权返回到调用它的函数。这样依次弹栈直到栈为空整个递归调用过程结束。
因此在这个过程中函数调用栈的压栈和弹栈是通过递归调用的方式来实现的。每次递归调用都会将函数调用信息压入栈顶每次函数调用完成后又会从栈顶弹出相应的函数调用信息。
#include iostream
#include conio.h // 用于 _getch() 函数using namespace std;// 定义二叉树节点结构
struct TreeNode {int value;TreeNode *left;TreeNode *right;TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};// 函数用于前序遍历根节点及其左子树的所有节点
void preorderTraversalLeftSubtree(TreeNode* node) {if (node ! nullptr) {// 访问当前节点cout node-value ;// 递归遍历左子节点preorderTraversalLeftSubtree(node-left);// 递归遍历右子节点但仅在左子树中preorderTraversalLeftSubtree(node-right);}
}
// 主函数
int main() {TreeNode* root new TreeNode(1);root-left new TreeNode(2);root-right new TreeNode(3);root-left-left new TreeNode(4);root-left-right new TreeNode(5);root-right-left new TreeNode(6);root-right-right new TreeNode(7);root-left-left-left new TreeNode(8);// root-left-left-right new TreeNode(9);root-left-right-left new TreeNode(10);// root-left-right-right new TreeNode(11);// 调用前序遍历函数cout 前序遍历结果;cout root-value ; // 手动输出根节点preorderTraversalLeftSubtree(root-left); // 仅前序遍历左子树cout endl 请按任意键继续. . . endl;_getch(); // 等待用户按键return 0;
}
