이 진 트 리 의 스 트 리밍 알고리즘(상세 예제 분석)
#include<iostream>
#include<assert.h>
#include<stack>
#include<queue>
using namespace std;
struct Node
{
int v;
Node *leftChild,*rightChild;
Node():leftChild(NULL),rightChild(NULL){}
Node(int vv):leftChild(NULL),rightChild(NULL)
{
v=vv;
}
};
void print(int v)
{
cout<<v<<" ";
}
void PreOrderTraverse(Node *n, void (* visit)(int))
{
assert(n!=NULL&&visit!=NULL);
(*visit)(n->v);
if(n->leftChild!=NULL) PreOrderTraverse(n->leftChild,visit);
if(n->rightChild!=NULL) PreOrderTraverse(n->rightChild,visit);
}
void InOrderTraverse(Node *n, void (* visit)(int))
{
assert(n!=NULL&&visit!=NULL);
if(n->leftChild!=NULL) InOrderTraverse(n->leftChild,visit);
(*visit)(n->v);
if(n->rightChild!=NULL) InOrderTraverse(n->rightChild,visit);
}
void PostOrderTraverse(Node *n, void (* visit)(int))
{
assert(n!=NULL&&visit!=NULL);
if(n->leftChild!=NULL) PostOrderTraverse(n->leftChild,visit);
if(n->rightChild!=NULL) PostOrderTraverse(n->rightChild,visit);
(*visit)(n->v);
}
// ,
// , , ( ) ,
// ,
void PreOrder(Node *n, void (* visit)(int))
{
stack<Node*> sta;
sta.push(n);
while(!sta.empty())
{
Node * t=sta.top();
sta.pop();
assert(t!=NULL);
(*visit)(t->v);
if(t->rightChild!=NULL) sta.push(t->rightChild);
if(t->leftChild!=NULL) sta.push(t->leftChild);
}
}
//
void InOrder(Node * n , void (* visit) (int))
{
stack<Node *> sta;
sta.push(n);
Node * p= n;
while(!sta.empty()&&p!=NULL)
{
p=sta.top();
while(p!=NULL&&!sta.empty())
{
sta.push(p->leftChild);
p=p->leftChild;
}
sta.pop();//
if(!sta.empty())
{
p=sta.top();
sta.pop();
(*visit)(p->v);
sta.push(p->rightChild);
}
}
}
//
struct StkNode
{
Node * ptr;
bool tag;//false=left and true=right
StkNode():ptr(NULL),tag(false)
{}
};
void PostOrder(Node * n ,void (*visit) (int))
{
stack<StkNode> sta;
StkNode w;
Node * p = n;
do {
while(p!=NULL)
{
w.ptr=p;
w.tag=false;
sta.push(w);
p=p->leftChild;
}
bool flag=true;
while(flag&&!sta.empty())
{
w=sta.top();
sta.pop();
p=w.ptr;
if(!w.tag)//left, ,
{
w.tag=true;//
sta.push(w);
flag=false;
p=p->rightChild;
}
else
{
(*visit)(p->v);
}
}
} while(!sta.empty());
}
// ,
void LevelOrderTraverse(Node * n , void (* visit )(int))
{
assert(n!=NULL&&visit!=NULL);
queue<Node * > que;
que.push(n);
while(!que.empty())
{
Node * t=que.front();
(*visit)(t->v);
que.pop();
if(t->leftChild!=NULL) que.push(t->leftChild);
if(t->rightChild!=NULL) que.push(t->rightChild);
}
}
int main()
{
Node * head= new Node(0);
Node * node1= new Node(1);
Node * node2= new Node(2);
Node * node3= new Node(3);
Node * node4= new Node(4);
Node * node5= new Node(5);
Node * node6= new Node(6);
head->leftChild=node1;
head->rightChild=node2;
node1->leftChild=node3;
node1->rightChild=node4;
node2->rightChild=node5;
node4->leftChild=node6;
/* LevelOrderTraverse(head,print);
cout<<endl;
PreOrderTraverse(head,print);
cout<<endl;*/
InOrder(head,print);
cout<<endl;
InOrderTraverse(head,print);
cout<<endl;
PostOrder(head,print);
cout<<endl;
PostOrderTraverse(head,print);
cout<<endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1717 소수 화 점수 2 (수학)소수 화 점수 2 레이 는 수학 시간 에 선생님 의 말씀 을 듣 고 모든 소수 가 점수 로 표시 되 는 형식 이 라 고 말 했다. 그 는 녹 기 시 작 했 고 곧 완성 되 었 다. 그러나 그 는 또 하나의 문 제 를...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.