C/C++实现树操作的实例代码

预处理命令 #include <stdio> #include <stdlib> #define TRUE 1 #define FALSE 0 typedef int elemtype; typedef struct tNode* tree; typedef struct tNode { elemtype elem; tree left; tree right; }tNode; 计算树的节点个数 //明确函数的功能：返回传入树的节点个数 //定好尾头：尾：当传入的节点尾NULL时 头：1 + count(t->left) + count(t->right) int count 在C/C++编程中，树是一种非常重要的数据结构，它被广泛用于表示层次关系和执行各种操作。在给定的代码实例中，我们看到几个针对二叉树操作的函数，包括计算节点个数、查找特定数值的节点个数、求节点数据的总和、判断树中是否存在某个值以及打印树的主干。以下是对这些函数的详细解释： 1. 计算树的节点个数： 函数`count(tree t)`使用递归方法计算树中节点的总数。当输入的节点`t`为空（NULL）时，返回0（表示没有节点）。否则，返回1（当前节点）加上左子树的节点数和右子树的节点数。这是典型的递归问题，每个节点的子节点数量将被累加。 2. 求树中节点数据为`num`的节点个数： 函数`count_num(tree t, elemtype num)`同样采用递归策略。如果当前节点`t`的元素值等于`num`，则返回1（当前节点）加上左子树和右子树中`num`的节点数；否则，仅返回子树中`num`的节点数。 3. 求树中节点数据的总和： `add(tree t)`函数通过递归遍历整棵树，累加所有节点的数据。当节点`t`为空，返回0，否则返回当前节点的数据加上左子树和右子树的数据总和。 4. 判断树中是否有数据为`num`的节点： 这里有两个实现，`inTree_1`和`inTree_2`。它们都使用递归来检查树的每个节点。`inTree_1`在找到匹配的节点时立即返回TRUE，而`inTree_2`会遍历整个树并返回1（表示存在匹配节点）或0（表示不存在匹配节点）。 5. 计算值为`num`的节点个数： 函数`count_elem(tree t, elemtype val, int* num)`递归地计算值为`val`的节点个数。它使用一个指向整数的指针`num`来累计计数。对于每个子节点，它检查值并更新`num`，最后返回`num`的值。 6. 打印树的主干： `print_trunk(tree t)`函数用于打印树的主干，即所有有子节点的节点。如果当前节点`t`有子节点（左或右），则打印节点值，并递归调用自身来打印左侧和右侧的子树的主干。 这些函数展示了如何使用C/C++中的结构体和指针来定义二叉树，以及如何通过递归方法处理与树相关的操作。递归是解决这类问题的关键，因为它允许程序以自相似的方式处理树的层次结构。在实际编程中，理解并掌握这些基本的树操作对于处理复杂的数据结构和算法问题至关重要。