53_树中结点的查找操作

关键词：基于数据元素值的查找、基于结点的查找

0. 查找的方式

• 基于数据元素值的查找
  GTreeNode<T>* find(const T& value) const
• 基于结点的查找
  GTreeNode<T>* find(GTreeNode<T>* node) const
  树中数据元素和结点的查找

1. 基于数据元素值的查找

• 定义功能函数：GTreeNode<T>* find(GTreeNode<T>* node, const T& value) const
  在以node为根节点的树中查找value所在的结点
  递归查找

GTreeNode<T>* find(GTreeNode<T>* node, const T& value) const
    {
        GTreeNode<T>* ret = NULL;

        if( node != NULL )
        {
            if( node->value == value )
            {
                return node;
            }
            else
            {
                for(node->child.move(0);
                    !node->child.end() && (ret == NULL);
                    node->child.next())
                {
                    ret = find(node->child.current(), value);
                }
            }
        }

        return ret;
    }

GTreeNode<T>* find(const T& value) const
    {
        return find(root(), value);
    }

2. 基于结点的查找

• 定义功能函数：GTreeNode<T>* find(GTreeNode<T>* node, GTreeNode<T>* obj) const
  在以node为根节点的树中查找是否存在obj结点
  递归查找

GTreeNode<T>* find(GTreeNode<T>* node, GTreeNode<T>* obj) const
    {
        GTreeNode<T>* ret = NULL;

        if( node == obj )
        {
            return node;
        }
        else
        {
            if( node != NULL )
            {
                for(node->child.move(0);
                    !node->child.end() && (ret == NULL);
                    node->child.next())
                {
                    ret = find(node->child.current(), obj);
                }
            }
        }

        return ret;
    }

GTreeNode<T>* find(TreeNode<T>* node) const
    {
        return find(root(), dynamic_cast<GTreeNode<T>*>(node));
    }

3. 小结

• 查找操作是树的关键操作之一
• 基于数据元素的查找可判断值是否存在于树中
• 基于结点的查找可判断树中是否存在指定结点
• 插入操作和删除操作都依赖于查找操作

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