二叉树的中序非递归算法,详见下
首先,二叉树结点定义
typedef struct BiTNode//二叉树结点结构{string data;struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;
中序非递归算法,代码如下
void Inorder_I(BiTree T)//中序的非递归遍历{stack<BiTNode*>s;BiTree p=T;while(p!=NULL||!s.empty())//栈不空或P不空时循环{if(p) //一路向左{s.push(p); //当前节点入栈p=p->lchild; //左孩子不空,一直往左走}else //出栈,并转向出栈节点的右子树{p=s.top();cout<<p->data; s.pop();//栈顶元素出栈,访问出栈节点p=p->rchild; //返回while循环继续进入if-else语句}}}
运行结果如下