设计思想
递归
- 定义一个二叉树结点类型的结构体,创建一个二叉树,定义一个输入的数是字符型的,当ch为空时,T就为空值,否则的话就分配空间给T,T就指向它的结点,然后左指针域指向左孩子,右指针指向右孩子,若还有,继续调用,依次循环下去,直到ch遇到空时,结束。最后要返回建立的二叉树T。注:此程序按先序递归创建二叉树。
- 先序遍历规则:当T为非空时,先访问根节点,之后访问左子树,再访问右子树,依次进行下去直到遍历结束。
- 中序遍历规则:当T为非空时,先左指针指向左孩子数据,然后输出结点处的数据,再右指针指向右孩子,依次进行下去直到遍历结束。
- 后序遍历规则:当T为非空时,先左指针指向左孩子,然后右指针指向右孩子,最后输出结点处的数据,依次进行下去直到遍历结束。
非递归
- 跟递归遍历二叉树的前提一样,首先应该创建一个二叉树,同样使用先序递归的方式创建二叉树。
- 然后是中序,先序,后序非递归遍历二叉树。
- 先序非递归遍历二叉树的思想是:首先建立一个栈,P是遍历指针指向根节点,当栈不空或者p不空时循环,当P不为空的时候,入栈访问根节点,遍历左子树,否则将栈顶元素出栈,然后访问右子树。重复操作,直到栈为空。
- 中序非递归遍历二叉树的思想是:首先是根节点压栈,当根节点的左子树不是空的时候,左子树压栈。直到左子树为空的时候,不再压栈。将栈顶元素出栈,访问栈顶元素,并将栈顶的右子树进栈。当右子树的左子树不是空的时候,左子树一直进栈,直到左子树为空,则不再进栈。重复上面的操作,直到栈空的时候。
- 后序非递归遍历二叉树的思想:首先是根节点进栈,当根节点的左子树不为空的时候,左子树进栈,直到左为空的时候,左子树不再进栈。指针指向的是右子树,当右子树为空的时候,直接访问根节点。当右子树不为空的时候,则右子树的指针进栈,当右子树的左子树不为空的时候,则左也进栈,直到左为空。重复上面的操作,直到栈为空的时候,则遍历树完成。
设计思想
本题中规定的功能涉及的算法有:中缀表达式求值、将中缀表达式转换为后缀表达式、后缀表达式求值。
1. 中缀表达式求值
- 首先定义两个栈,分别用于存取运算符和运算数。
- 然后依次读取表达式的一个字符ch,如果ch是数值,入数值栈
如果ch是运算符,把它与符号栈的栈顶元素的优先级比较:
- 若“<”即优先级低:该运算符进栈,读入下一个字符;
- 若“>”即优先级高,从运算符栈退出一个运算符,从运算数栈里退出两个运算数进行运算,并将结果入运算数栈。
- 若“=”即优先级相等(一般用于“()”的判定):运算符退栈,消去一个括号读入下一个字符;
- 这时需用到比较运算符优先级的函数:precede(w,ch)
- 重复上述过程,直至整个表达式求值完毕(即符号栈的栈顶元素和当前读入的字符均为”#”),操作数栈的栈顶元素为计算结果。
2. 将中缀表达式转换为后缀表达式
- 从左向右读取表达式,读到运算数把它输出;
读到运算符f,则把符号栈的栈顶元素的算符和f进行优先级比较:
- 若优先级高:该运算符入运算符栈;
- 若优先级相等:从运算符栈退出一个运算符,不输出;
- 若优先级低,从运算符栈退出一个运算符,从运算数栈里输出所有比f优先级高的运算符,直至栈顶算符优先级小于f,f入运算符栈。
- 重复以上流程,一直到最终输出后缀表达式为止。