【408DS算法题】035进阶-17年真题_二叉树转中缀表达式

本文主要是介绍【408DS算法题】035进阶-17年真题_二叉树转中缀表达式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

真题题目

请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。
例如， 当下列两棵表达式树作为算法的输入时， 输出的等价中缀表达式分别为(a+b)*(c*(-d))和(a*b)+(-(c-d))。

二叉树结点定义如下：

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

要求：
1 - 给出算法的基本设计思想。
2 - 根据设计思想，采用C或 C++语言描述算法，关键之处给出注释。

---

（本文重点关注算法实现及思路分析，不含具体答题表述）

分析实现

对于中缀表达式，与之对应的遍历方式为中序遍历。中序遍历得到的操作数/符序列与中缀表达式中的序列是相对应的，而本题中除了结点中的操作数/符，还需要额外再考虑括号——“通过括号反映操作符的计算次序”。

从示例中可知，本题中的括号满足以下两点：
1 - 根节点对应运算两侧不加括号；
2 - 其余每个操作符对应结点（即非根非叶结点）的运算两侧需要加括号。

根据以上规则，具体实现如下：

// 二叉树转中缀表达式辅助函数
void tree2ExpUtil(BTree *cur, int depth){if(cur==NULL)return;// 特殊处理叶结点if(cur->left==NULL && cur->right==NULL){cout<<cur->data;return;}// 1.处理左子树if(depth>1)cout<<"(";tree2ExpUtil(cur->left, depth+1);// 2.处理当前结点cout<<cur->data;// 3.处理右子树tree2ExpUtil(cur->right, depth+1);if(depth>1)cout<<")";
}// 二叉树转中缀表达式
void tree2Exp(BTree *root){tree2ExpUtil(root, 1);
}

---

总结

以上就是通过中序遍历完成二叉树转中缀表达式的实现。

本题重点在于中序遍历，在此基础上，又通过传递当前深度，来判断运算操作是否对应根节点。

这篇关于【408DS算法题】035进阶-17年真题_二叉树转中缀表达式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---