已知一棵含有n个节点的二叉树,按顺序方式存储,设计用先序遍历二叉树中结点的递归和非递归算法C语言

以下是用C语言实现先序遍历二叉树的递归算法：

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

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

void preorderTraversal(struct TreeNode* root){
    if(root){
        printf("%d ", root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

以下是用C语言实现先序遍历二叉树的非递归算法：

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

#define MAX_SIZE 50

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

void preorderTraversal(struct TreeNode* root){
    struct TreeNode* stack[MAX_SIZE];
    int top = -1;
    if(root){
        stack[++top] = root;
        while(top >= 0){
            struct TreeNode* node = stack[top--];
            printf("%d ", node->val);
            if(node->right){
                stack[++top] = node->right;
            }
            if(node->left){
                stack[++top] = node->left;
            }
        }
    }
}

以上两个算法均可以对二叉树进行先序遍历。其中，递归算法利用了函数调用栈，而非递归算法则利用了栈结构模拟递归过程。