二叉树的非递归先序遍历c语言代码

非递归先序遍历二叉树的c语言代码如下： 1. 建立一个栈，将根节点入栈
2. 循环，只要栈不为空，就进行以下操作：
a) 取出栈顶元素，访问该节点
b) 如果其右子节点不为空，将右子节点入栈
c) 如果其左子节点不为空，将左子节点入栈
3. 退出循环

相关问题

c语言实现非递归先序遍历二叉树

非递归先序遍历二叉树可以使用栈来实现。具体实现思路如下：

1. 创建一个栈，并将根节点入栈。
2. 当栈不为空时，执行以下操作：
- 弹出栈顶节点，并输出其值。
- 如果该节点有右子树，则将右子树入栈。
- 如果该节点有左子树，则将左子树入栈。
3. 当栈为空时，遍历完成。

以下是示例代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct Stack {
    int top;
    int size;
    TreeNode **data;
} Stack;

Stack *createStack(int size) {
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->top = -1;
    stack->size = size;
    stack->data = (TreeNode **)malloc(size * sizeof(TreeNode *));
    return stack;
}

void push(Stack *stack, TreeNode *node) {
    if (stack->top == stack->size - 1) {
        printf("Stack overflow!\n");
        return;
    }
    stack->data[++stack->top] = node;
}

TreeNode *pop(Stack *stack) {
    if (stack->top == -1) {
        printf("Stack underflow!\n");
        return NULL;
    }
    return stack->data[stack->top--];
}

void preorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    Stack *stack = createStack(100);
    push(stack, root);
    while (stack->top != -1) {
        TreeNode *node = pop(stack);
        printf("%d ", node->val);
        if (node->right != NULL) {
            push(stack, node->right);
        }
        if (node->left != NULL) {
            push(stack, node->left);
        }
    }
    free(stack->data);
    free(stack);
}

int main() {
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;
    preorderTraversal(root);
    free(root->left);
    free(root->right->left);
    free(root->right->right);
    free(root->right);
    free(root);
    return 0;
}

二叉树的非递归遍历c语言

以下是二叉树的非递归遍历的C语言代码实现：

1. 非递归先序遍历

void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        printf("%d ", node->val);
        if (node->right != NULL) {
            stk.push(node->right);
        }
        if (node->left != NULL) {
            stk.push(node->left);
        }
    }
}

2. 非递归中序遍历

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> stk;
    TreeNode* node = root;
    while (node != NULL || !stk.empty()) {
        while (node != NULL) {
            stk.push(node);
            node = node->left;
        }
        node = stk.top();
        stk.pop();
        printf("%d ", node->val);
        node = node->right;
    }
}

3. 非递归后序遍历

void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> stk1, stk2;
    stk1.push(root);
    while (!stk1.empty()) {
        TreeNode* node = stk1.top();
        stk1.pop();
        stk2.push(node);
        if (node->left != NULL) {
            stk1.push(node->left);
        }
        if (node->right != NULL) {
            stk1.push(node->right);
        }
    }
    while (!stk2.empty()) {
        TreeNode* node = stk2.top();
        stk2.pop();
        printf("%d ", node->val);
    }
}

以上是二叉树的非递归遍历的C语言代码实现，其中用到了栈的数据结构，通过栈的先进后出特性实现二叉树的遍历。