使用递归的查找算法有哪些？
楼主，以下程序编译调试通过。
程序中使用了C++的std::stack
算法在BiNodeTree::find(int value, BiNodeTree *root)中，(找不到返回0，找到返回其指针）
你可以根据自己二叉树定义稍作修改。
main()中是测试，你可以修改以便作更多的测试。写了这么多能不能多给点分啊? :-P
#define BINODETREE_DEBUG //调试的时候定义，否则删除这一行
#include
#include
using namespace std;
class BiNodeTree
{
public:
int value;
BiNodeTre...全部
楼主，以下程序编译调试通过。
程序中使用了C++的std::stack
算法在BiNodeTree::find(int value, BiNodeTree *root)中，(找不到返回0，找到返回其指针）
你可以根据自己二叉树定义稍作修改。
main()中是测试，你可以修改以便作更多的测试。写了这么多能不能多给点分啊? :-P
#define BINODETREE_DEBUG //调试的时候定义，否则删除这一行
#include
#include
using namespace std;
class BiNodeTree
{
public:
int value;
BiNodeTree* left;
BiNodeTree* right;
BiNodeTree(){left=right=0;}
BiNodeTree(int i){value=i; left=right=0;}
BiNodeTree* find(int value, BiNodeTree *root);
BiNodeTree* find(int value){return find(value,this);}
};
BiNodeTree* BiNodeTree::find(int value, BiNodeTree* root)
{
stack st;
BiNodeTree* pNode = root;
BiNodeTree* pchecked = root;
while(1)
{
#ifdef BINODETREE_DEBUG //调试的时候定义，否则删除这一行
coutvaluevalue == value)
return pNode;
if(pchecked == pNode->right)
{//右不为NULL，且右边刚查过
pchecked = pNode;
if(st。
empty()) return 0;
pNode = st。top();
st。pop();
continue;
}
if(pNode->left != 0)
{
if( pchecked == pNode->left )
{
if( pNode->right )
{//左不为NULL，且左刚查过，且右不为NULL
st。
push(pNode);
pNode = pNode->right;
continue;
}
else
{//左不为NULL，且左刚查过，且右=NULL
pchecked = pNode;
if(st。
empty()) return 0;
pNode = st。top();
st。pop();
continue;
}
}
else
{//左不为NULL，且左没有查过
st。
push(pNode);
pNode = pNode->left;
continue;
}
}
else if( pNode->right )
{//左=NULL，且右不为NULL，（右必然没有查过，否则走while下的第一分支）
st。
push(pNode);
pNode = pNode->right;
continue;
}
else
{//左=NULL，且右=NULL
pchecked = pNode;
if(st。
empty()) return 0;
pNode = st。top();
st。pop();
}
}//end of while
};
void main(void)
{
BiNodeTree t1(1),t2(2),t3(3),t4(4),t5(5),t6(6),t7(7),t8(8),t9(9),t10(10),t11(11);
t1。
left = &t2;
t1。right = &t3;
t2。left = &t4;
t2。right = &t5;
t4。left = &t6;
t5。
right = &t7;
t7。left = &t8;
t7。right = &t9;
t3。left = &t10;
t3。right = &t11;
if(&t11 == t1。
find(11))
cout<<"found 11 with root=1\n";
else
cout<<"not found 11 with root=1\n";
if(&t9 == t1。
find(9))
cout<<"found 9 with root=1\n";
else
cout<<"not found 9 with root=1\n";
if(&t8 == t3。
find(8))
cout<<"found 8 with root=3\n";
else
cout<<"not found 8 with root=3\n";
}。
收起
