关键词：基于数据元素值的查找、基于结点的查找
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
