① 跪求!!10分奉上!统计二叉树结点个数的算法 非递归
一般情况下,涉及二叉树的很多操作都包含两个方面。一方面,由于二叉树本身的递归定义,因此用递归的思想设计其很多操作是顺理成章的;另一方面,为了控制过程的深度和节约栈空间,我们有时也会考虑用非递归的思想设计很多关于二叉树的操作。必须说明的是,非递归思想一般都需要额外栈或队列结构的支持。下面来看一下关于统计二叉树结点个数的非递归算法设计:
1、将根结点插入队列。
2、判断队列是否为空,非空执行第三步,否则执行第四步退出循环。
3、从队列中取出一个结点,同时将取出结点的儿子结点插入队列。此外,将计数器加1,再转到第二步。
4、结束循环。
注意:队列是先进先出的结构,与栈相反。
如果你根据以上仍然不能写出完整的程序,下面的程序可作为你的参考。
int size()//返回结点数函数
{
linkqueue<node*>list;//定义元素为node*型的队列
int sum=0;
list.push(root);
while(!list.empty())
{
node* p=list.top();//保存即将出队的元素
list.pop();//队列首元素出队
if(p->lchild)//左儿子不为空,即进队
list.push(p->lchild);
if(p->rchild)//同上
list.push(p->rchild);
sum++;//计数器增1
}
return sum;
}
要想完全把握以上程序你必须对队列的结构有很好的理解。此外,需要说明的是,计数器是以出队元素个数为指标进行计数的,而非进队元素。这样可使程序简洁和容易理解得多。
② 关于全排列的生成算法
个人一点见解,希望对你有所帮助。
依我之见,你的对换部分出了一点点问题。只要作如下修改即可:
1、exchange 改为:
procere exchange(l,r:integer);
var
t,len:integer;
begin
if l=r then exit;
len:=r-l+1;
len:=len div 2;
for i:=1 to len do
begin
t:=a[l+i-1];
a[l+i-1]:=a[r-i+1];
a[r-i+1]:=t;
end;
end;
2、主过程中exchange(p,n)改为exchange(i+1,n)。