C语言用非递归算法中序遍历二叉树，输出其中序序列，写出完整代码

假设二叉树的结构体定义如下：

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

非递归中序遍历二叉树的基本思路是使用栈来模拟递归过程，这里给出完整代码实现：

void inorderTraversal(TreeNode* root) {
    if (root == NULL)
        return;

    TreeNode* stack[1000];
    int top = -1;
    TreeNode* p = root;

    while (p != NULL || top != -1) {
        // 将当前节点的左子树全部压入栈中
        while (p != NULL) {
            stack[++top] = p;
            p = p->left;
        }

        // 弹出栈顶元素并输出
        p = stack[top--];
        printf("%d ", p->val);

        // 移动到右子树
        p = p->right;
    }
}

在主函数中调用该函数即可输出二叉树的中序序列。

相关问题

用c语言来表示 1、输入字符序列，建立二叉树。 2、中序遍历二叉树：递归算法。 3、中序遍历二叉树：非递归算法。 4、综合训练：为N个权值设计哈夫曼编码。

1. 在C语言中，我们可以使用结构体来表示二叉树节点，每个节点包含一个字符和两个指向左右孩子的指针。创建二叉树通常从用户输入开始，例如：

typedef struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

void insertCharacter(TreeNode** root, char ch) {
    if (*root == NULL) {
        *root = (TreeNode*)malloc(sizeof(TreeNode));
        (*root)->data = ch;
        (*root)->left = (*root)->right = NULL;
    } else if (ch < (*root)->data) {
        insertCharacter(&(*root)->left, ch);
    } else {
        insertCharacter(&(*root)->right, ch);
    }
}

2. 中序遍历二叉树的递归算法通常是这样的：

void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%c", root->data); // 输出左子树后，访问当前节点
        inorderTraversal(root->right);
    }
}

3. 非递归版本的中序遍历可以借助栈来实现：

void inorderTraversalNonRecursive(TreeNode* root, char* result, int* index) {
    stack<TreeNode*> s;
    TreeNode* curr = root;
    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        result[*index++] = curr->data; // 将节点数据存入数组
        curr = curr->right;
    }
}

4. 对于给定N个权值设计哈夫曼编码，首先需要构建哈夫曼树，然后分配编码。这是一个复杂的过程，可以用优先队列（如最小堆）辅助。以下是创建和合并节点的基本步骤：

typedef struct Node {
    char ch;
    int freq;
    struct Node* left, *right;
} Node;

Node* createHuffmanCode(int freq[], int n) {
    // ... 建立频率优先级队列并合并节点 ...
}

// 创建编码函数
void buildHuffmanCode(Node* root, char* codes, int* codeLength, int i) {
    // ... 根据节点顺序生成二进制码 ...
}

使用C语言解决以下问题（1） 输入字符序列，建立二叉链表。 （2） 中序遍历二叉树:递归算法。 （3）中序遍历二叉树:非递归算法。 （4）求二叉树的高度 要求是完整代码并且有主函数，需要有输出例子和输入例子。

好的，我来回答你的问题。以下是使用C语言解决你提出的问题的完整代码：

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

// 定义二叉树结点
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 建立二叉链表
TreeNode* createBinaryTree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {  // 如果输入的是 #，则返回 NULL
        return NULL;
    }
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = ch;
    node->left = createBinaryTree();  // 递归建立左子树
    node->right = createBinaryTree();  // 递归建立右子树
    return node;
}

// 中序遍历二叉树：递归算法
void inorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%c ", root->data);
    inorderTraversal(root->right);
}

// 中序遍历二叉树：非递归算法
void inorderTraversalWithoutRecursion(TreeNode *root) {
    TreeNode *stack[100];
    int top = -1;
    TreeNode *p = root;
    while (p != NULL || top != -1) {
        if (p != NULL) {
            stack[++top] = p;
            p = p->left;
        } else {
            p = stack[top--];
            printf("%c ", p->data);
            p = p->right;
        }
    }
}

// 求二叉树的高度
int getHeight(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int main() {
    printf("请输入二叉树的字符序列（用 # 表示空结点）：\n");
    TreeNode *root = createBinaryTree();

    printf("中序遍历二叉树（递归算法）：\n");
    inorderTraversal(root);
    printf("\n");

    printf("中序遍历二叉树（非递归算法）：\n");
    inorderTraversalWithoutRecursion(root);
    printf("\n");

    printf("二叉树的高度为：%d\n", getHeight(root));

    return 0;
}

输入例子：

AB#D##C##

输出例子：

请输入二叉树的字符序列（用 # 表示空结点）：
中序遍历二叉树（递归算法）：
A B D C 
中序遍历二叉树（非递归算法）：
A B D C 
二叉树的高度为：3

注意：在输入字符序列时，每个字符之间需要用空格隔开。例如，上面的输入例子应该输入为 `A B # D # # C # #`，而不是 `AB#D##C##`。