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

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

六、二叉树的基本操作（非递归遍历）&二叉排序树的操作

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

1. 非递归中序遍历

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

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

template <class elemType>voidbSearchTreeType<elemType>::deleteFromTree(nodeType<elemType>*&p){       nodeType<elemType>*temp;       nodeType<elemType>*current;       nodeType<elemType>*trailCurrent;        if(p== NULL)       {              cout<< "The BST is NULL!" << endl;              return;       }       if(p->llink== NULL && p->rlink == NULL)      //情况1,左右节点都为空（叶节点）       {              temp= p;              p= NULL;              deletetemp;       }       elseif( p->rlink == NULL)                     //情况2,右子树为空，左非空       {              temp= p;              p= temp->llink;              deletetemp;       }       elseif(p->llink == NULL)                      //情况3,左子树为空，右非空       {              temp= p;              p= temp->rlink;              deletetemp;       }       else                           //情况4,左右都非空[用中序遍历的前一个节点替换]       {              current= p->llink;              trailCurrent= NULL;               while(current->rlink!= NULL)              {                     trailCurrent= current;   //trailCurrent最终指向准备删除节点的前一个节点                     current= current->rlink;              }               p->info= current->info;                //信息赋值               if(trailCurrent== NULL)              //仅一个左孩子节点              {                     p->rlink = current->llink;                       }              else              {                     trailCurrent->rlink= current->llink; //给删除前点的前面一个节点调整指针指向              }              deletecurrent;       } }