? ? ? ? {
? ? ? ? ? ? p=queue[head++];//取对头元素
? ? ? ? ? ? if(p->left!=NULL)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? queue[tail++]=p->left;//如果有则记录左孩子
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? }
? ? ? ? ? ? if(p->right!=NULL)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? queue[tail++]=p->right;//如果有则记录右孩子
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? }
? ? ? ? ? ? putchar(p->data);//输出当前结点值
? ? ? ? }
? ? ? ? amount=j;//更新计数器
? ? ? ? if(amount==0)break;
? ? }
}
八.计算从根到指定结点的路径
?
要记录路径，当然不宜用递归的方式，这里采用后序遍历的非递归实现
?
为什么选择后序遍历？
?
因为在这种遍历方式中，某一时刻栈中现有的结点恰恰就是从根结点到当前结点的路径（从栈底到栈顶）。严格地说，此时应该用队列来保存路径，因为栈不支持从栈底到栈顶的出栈操作（这样的小细节就把它忽略好了...）
?
?
//参数c为指定结点值
void printPath(struct bt* root,char c)
{
? ? struct st* stack[100];//声明结点栈
? ? int top=-1;//栈顶索引
? ? int i;
? ? struct bt* p=root;//当前结点
? ? struct bt* q=NULL;//上一次处理的结点
? ? while(p!=NULL||top!=-1)
? ? {
? ? ? ? for(;p!=NULL;p=p->left)stack[++top]=p;//遍历左子树
? ? ? ? if(top!=-1)
? ? ? ? {
? ? ? ? ? ? p=stack[top];//获取栈顶元素
? ? ? ? ? ? if(p->right==NULL||p->right==q)//如果当前结点没有右孩子或者右孩子刚被访问过
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(p->data==c)//如果找到则输出路径
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? for(i=0;i<=top;i++)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? p=stack[i];
? ? ? ? ? ? ? ? ? ? ? ? putchar(p->data);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? printf("\n");
? ? ? ? ? ? ? ? ? ? //此处不跳出循环，因为可能存在不唯一的结点值，遍历整个树，找出所有路径
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? q=p;
? ? ? ? ? ? ? ? p=stack[top];
? ? ? ? ? ? ? ? top--;
? ? ? ? ? ? ? ? p=NULL;
? ? ? ? ? ? }
? ? ? ? ? ? else p=p->right;//遍历右子树
? ? ? ? }
? ? }
}
?
源码：#include
?
struct bt
{
? ? char data;
? ? struct bt *left;
? ? struct bt *right;
};
?