C语言树的前序遍历递归算法和非递归算法，中序的递归和非递归算法

### C语言中树的前序和中序遍历

#### 1. 前序遍历

##### 递归实现
在递归方式下，前序遍历遵循根节点 -> 左子树 -> 右子树的原则。

void preOrderRecursive(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrderRecursive(root->left);
        preOrderRecursive(root->right);
    }
}

此方法通过函数调用栈来隐式管理访问顺序[^2]。

##### 非递归实现
对于非递归版本，则需显式利用栈结构模拟这一过程：

void preOrderNonRecursive(TreeNode *T){
    TreeNode *stack[100];
    int top = -1;
    TreeNode *p = T;

    while(p || top != -1){
        while(p){
            printf("%d\t", p->data); // 访问当前结点
            stack[++top] = p;       // 当前结点入栈
            p = p->lChild;          // 移动到左孩子
        }

        if(top != -1){
            p = stack[top--];      // 出栈并回溯至上层父节点
            p = p->rChild;         // 转向右子树继续处理
        }
    }
}

这段代码展示了如何手动控制程序流以达到相同效果[^4]。

#### 2. 中序遍历

##### 递归实现
按照左子树 -> 根节点 -> 右子树的方式进行遍历。

void inOrderRecursive(TreeNode *root) {
    if (root != NULL) {
        inOrderRecursive(root->left);
        printf("%d ", root->data);
        inOrderRecursive(root->right);
    }
}

这是最直观的方法之一，易于理解和编写[^3]。

##### 非递归实现
采用栈辅助完成迭代式的中序遍历如下所示：

void inOrderNonRecursive(TreeNode *T){
    TreeNode *stack[15];
    int top = -1;
    TreeNode *p = T;

    while(p != NULL || top != -1){
        if(p != NULL){
            stack[++top] = p;
            p = p->lChild;
        } else {
            p = stack[top--];
            printf("%d\t", p->data);
            p = p->rChild;
        }
    }
}

这里的关键在于正确地交替执行压栈操作与打印节点值的操作序列[^1]。