57_树中属性操作的实现

关键词：树中结点的数目、树的高度、树的度数

0. 树中结点的数目

• 定义功能：count(node)：在node为根结点的树中统计结点数目
  树中结点的数目递归计算
  树中结点的计算示例

    int count(GTreeNode<T>* node) const
    {
        int ret = 0;

        if(node != NULL )
        {
            ret = 1;

            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                ret += count(node->child.current());
            }
        }

        return ret;
    }

    int count() const
    {
        return count(root());
    }

1. 树的高度

• 定义功能函数：height(node)：获取node为根结点的树的高度
  树的高度的递归计算
  树的高度计算示例

    int height(GTreeNode<T>* node) const
    {
        int ret = 0;

        if( node != NULL )
        {
            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                int h = height(node->child.current());

                if( ret < h )
                {
                    ret = h;
                }
            }

            ++ret;
        }

        return ret;
    }

    int height() const
    {
        return height(root());
    }

2. 树的度数

• 定义功能函数：degree(node)：获取node为根结点的树的度数
  树的度数递归调用
  树的度数计算示例

    int degree(GTreeNode<T>* node) const
    {
        int ret = 0;

        if( node != NULL )
        {
            ret = node->child.length();

            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                int d = degree(node->child.current());

                if( ret < d )
                {
                    ret = d;
                }
            }
        }

        return ret;
    }

    int degree() const
    {
        return degree(root());
    }

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4