二叉树遍历的非递归算法
时间: 2023-09-17 15:09:35 浏览: 55
二叉树的遍历有三种方式:前序遍历、中序遍历和后序遍历。其非递归算法如下:
1. 前序遍历非递归算法
使用栈来模拟前序遍历的递归过程,先将根节点压入栈中,然后循环执行以下步骤:
- 弹出栈顶节点,并打印该节点的值。
- 如果该节点有右子树,则将右子树压入栈中。
- 如果该节点有左子树,则将左子树压入栈中。
代码实现:
void PreOrderTraversal(BinTree BT)
{
if (!BT) return; // 空树直接返回
Stack S = CreateStack(MaxSize); // 创建栈
BinTree T = BT;
while (T || !IsEmpty(S))
{
while (T)
{
printf("%d ", T->Data); // 访问节点
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S);
T = T->Right;
}
}
}
2. 中序遍历非递归算法
使用栈来模拟中序遍历的递归过程,先将根节点入栈,然后循环执行以下步骤:
- 如果当前节点不为空,将其左子树入栈。
- 如果当前节点为空,弹出栈顶节点,并打印该节点的值,然后将其右子树入栈。
代码实现:
void InOrderTraversal(BinTree BT)
{
if (!BT) return; // 空树直接返回
Stack S = CreateStack(MaxSize); // 创建栈
BinTree T = BT;
while (T || !IsEmpty(S))
{
while (T)
{
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S);
printf("%d ", T->Data); // 访问节点
T = T->Right;
}
}
}
3. 后序遍历非递归算法
使用栈来模拟后序遍历的递归过程,需要记录上一个访问的节点 LastVisit。先将根节点入栈,然后循环执行以下步骤:
- 如果栈顶节点的左右子树都为空,弹出栈顶节点,并打印该节点的值,然后将 LastVisit 指向该节点。
- 如果栈顶节点的右子树不为空且未被访问过,则将右子树入栈。
- 如果栈顶节点的左子树不为空且未被访问过,则将左子树入栈。
代码实现:
void PostOrderTraversal(BinTree BT)
{
if (!BT) return; // 空树直接返回
Stack S = CreateStack(MaxSize); // 创建栈
BinTree T = BT, LastVisit = NULL;
while (T || !IsEmpty(S))
{
while (T)
{
Push(S, T);
T = T->Left;
}
T = Top(S);
if (T->Right == NULL || T->Right == LastVisit)
{
Pop(S);
printf("%d ", T->Data); // 访问节点
LastVisit = T;
T = NULL;
}
else
{
T = T->Right;
}
}
}