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

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

时间: 2024-06-24 09:00:22 浏览: 142

二叉树的遍历主要有三种方法：前序遍历、中序遍历和后序遍历，非递归实现通常使用栈来模拟递归的过程。以下是C语言中非递归方式实现二叉树遍历的示例：

前序遍历（根-左-右）： ```c struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };

void preOrder(struct TreeNode* root) { if (root == NULL) return; stack(struct TreeNode*) s; s.push(root); while (!s.is_empty()) { struct TreeNode* node = s.top(); printf("%d ", node->val); // 输出节点值 s.pop(); if (node->right != NULL) s.push(node->right); // 先右子树 if (node->left != NULL) s.push(node->left); // 后左子树 } }


2. **中序遍历（左-根-右）**：
```c
void inOrder(struct TreeNode* root) {
    if (root == NULL) return;
    stack(struct TreeNode*) s;
    struct TreeNode* curr = root;
    while (curr != NULL || !s.is_empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        printf("%d ", curr->val);
        curr = curr->right;
    }
}

后序遍历（左-右-根）：

void postOrder(struct TreeNode* root) {
 if (root == NULL) return;
 stack(struct TreeNode*) s1, s2;
 s1.push(root);
 while (!s1.is_empty()) {
     struct TreeNode* node = s1.top();
     s1.pop();
     s2.push(node);
     if (node->left != NULL) s1.push(node->left);
     if (node->right != NULL) s1.push(node->right);
 }
 while (!s2.is_empty()) {
     struct TreeNode* node = s2.top();
     s2.pop();
     printf("%d ", node->val);
     s2.push(NULL); // 为下一次迭代用，防止栈溢出
 }
}