前序遍历的顺序:根-左-右
思路分析:
非递归的二叉树前序遍历大的思想分为:①访问它的左路节点;②访问左路节点的右子树
具体非递归的实现思路如下: ①拿到根节点,然后将其入栈,再看它的左子树是否为空; ②若左子树不为空,则把此时左子树作为当前节点,重复操作①; ③当左子树为空时,让栈顶节点出栈,但不输出,并去访问出栈节点的右子树,看其是否为空; ④若出栈节点的右子树不为空,则取出节点,循环到操作①; ⑤如果出栈节点的右子树为空,则继续出栈,但不输出,同时将出栈节点的右子树置为当前节点,看其是否为空,重复操作④和⑤; ⑥直到当前节点为NULL并且栈空,遍历结束。
具体实现代码如下:
void BinaryTreePrevOrderNonR(BTNode* root)//前序遍历的非递归
{
Stack st;
StackInit(&st,10);
BTNode* cur = root;
while (cur || StackEmpty(&st) != 0)
{
//开始访问一棵树
//1.先访问树的左路节点
while (cur)
{
printf("%c ", cur->_data);
StackPush(&st, cur);
cur = cur->_left;
}
BTNode* top = StackTop(&st);
StackPop(&st);
//2.访问左路节点的右子树
cur = top->_right;
}
printf("\n");
}