完成二叉树先序遍历的非递归算法的代码
时间: 2023-12-03 22:03:56 浏览: 40
以下是二叉树先序遍历的非递归算法的代码,使用栈来辅助实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
其中,stack 是用来存储待遍历的节点的栈,res 是用来存储遍历结果的列表。先将根节点入栈,然后不断地从栈中弹出节点并访问它,如果该节点有右子节点,则将右子节点入栈,如果该节点有左子节点,则将左子节点入栈。这样就可以保证先访问左子节点,再访问右子节点,最后访问根节点,从而实现先序遍历。
相关问题
完成二叉树先序遍历的非递归算法
好的,以下是二叉树先序遍历的非递归算法:
1. 新建一个栈,将根节点压入栈中。
2. 当栈不为空时,执行以下操作:
a. 弹出栈顶元素并输出该元素。
b. 如果该元素的右子树不为空,则将右子树压入栈中。
c. 如果该元素的左子树不为空,则将左子树压入栈中。
3. 重复步骤2,直到栈为空。
这个算法的思路是先访问根节点,然后将右子树压入栈中,再将左子树压入栈中,保证左子树先于右子树被访问。由于是非递归算法,需要用栈来模拟递归过程。
先序遍历非递归算法二叉树C语言
先序遍历的非递归算法可以通过使用栈来实现。具体步骤如下:
1. 创建一个栈,并将根节点入栈。
2. 当栈不为空时,执行以下操作:
1. 弹出栈顶节点并输出该节点的值。
2. 如果该节点的右子树非空,则将右子树入栈。
3. 如果该节点的左子树非空,则将左子树入栈。
3. 当栈为空时,遍历结束。
以下是C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
// 定义二叉树结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 定义栈结构体
typedef struct Stack {
TreeNode* data[MAXSIZE];
int top;
} Stack;
// 初始化栈
void initStack(Stack* s) {
s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack* s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack* s) {
return s->top == MAXSIZE - 1;
}
// 入栈
void push(Stack* s, TreeNode* node) {
if (isFull(s)) {
printf("Stack is full!\n");
return;
}
s->data[++(s->top)] = node;
}
// 出栈
TreeNode* pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return NULL;
}
return s->data[(s->top)--];
}
// 先序遍历二叉树(非递归算法)
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
Stack s;
initStack(&s);
push(&s, root);
while (!isEmpty(&s)) {
TreeNode* cur = pop(&s);
printf("%d ", cur->data);
if (cur->right) {
push(&s, cur->right);
}
if (cur->left) {
push(&s, cur->left);
}
}
}
// 创建新节点
TreeNode* createNode(int data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 构建二叉树
TreeNode* buildTree() {
TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
return root;
}
int main() {
TreeNode* root = buildTree();
preOrder(root); // 输出:1 2 4 5 3 6 7
return 0;
}
```