当前位置: 代码迷 >> 综合 >> 二叉树遍历-非递归-Cpp代码-后序
  详细解决方案

二叉树遍历-非递归-Cpp代码-后序

热度:71   发布时间:2024-01-16 02:15:41.0
#include<iostream>
#include<stack>
using namespace std;  //定义二叉树结点链式存储结构
struct BiTNode{int data;//数据域struct BiTNode *lchild,*rchild;//左右孩子指针
}*BiTree;//后序遍历函数声明
int PostOrder(struct BiTNode *BiTree);int main()  
{//初始化结点struct BiTNode node1,node2,node3,node4,node5,node6,node7,node8,node9,node10,node11;node1=(struct BiTNode){7,&node2,&node3};node2=(struct BiTNode){3,&node4,&node5};node3=(struct BiTNode){6,&node6,&node7};node4=(struct BiTNode){1,NULL,NULL};node5=(struct BiTNode){2,NULL,NULL};node6=(struct BiTNode){4,NULL,NULL};node7=(struct BiTNode){5,NULL,NULL};//建树BiTree=&node1;PostOrder(BiTree);cout << endl;return 0;  
}//后序遍历-非递归实现
int PostOrder(struct BiTNode *BiTree){stack<BiTNode*> s;struct BiTNode* p=BiTree;struct BiTNode* r=NULL;while(p||!s.empty()){if(p){?//走到最左边s.push(p);p=p->lchild;}else{?//向右p=s.top();?//取栈顶结点if(p->rchild&&p->rchild!=r){?//如果右子树存在且未被访问过p=p->rchild;?//转向右s.push(p);?//压入栈p=p->lchild;?//再走到最左}else{??//否则,弹出节点并访问p=s.top();s.pop();?//弹出cout << p->data << " ";?//访问r=p;?//记录最近访问过的结点p=NULL;?//结点访问完后,重置p指针}}//else}//whilereturn 0;
}

 

  相关解决方案