二叉树的先序非递归遍历代码
时间: 2023-09-21 09:09:13 浏览: 47
以下是二叉树先序遍历的非递归实现代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root):
if not root:
return []
stack = []
result = []
node = root
while node or stack:
while node:
result.append(node.val)
stack.append(node)
node = node.left
node = stack.pop()
node = node.right
return result
```
这段代码使用了一个栈来模拟递归的过程。首先将根节点入栈,然后进入循环,如果当前节点存在,则将其值加入结果列表,并将当前节点入栈,然后继续遍历其左子树。如果当前节点为空,则从栈中弹出一个节点,并继续遍历其右子树。重复这个过程直到栈为空。最后返回结果列表即为先序遍历的结果。
相关问题
二叉树的先序非递归遍历算法思想
二叉树的先序非递归遍历算法思想如下:
1. 创建一个空栈,用于存储待访问的节点。
2. 初始化当前节点为根节点。
3. 循环执行以下步骤,直到栈为空:
1. 访问当前节点,并将其值输出或存储。
2. 如果当前节点有右子节点,则将右子节点入栈。
3. 如果当前节点有左子节点,则将左子节点入栈。
4. 弹出栈顶元素作为当前节点,继续循环。
在这个算法中,我们通过栈来模拟递归的过程。先序遍历的顺序是根节点 -> 左子树 -> 右子树,所以我们首先访问根节点,然后将右子节点入栈,再将左子节点入栈。这样,在遍历完左子树之后,我们可以按栈的顺序依次访问右子树的节点。
这种非递归的遍历算法可以保证每个节点都被访问且仅被访问一次,时间复杂度为 O(n),其中 n 是二叉树的节点个数。
试用C语言编写一个二叉树按层遍历和先序非递归遍历函数
二叉树按层遍历函数的代码如下:
```
void levelOrderTraversal(Node* root) {
if (root == NULL)
return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
cout << current->data << " ";
if (current->left != NULL)
q.push(current->left);
if (current->right != NULL)
q.push(current->right);
}
}
```
先序非递归遍历函数的代码如下:
```
void preOrderTraversal(Node* root) {
if (root == NULL)
return;
stack<Node*> s;
s.push(root);
while (!s.empty()) {
Node* current = s.top();
s.pop();
cout << current->data << " ";
if (current->right != NULL)
s.push(current->right);
if (current->left != NULL)
s.push(current->left);
}
}
```
请注意对以上代码进行适当测试,以验证其正确性。