關鍵詞：基于數(shù)據(jù)元素值的查找疤祭、基于結點的查找
0. 查找的方式
- 基于數(shù)據(jù)元素值的查找
GTreeNode<T>* find(const T& value) const - 基于結點的查找
GTreeNode<T>* find(GTreeNode<T>* node) const
樹中數(shù)據(jù)元素和結點的查找
1. 基于數(shù)據(jù)元素值的查找
- 定義功能函數(shù)：
GTreeNode<T>* find(GTreeNode<T>* node, const T& value) const
在以node為根節(jié)點的樹中查找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. 基于結點的查找
- 定義功能函數(shù)：
GTreeNode<T>* find(GTreeNode<T>* node, GTreeNode<T>* obj) const
在以node為根節(jié)點的樹中查找是否存在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. 小結
- 查找操作是樹的關鍵操作之一
- 基于數(shù)據(jù)元素的查找可判斷值是否存在于樹中
- 基于結點的查找可判斷樹中是否存在指定結點
- 插入操作和刪除操作都依賴于查找操作
聲明：此文章僅是本人在學習狄泰學院《數(shù)據(jù)結構實戰(zhàn)開發(fā)教程》所做的筆記拟枚，文章中包含狄泰軟件資料內(nèi)容镜廉，一切版權歸狄泰軟件所有凿滤！
實驗環(huán)境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
