实习二 树、二叉树及其应用.pptVIP

实习二 树、二叉树及其应用 任选一题 1、建立二叉树并求指定结点路径 【问题描述】 给定按照先序遍历的次序输入的字符串序列（可以@代替空格），建立二叉树，进行中序遍历，输出指定结点的路径。 【基本要求】 已知先序遍历次序的字符串序列，试设计完成下列任务： （1）构造一棵二叉树； （2）对该二叉树进行非递归中序遍历，输出遍历序列。 （3）用凹入法打印该二叉树。 （4）给定任意结点，输出从树根到该结点的路径。 2、计算命题演算公式的真值 【问题描述】 所谓命题演算公式是指由逻辑变量（其值为TRUE 或FALSE）和逻辑运算符∧（AND）、∨（OR）和 ┐（NOT）按一定规则所组成的公式（蕴含之类 的运算可以用∧、∨和┐来表示）。公式运算的 先后顺序为┐、∧、∨，而括号（）可以改变优 先次序。已知一个命题演算公式及各变量的值， 要求设计一个程序来计算公式的真值。 【基本要求】 （1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。 （2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。 （3）根据用户的要求显示表达式的真值表。 * * *