文件名称：统计二叉树中的高度-复高斯分布的数学基础理论
文件大小：6.48MB
文件格式：PDF
更新时间：2024-06-28 07:07:20
嵌入式 Linux C
（2）统计二叉树中的叶子节点 二叉树的遍历是操作二叉树的基础，二叉树的很多特性都可以通过遍历二叉树来得到。 在实际应用中，统计二叉树叶子节点的个数是非常常见的一种操作。 这个操作可以使用 3 种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是 否为叶子节点，如果是叶子节点将累加器加 1 即可。下面这个算法是利用先序遍历实现的。 /*二叉树叶子节点统计*/ int leaf_num(Node *tree_node, int *count) { if(tree_node) { /*访问根节点，判断该节点是否为叶子节点*/ if(!tree_node->lchild && !tree_node->rchild) (*count)++; /*先序遍历左子树*/ if(leaf_num(tree_node->lchild, count)) /*先序遍历右子树*/ if(leaf_num(tree_node->rchild, count)) return 1; return 0; } else return 1; } 要注意的是，在该函数中，计数器 count 必须是一个指针，否则 count 的值无法传递回主 函数。读者可以同样在主函数调用该函数，如下所示： printf("\ncounting leaf_number\n"); leaf_num(root, &count); printf("leaf number is %d\n", count); 这样，程序就会有正确的输出结果： counting leaf_number leaf number is 3 可以看到，这个输出结果与本节构建的二叉树相一致。 （3）统计二叉树中的高度 求二叉树的高度也是非常常见的一个操作。这个操作使用后序遍历比较符合人们求解二 叉树高度的思维方式：首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左 右子树较大的高度值加 1，其代码如下所示： int tree_height(Node *tree_node) { int h1, h2; if(!tree_node) return -1; else { /*后序遍历左子树，求出左子树的高度*/ h1 = tree_height(tree_node->lchild); /*后序遍历右子树，求出右子树的高度*/ h2 = tree_height(tree_node->rchild);