关键词：二叉树中结点的数目、二叉树的高度、二叉树的度树
0. 二叉树中结点的数目
- 定义功能函数
count(node)：在node为根结点的二叉树中统计结点数目
count函数的递归调用示意图
int count(BTreeNode<T>* node) const
{
return node ? count(node->left) + count(node->right) + 1 : 0;
}
int count() const
{
return count(root());
}
1. 二叉树的高度
- 定义功能函数
height(node)：获取node为根结点的二叉树的高度
height函数的递归调用示意图
int height(BTreeNode<T>* node) const
{
int ret = 0;
if( node != NULL )
{
int l = height(node->left);
int r = height(node->right);
ret = (l > r ? l : r) + 1;
}
return ret;
}
int height() const
{
return height(root());
}
2. 二叉树的度树
- 定义功能
degree(node)：获取node为根结点的二叉树的度数
degree函数的递归调用示意图
int degree(BTreeNode<T>* node) const
{
int ret = 0;
if( node != NULL )
{
BTreeNode<T>* child[] = {node->left, node->right}; // 通过数组去掉代码冗余
ret = (!!node->left) + (!!node->right); // 通过两次取反，如果该node的child为空，则值为0，若为非空，则为1
for(int i=0; (i<2) && (ret<2); ++i) // 当ret == 2时，跳出循环，在二叉树中度最大为2，因此不需要继续递归，提高了效率
{
int d = degree(child[i]);
if( ret < d )
{
ret = d;
}
}
}
return ret;
}
int degree() const
{
return degree(root());
}
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
