二叉树的先序、中序非递归遍历

之前写过二叉树的递归遍历的三种情况，很简单的讲解，很简单的代码就能实现，因为二叉树的很多操作都基于二叉树这个自然的递归情况，所以操作起来十分简单。但是我们今天还是要介绍一下二叉树的非递归遍历，为什么还要写这个更复杂的非递归遍历呢？其实这个大家也应该都清楚啊，递归的优点和缺点，如果你的树足够大的话，一直递归下去怎么办？栈的空间通常也只有几兆大小而已，总有一天会用完，所以就需要通过非递归的方式来解决这个问题。

  之前也写过一些将递归问题转换成非递归的方式来解决，基本上来说，转换这种问题有两种思路。一是通过循环来实现，但是这种条件有一个小小的限制，就是这种方法一般用来解决单递归问题。什么是单递归问题，二叉树是双递归问题，它有两种循环情况，所以很明显通过普通的循环很难来实现二叉树的非递归遍历，那就只能是第二种情况，也就是通过模拟栈来实现，不正规的可以理解成， 你递归用的是系统的栈，你不够用，那我就模仿一个数据结构的栈给你用。二叉树的非递归情况就是通过这个方式来进行简单的实现。

 首先是实现二叉树的先序遍历。

 

还是拿之前的图，递归的时候首先通过一层一层的循环走到最后一层左子树，然后因为是先序遍历所以当你遇到了节点的时候就要先把他输出，当你访问完2的左子树的时候是不是该访问2的右子树了，那这时候我怎么才能找到我的2的右子树，拿一个节点把他存起来？那要是数据很多的时候呢？ 这时候自然想到的是拿一个数据结构来把你的数据存起来，而且这个是先访问的节点后访问他的右子树，自然而然也就想到了通过栈来存储这些访问了但是还没有访问它右子树的节点。

 

void BTreePrevOrderNonR(BTNode* root)

{

assert(root);

Stack S;

StackInit(&S,100);

BTNode *cur = root;

BTNode *top = NULL;

while (cur || StackEmpty(&S))

{

 

while (cur)

{

printf("%d", cur->_data);

StackPush(&S, cur);

cur = cur->_left;

}

top = StackTop(&S);

StackPop(&S);

cur = top->_right;

}

 

}

这里和层序遍历的时候改队列一样，你在栈中存储的并不是说1,2,3这些int类型的数据，而是存的是某个节点，这样cur = top->_right;这个语句才有用途才有含义。不然你怎么访问一个int类型数据的右孩子。

这里的第一个while循环的条件一定要想清楚，不能是如果栈不为空就跳出，拿上图来说你想想，当你1出栈的时候，虽然这时候cur指向了1的右孩子，但是还没有访问，下一个结点也还没有进去，这时候你跳出循环的话就是错误的。第二个循环就是找传入结点的最左孩子。每次找到最下边的结点的时候，代表需要从下往*问节点的右子树。这时候找到栈顶的结点，这是最近一个需要访问右子树的结点，找到后然后pop，让cur等于那个节点的右孩子。

 

可以看出来成功运行了出来。这里其实就是在模仿你的递归，首先通过第一个while循环不断的往最深一层走，找到没有左孩子的结点，这时候访问右子树就是他的子问题，但是最大的问题其实就是怎么找到你这个节点的右孩子，就是通过一个数据结构将他存起来，其实什么都可以存下来，不过，栈是最合适的一种，因为他是先进后出，很符合你的二叉树的遍历特点。

 写了先序遍历之后中序遍历就十分简单了，就是在你当前程序上进行少量的更改。

void BTreeInOrderNonR(BTNode* root)

{

assert(root);

Stack S;

StackInit(&S, 100);

BTNode *cur = root;

BTNode *top = NULL;

while (cur || StackEmpty(&S))

{

 

while (cur)

{

StackPush(&S, cur);

cur = cur->_left;

}

top = StackTop(&S);

printf("%d", top->_data);

StackPop(&S);

cur = top->_right;

}

}

中序遍历就是在出这个结点的时候出栈的时候，也就是访问完你的结点的左子树之后输出你这个结点的数据，然后去访问他的右子树的数据。