# 二叉树遍历的非递归实现

```#include<stdio.h>
#include<stack>
#include<stdlib.h>
using namespace std;

struct ListNode
{
int data;
ListNode *lchild,*rchild;
};

ListNode* Createbst()
{
int data;
scanf("%d",&data);
if(data!=-1)
{
ListNode* root=(ListNode*)malloc(sizeof(ListNode));
root->lchild=root->rchild=NULL;
root->data=data;
root->lchild=Createbst();
root->rchild=Createbst();
return root;
}
else return NULL;
}

void PreOrder(ListNode *root)
{
stack<ListNode*> s;
ListNode *p=root;
while(p!=NULL || !s.empty())
{
while(p!=NULL)
{
printf("%d",p->data);
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}

int main()
{
ListNode* root;
root=Createbst();
PreOrder(root);
return 0;
}```

中序遍历

```void InOrder(ListNode*root)
{
stack<ListNode*>s;
ListNode* p=root;
while(p!=NULL || !s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
printf("%d",p->data);
p=p->rchild;
}
}
}```

后序遍历

```struct BiTree
{
ListNode* treeNode;
int flag;
};
void PostOrder(ListNode* root)
{
stack<BiTree*> s;
BiTree* sTree=(BiTree*)malloc(sizeof(BiTree));
sTree->treeNode=root;
sTree->flag=0;
s.push(sTree);
while(!s.empty())
{
BiTree* tmptree=s.top();
if(tmptree->flag==2)
{
printf("%d ",tmptree->treeNode->data);
s.pop();
}
else
{
if(tmptree->treeNode->rchild)
{
sTree=(BiTree*)malloc(sizeof(BiTree));
sTree->flag=0;
sTree->treeNode=tmptree->treeNode->rchild;
s.push(sTree);
}
tmptree->flag++;
if(tmptree->treeNode->lchild)
{
sTree=(BiTree*)malloc(sizeof(BiTree));
sTree->flag=0;
sTree->treeNode=tmptree->treeNode->lchild;
s.push(sTree);
}
tmptree->flag++;
}
}
}```

235 篇文章42 人订阅

0 条评论