C语言非递归的方法实现对给定二叉树的先序和层序遍历算法。
时间: 2024-05-11 22:13:44 浏览: 9
先序遍历:使用栈来实现非递归的先序遍历,从根节点开始,先将根节点入栈,然后进入循环,每次从栈中弹出一个节点,打印该节点的值,并将其右子节点和左子节点依次入栈(注意先入右子节点再入左子节点),直到栈为空。
层序遍历:使用队列来实现非递归的层序遍历,从根节点开始,先将根节点入队列,然后进入循环,每次从队列中弹出一个节点,打印该节点的值,并将其左子节点和右子节点依次入队列,直到队列为空。
代码实现如下:
先序遍历:
```c
void PreOrderTraversal(BiTree T)
{
if(T == NULL)
return;
Stack S;
InitStack(&S);
Push(&S, T);
while(!StackEmpty(&S))
{
BiTree p;
Pop(&S, &p);
printf("%c ", p->data);
if(p->rchild)
Push(&S, p->rchild);
if(p->lchild)
Push(&S, p->lchild);
}
}
```
层序遍历:
```c
void LevelOrderTraversal(BiTree T)
{
if(T == NULL)
return;
Queue Q;
InitQueue(&Q);
EnQueue(&Q, T);
while(!QueueEmpty(&Q))
{
BiTree p;
DeQueue(&Q, &p);
printf("%c ", p->data);
if(p->lchild)
EnQueue(&Q, p->lchild);
if(p->rchild)
EnQueue(&Q, p->rchild);
}
}
```