树的非递归前中后序 ~

由于递归容易导致栈溢出，所以我们采用非递归进行处理

非递归采用 循环和栈 的方式进行处理

一、前序

//前序 void PreOrderLoop(TreeNode *pRoot) { TreeNode *pCur = pRoot; Stack stack; //定义一个栈 TreeNode *pTop; //栈顶元素 stackInit(&stack); while (!stackIsempty(&stack) || pCur != NULL) //循环条件 { while (pCur != NULL) { printf("%c ", pCur->data); //打印结点数据 stackPush(&stack, pCur); //进行入栈 pCur = pCur->pleft; //再去遍历他的左子树 } pTop = stackTop(&stack); //循环退出 左子树全部遍历完 stackPop(&stack); //将栈顶元素出栈 pCur = pTop->pright; //再去遍历此时根的左子树 } }

二、中序

//中序 void InOrderLoop(TreeNode *pRoot) { TreeNode *pCur = pRoot; Stack stack; TreeNode *pTop; stackInit(&stack); while (!stackIsempty(&stack) || pCur != NULL) { while (pCur != NULL) { stackPush(&stack, pCur); pCur = pCur->pleft; } pTop = stackTop(&stack); stackPop(&stack); printf("%c ", pTop->data); pCur = pTop->pright; } }

 

三、后序

 

后序这里我们要考虑的比前面两个多一点，首先：我们会定义一个plast变量来表示上一次已经被后序遍历完的根

我们打印的条件分为两种：（1）右子树为空  （2）右子树已经被遍历

若符合则进行打印，否则遍历此结点的右子树

代码如下~

//后序 void PostOrderLoop(TreeNode *pRoot) { TreeNode *pCur = pRoot; Stack stack; TreeNode *pTop=NULL; TreeNode *plast = NULL; //表示上一次已经被后序遍历完的树的根 stackInit(&stack); while (!stackIsempty(&stack) || pCur != NULL) { while (pCur != NULL) { stackPush(&stack, pCur); pCur = pCur->pleft; } //没有被遍历的 还剩栈里的右子树和根 pTop = stackTop(&stack); if (pTop->pright == NULL || pTop->pright == plast) { printf("%c ", pTop->data); stackPop(&stack); plast = pTop; continue; } //遍历top的右子树，成为子问题 pCur = pTop->pright; } }