设计思想

递归    

1. 定义一个二叉树结点类型的结构体，创建一个二叉树，定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用,依次循环下去，直到ch遇到空时，结束。最后要返回建立的二叉树T。注：此程序按先序递归创建二叉树。
2. 先序遍历规则：当T为非空时，先访问根节点，之后访问左子树，再访问右子树，依次进行下去直到遍历结束。
3. 中序遍历规则：当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去直到遍历结束。
4. 后序遍历规则：当T为非空时，先左指针指向左孩子，然后右指针指向右孩子，最后输出结点处的数据，依次进行下去直到遍历结束。  

非递归  

1. 跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。
2. 然后是中序，先序，后序非递归遍历二叉树。
3. 先序非递归遍历二叉树的思想是：首先建立一个栈，P是遍历指针指向根节点，当栈不空或者p不空时循环，当P不为空的时候，入栈访问根节点，遍历左子树，否则将栈顶元素出栈，然后访问右子树。重复操作，直到栈为空。
4. 中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。
5. 后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。

设计思想

本题中规定的功能涉及的算法有：中缀表达式求值、将中缀表达式转换为后缀表达式、后缀表达式求值。

1. 中缀表达式求值

• 首先定义两个栈，分别用于存取运算符和运算数。
• 然后依次读取表达式的一个字符ch，如果ch是数值，入数值栈

• 如果ch是运算符，把它与符号栈的栈顶元素的优先级比较：

  • 若“<”即优先级低:该运算符进栈，读入下一个字符；
  • 若“>”即优先级高，从运算符栈退出一个运算符，从运算数栈里退出两个运算数进行运算，并将结果入运算数栈。
  • 若“=”即优先级相等(一般用于“（）”的判定):运算符退栈，消去一个括号读入下一个字符;
  • 这时需用到比较运算符优先级的函数：precede(w,ch)
• 重复上述过程，直至整个表达式求值完毕（即符号栈的栈顶元素和当前读入的字符均为”#”），操作数栈的栈顶元素为计算结果。

2. 将中缀表达式转换为后缀表达式

• 从左向右读取表达式，读到运算数把它输出；

• 读到运算符f，则把符号栈的栈顶元素的算符和f进行优先级比较：

  • 若优先级高:该运算符入运算符栈；
  • 若优先级相等:从运算符栈退出一个运算符，不输出;
  • 若优先级低，从运算符栈退出一个运算符，从运算数栈里输出所有比f优先级高的运算符，直至栈顶算符优先级小于f，f入运算符栈。
• 重复以上流程，一直到最终输出后缀表达式为止。