C语言实现表达式树转中缀表达式算法

问题描述：

设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。二叉树结点定义如下：

typedef struct node
{	char  data[10]；			// 存储操作数或操作符
	struct node *left, *right；
} BTree；

思路：

采用递归的思想，对于当前节点，如果是操作数，则直接输出，如果是操作符，则分别对左右子树进行递归操作，得到左右子树的中缀表达式，然后将左右子树的中缀表达式和当前操作符组合成一个完整的中缀表达式输出。

代码：

void inorder(BTree *root)
{
    if(root == NULL) return;
    if(root->left != NULL || root->right != NULL) printf("(");
    inorder(root->left);
    printf("%s", root->data);
    inorder(root->right);
    if(root->left != NULL || root->right != NULL) printf(")");
}

时间复杂度分析：

对于每个节点，都需要进行递归操作，时间复杂度为 O(n)，其中 n 为节点个数。

空间复杂度分析：

递归过程中需要使用栈来保存递归的状态，空间复杂度为 O(h)，其中 h 为二叉树的高度。最坏情况下二叉树退化为单链表，空间复杂度为 O(n)。