数据机构实验 树及其应用实验

在这个实验中，我们将探讨如何利用数据结构，特别是二叉树，来实现一个重言式的判别程序。这个程序主要用于处理逻辑表达式，其中包括常见的逻辑运算符"或"（|）、"与"（&）和"非"（~）。运算符的优先级遵循常规规则，即括号内的运算优先。下面我们将详细解释实验的关键知识点。 我们需要了解**数据结构**，特别是**二叉树**。二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。在这个实验中，我们使用二叉树来表示逻辑表达式。每个节点包含一个字符数据成员，用于存储运算符或变量，以及指向其左子树和右子树的指针。 在实现这个程序时，我们使用了**C++**语言，这是一种面向对象的编程语言，允许我们创建类和对象，方便地处理数据结构。在代码中，我们定义了`BiTNode`结构体来表示二叉树的节点，包含了数据（`uchar data`）、左子节点（`struct BiTNode *lchild`）和右子节点（`struct BiTNode *rchild`）的指针。 为了处理逻辑表达式，我们还需要实现一个**栈**的数据结构。这里使用了顺序栈（`SqStack`），它由一个基础指针`base`和一个顶部指针`top`组成，以及栈的大小`stacksize`。栈的操作包括初始化（`InitStack`）、压栈（`Push`）、弹栈（`Pop`）和获取栈顶元素（`GetTop`）。这些操作都是通过动态内存分配来扩展栈的大小，以适应不断变化的需求。 此外，实验还涉及到**逻辑运算符的优先级**处理。在创建二叉树时，我们根据运算符的优先级自底向上地构建树。例如，如果左子树的节点代表的运算符优先级更高，那么它的左右孩子将被设置为空，表明它是运算符的直接结果，而右子树则保持完整，等待进一步的运算。 为了测试所有可能的逻辑变量组合，我们使用了一个名为`Creat_Com`的函数。这个函数生成一个二维数组`combin`，其中包含了变量的所有可能取值组合。在逻辑表达式中，变量可以取真（1）或假（0）值，这个函数通过位运算生成这些组合。 `Creat_Tree`函数用于根据运算符优先级创建二叉树。它接收两个子节点（左子树`l`和右子树`r`）以及一个新节点的指针`subtree`，并将这两个子节点连接到新节点上。这一步是构建逻辑表达式树的关键。 通过以上这些技术，我们可以实现一个能够解析和评估逻辑表达式的程序。用户可以从键盘输入逻辑表达式，程序会根据输入构建一棵二叉树，并通过遍历这棵树来判断表达式是否为重言式（恒为真的逻辑表达式）。整个过程展示了数据结构和算法在解决实际问题中的应用，特别是二叉树和栈在处理逻辑表达式时的重要作用。