void inOrderS(TreeNode* root) { stack<TreeNode*> S; TreeNode *p = root; while (p || !S.empty()){ if(p->left){ S.push(p); p = p->left; } else{ cout << S.top()->val; p = S.top()->right; S.pop(); } } }
时间: 2023-07-14 18:13:04 浏览: 47
这是一个二叉树的中序遍历的非递归实现,使用了栈来辅助实现遍历。具体实现步骤如下:
1. 定义一个栈S和一个指针p,初始时p指向树的根节点。
2. 如果p不为空或者栈S不为空,则执行以下循环:
a. 如果p不为空,则将p压入栈S中,并将p移动到它的左子节点。
b. 如果p为空,则弹出栈顶元素,输出其值,并将p移动到弹出元素的右子节点。
3. 如果栈S为空并且p也为空,则遍历结束。
这段代码实现了二叉树的中序遍历,它的时间复杂度为O(n),其中n为二叉树节点数。
相关问题
stack<TreeNode*> s; TreeNode* p=root;
这是一段 C++ 代码,首先创建了一个栈(stack)对象 s,然后将二叉树的根节点指针 root 赋值给指针变量 p。
这段代码可能用于二叉树的遍历,具体而言,可能是深度优先遍历(DFS)中的前序遍历(先遍历当前节点,再遍历左子树和右子树)实现的一部分。在遍历过程中,我们可以使用栈来保存待遍历的节点。对于当前节点 p,先将其值输出(或者进行其他操作),然后将其右子树(如果存在)入栈,再将其左子树(如果存在)入栈。由于栈是后进先出的数据结构,因此每次从栈中取出的节点都会是下一个需要遍历的节点。这样,我们就可以完成整个树的遍历。
vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> s; TreeNode* p = root;
这段代码是用来实现二叉树的前序遍历的。
首先,定义了一个 vector<int> 类型的变量 res,用来存储遍历结果。
接着,定义了一个 stack<TreeNode*> 类型的变量 s,用来存储待遍历的节点。将二叉树的根节点指针 root 赋值给指针变量 p。
接下来,进入循环,判断条件为:p 不为空,或者栈不为空。这个条件的意义是,只要二叉树还没有遍历完,就需要继续遍历。
在循环中,首先判断当前节点 p 是否为空。如果不为空,就将其值加入到 res 中,并将其入栈。然后将指针 p 移动到其左子树。
如果当前节点 p 为空,说明已经遍历完了当前子树。此时需要从栈中取出一个节点,将指针 p 指向其右子树。由于前序遍历的顺序是“根-左-右”,因此要先遍历右子树,再遍历左子树。
最后,当循环结束时,返回遍历结果 res 即可。