写一个非递归的先序遍历算法
时间: 2023-11-18 17:07:48 浏览: 27
非递归的先序遍历算法可以使用栈来实现。具体步骤如下:
1. 将根节点入栈
2. 当栈不为空时,取出栈顶元素并访问(即输出)
3. 如果该节点存在右子树,则将其右子树入栈
4. 如果该节点存在左子树,则将其左子树入栈
5. 重复步骤2-4,直到栈为空
下面是一个示例代码:
```python
def preorder(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val) # 访问节点
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
```
其中,`root`为二叉树的根节点,`stack`为存储节点的栈。在每次循环中,取出栈顶元素并访问,然后将其右子树和左子树(如果存在)分别入栈。循环终止条件是栈为空。
相关问题
非递归先序遍历的核心算法
非递归先序遍历的核心算法是使用栈来模拟递归过程。具体步骤如下:
1. 创建一个空栈,并将根节点入栈。
2. 循环执行以下操作,直到栈为空:
a. 从栈中弹出一个节点,访问该节点。
b. 如果该节点存在右子节点,则将右子节点入栈。
c. 如果该节点存在左子节点,则将左子节点入栈。
这样,就可以实现非递归先序遍历。在这个算法中,首先访问根节点,然后遍历左子树,最后遍历右子树。通过使用栈来保存待访问的节点,可以模拟递归的过程,保证正确的遍历顺序。
非递归先序遍历二叉树
非递归先序遍历二叉树的思路是使用栈来模拟递归过程。具体的代码如下所示:
```
public static void preOrderTraverse(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
System.out.println(cur.val);
if (cur.right != null) stack.push(cur.right);
if (cur.left != null) stack.push(cur.left);
}
}
```
首先,我们创建一个栈并将根节点入栈。然后,我们进入一个循环,直到栈为空。在循环中,我们弹出栈顶的节点并打印其值。接着,我们将右子节点入栈,然后将左子节点入栈。因为栈是后进先出的,所以弹出栈顶的节点时,会先打印它的值,然后先压入右子节点,再压入左子节点。这样就实现了先序遍历的顺序。通过这个非递归算法,我们可以按先序遍历的顺序访问二叉树的所有节点。
举个例子来演示算法的执行过程。假设我们有如下二叉树:
```
1
/ \
2 3
/ \ \
4 5 6
```
我们按照非递归先序遍历的算法来遍历这棵树。首先,我们将根节点1入栈。然后,进入循环,弹出栈顶的节点1并打印它的值。接着,我们将右子节点3入栈,再将左子节点2入栈。此时,栈中的节点顺序为:3, 2。接下来,我们再次进入循环,弹出栈顶的节点2并打印它的值。因为节点2没有子节点,所以继续弹出栈顶的节点3并打印它的值。此时,栈中只剩下根节点1了。我们再次进入循环,弹出栈顶的节点1并打印它的值。最后,栈为空,遍历结束。
所以,按照非递归先序遍历的算法,上述二叉树的遍历结果为:1, 2, 4, 5, 3, 6。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [二叉树的非递归遍历算法](https://blog.csdn.net/weixin_47396585/article/details/120824248)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [非递归先序遍历二叉树总结(3种方法)](https://blog.csdn.net/qq_41512783/article/details/110524693)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]