C语言实现：树与二叉树算法解析及后序遍历求解表达式

"树与二叉树算法汇总" 这篇资料主要涵盖了树和二叉树在计算表达式中的应用以及顺序存储结构的讨论，特别适合于考研复习。它提供了一种使用二叉树表示和计算算术表达式的方法，并讲解了如何通过后序遍历来求解表达式值。 首先，二叉树被用来表示算术表达式，其中每个节点包含一个运算符（'+'，'-'，'*'，'/'）和两个子节点，分别代表左子表达式和右子表达式。在二叉树中，根节点的运算符决定了整个表达式的运算顺序。例如，对于二叉树结构，我们可以采用后序遍历（即左子树-右子树-根节点）来依次计算子表达式的值，最终得到整个表达式的值。下面是一个示例函数`PostEval`，它递归地处理二叉树的每一个节点，计算表达式的值： ```c typedef struct node { ElemType data; float val; char optr; // 只取‘+’，‘-’，‘*’，‘/’ struct node *lchild, *rchild } BiNode, *BiTree; float PostEval(BiTree bt) { float lv, rv; if (bt != null) { lv = PostEval(bt->lchild); // 求左子树表示的子表达式的值 rv = PostEval(bt->rchild); // 求右子树表示的子表达式的值 switch (bt->optr) { case '+': value = lv + rv; break; case '-': value = lv - rv; break; case '*': value = lv * rv; break; case '/': value = lv / rv; break; } } return (value); } ``` 接着，资料提到了二叉树的顺序存储结构。在完全二叉树中，所有节点可以按照从上到下、从左到右的顺序存放在一维数组中。但对于非完全二叉树，需要补充“虚结点”以保持这种存储方式。如果一个节点没有子节点，那么它被认为是叶子节点。在顺序存储的二叉树中，可以通过检查一个节点的左右子节点是否为0来判断它是否是叶子节点。如果一个节点的两倍索引超过了数组长度，说明它没有子节点，因此可以认定为叶子节点。此外，叶子节点和它们的双亲之间的索引关系满足完全二叉树的特性。 函数`Leaves`是用来计算深度为`h`的顺序存储二叉树的叶子节点数量。数组`BT`用于存储二叉树的节点值，初始化长度为`2^h - 1`，并从索引1开始存储。通过遍历数组，检查每个节点是否有子节点，如果没有则增加叶子节点计数。 这部分内容不仅涉及了二叉树的基本概念，还深入到实际问题的应用，如计算表达式和非完全二叉树的顺序存储。这些知识点对于理解和解决计算机科学中的数据结构和算法问题至关重要，尤其对于准备考研的学生来说，这是非常有价值的复习材料。