数据结构面试之六——二叉树的常见操作2（非递归遍历&二叉排序树)

题注

《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。

接上一节第五部分，主要分析二叉树的非递归遍历和二叉排序树的操作。

1. 非递归中序遍历

//1.依次将根节点root的左子树入栈,直到lchild=NULL,执行2

//2.将栈的元素出栈、访问；将当前指针指向节点的rchild，循环遍历。直到栈空为止！

template<typenameelemType>       voidbinaryTreeType<elemType>::noRecursionInorderTraversal()                      //非递归中序遍历       {              cout<< "noRecursio