非递归算法实现对二叉树的先序遍历,使用c++实现并给出代码
时间: 2024-05-13 14:21:08 浏览: 10
以下是使用C语言实现非递归算法实现二叉树的先序遍历的代码:
```
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left_child;
struct node *right_child;
};
struct node *create_node(int data) {
struct node *new_node = (struct node *) malloc(sizeof(struct node));
new_node->data = data;
new_node->left_child = new_node->right_child = NULL;
return new_node;
}
void preorder_traversal(struct node *root) {
if (root == NULL) {
return;
}
struct node *stack[100];
int top = -1;
stack[++top] = root;
while (top > -1) {
struct node *current_node = stack[top--];
printf("%d ", current_node->data);
if (current_node->right_child != NULL) {
stack[++top] = current_node->right_child;
}
if (current_node->left_child != NULL) {
stack[++top] = current_node->left_child;
}
}
}
int main() {
struct node *root = create_node(1);
root->left_child = create_node(2);
root->right_child = create_node(3);
root->left_child->left_child = create_node(4);
root->left_child->right_child = create_node(5);
root->right_child->left_child = create_node(6);
root->right_child->right_child = create_node(7);
printf("Preorder Traversal: ");
preorder_traversal(root);
return 0;
}
```
在上述代码中,我们使用一个栈来实现非递归遍历二叉树。我们首先将根节点压入栈中,然后进入一个循环,每次取出栈顶节点并输出数据,然后将其右子节点先压入栈,再将其左子节点压入栈,这样保证下一次取出的节点是先左后右的子节点,从而实现前序遍历。