이 진 트 리 의 비 재 귀적 사 이 를 깊이 이해 하 다.
1. 앞 순 서 는 앞 순 서 를 옮 겨 다 니 며 '뿌리 결산 점 - 왼쪽 아이 - 오른쪽 아이' 순서 로 방문 합 니 다.
1. 귀속 실현
void preOrder1(BinTree *root) //
{
if(root!=NULL)
{
cout<data< preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
2. 비 재 귀 는 앞 순서에 따라 방문 하 는 순 서 를 실현 하고 뿌리 노드 를 먼저 방문 한 다음 에 왼쪽 아이 와 오른쪽 아 이 를 각각 방문 합 니 다.즉, 모든 노드 에 대해 서 는 뿌리 노드 로 볼 수 있 기 때문에 직접 방문 할 수 있 습 니 다. 방문 한 후에 왼쪽 아이 가 비어 있 지 않 으 면 같은 규칙 에 따라 왼쪽 트 리 를 방문 할 수 있 습 니 다.왼쪽 트 리 에 접근 할 때 오른쪽 트 리 에 접근 합 니 다.따라서 그 처리 과정 은 다음 과 같다.
임의의 노드 P:
1) 결산 P 에 접근 하고 결산 P 를 창고 에 넣는다.2) 결산 P 의 왼쪽 아이 가 비어 있 는 지 여 부 를 판단 하고, 만약 비어 있 으 면, 결산 점 을 가 져 와 서 출고 작업 을 하고, 결산 점 의 오른쪽 아 이 를 현재 결산 점 P 로 설정 하여 1 로 순환 합 니 다).비어 있 지 않 으 면 P 의 왼쪽 아 이 를 현재 노드 P 로 설정 합 니 다.3) P 가 NULL 이 고 스 택 이 비어 있 을 때 까지 옮 겨 다 니 기 가 끝 납 니 다.
void preOrder2(BinTree *root) //
{
stack s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<data< s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
2. 중 서 는 중 서 를 옮 겨 다 니 며 '왼쪽 아이 - 뿌리 결산 점 - 오른쪽 아이' 의 순서에 따라 방문 합 니 다.
1. 귀속 실현
void inOrder1(BinTree *root) //
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<data< inOrder1(root->rchild);
}
}
2. 비 재 귀적 실현 은 중간 순서 로 옮 겨 다 니 는 순서 에 따라 모든 결점 에 대해 왼쪽 아 이 를 우선 방문 하고 왼쪽 아이의 결점 은 하나의 결점 으로 볼 수 있 으 며 그 다음 에 왼쪽 아이의 결점 을 계속 방문 하여 왼쪽 아이의 결점 이 빈 결점 을 만 날 때 까지 방문 한 다음 에 같은 규칙 에 따라 오른쪽 자 나 무 를 방문 합 니 다.따라서 그 처리 과정 은 다음 과 같다.
임의의 노드 P 에 대해,
1) 왼쪽 아이 가 비어 있 지 않 으 면 P 를 창고 에 넣 고 P 의 왼쪽 아 이 를 현재 P 로 설정 한 다음 현재 노드 P 를 동일 하 게 처리 합 니 다.2) 왼쪽 아이 가 비어 있 으 면 스 택 꼭대기 요 소 를 가 져 와 스 택 작업 을 하고 이 스 택 꼭대기 결산 점 을 방문 한 다음 에 현재 P 를 스 택 꼭대기 결산 점 의 오른쪽 아이 로 설정 합 니 다.3) P 가 NULL 이 고 스 택 이 비어 있 을 때 까지 스 트 리밍 이 끝 납 니 다.
void inOrder2(BinTree *root) //
{
stack s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<data< s.pop();
p=p->rchild;
}
}
}
3. 후 서 를 옮 겨 다 니 며 '왼쪽 아이 - 오른쪽 아이 - 뿌리 결산 점' 의 순서에 따라 방문 합 니 다.
1. 귀속 실현
void postOrder1(BinTree *root) //
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
cout<data< }
}
2. 비 재 귀 실현 후 순차 적 으로 옮 겨 다 니 는 비 재 귀 실현 은 세 가지 옮 겨 다 니 는 방식 중에서 가장 어 려 운 것 이다.뒷 순 서 를 옮 겨 다 니 면서 왼쪽 아이 와 오른쪽 아이 가 모두 방문 되 었 고 왼쪽 아이 가 오른쪽 아이 앞에서 방문 해 야 뿌리 결산 점 을 방문 할 수 있 기 때문에 절차 의 통제 에 어 려 운 문 제 를 가 져 왔 다.다음은 두 가지 사고방식 을 소개 한다.
첫 번 째 사고방식: 임의의 결점 P 에 대해 창고 에 넣 고 왼쪽 나 무 를 따라 왼쪽 아이의 결점 이 없 을 때 까지 계속 아래 를 수색 한다. 이때 이 결점 은 창고 꼭대기 에 나타 나 지만 이 때 는 창고 에서 나 와 방문 할 수 없 기 때문에 오른쪽 아 이 는 방문 할 수 있다.그 다음 에 똑 같은 규칙 에 따라 오른쪽 트 리 를 똑 같이 처리 하고 오른쪽 아 이 를 방문 할 때 이 결산 점 은 스 택 꼭대기 에 나타 나 면 스 택 에서 나 와 방문 할 수 있 습 니 다.이렇게 하면 정확 한 방문 순 서 를 보장 할 수 있다.이 과정 에서 모든 결산 점 이 두 번 씩 스 택 꼭대기 에 나타 나 고 두 번 째 로 스 택 꼭대기 에 나타 날 때 만 방문 할 수 있 음 을 알 수 있다.따라서 이 결점 이 창고 꼭대기 에 처음 나타 난 것 인지 변 수 를 하나 더 설정 해 야 한다.
void postOrder2(BinTree *root) //
{
stack s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) // ，
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //
{
cout<btnode->data< p=NULL;
}
}
}
}
두 번 째 사고방식: 뿌리 결점 이 왼쪽 아이 와 오른쪽 아이 가 방문 한 후에 야 방문 할 수 있 기 때문에 임의의 결점 P 에 대해 먼저 창고 에 넣 어야 한다.P 가 왼쪽 아이 와 오른쪽 아이 가 존재 하지 않 는 다 면 직접 방문 할 수 있 습 니 다.또는 P 는 왼쪽 아이 나 오른쪽 아이 가 존재 하지만 왼쪽 아이 와 오른쪽 아이 가 모두 방문 되 었 으 면 이 노드 를 직접 방문 할 수 있 습 니 다.상기 두 가지 상황 이 아니라면 P 의 오른쪽 아이 와 왼쪽 아 이 를 순서대로 창고 에 넣 으 면 창고 꼭대기 요 소 를 찾 을 때마다 왼쪽 아이 가 오른쪽 아이 앞에서 방문 되 고 왼쪽 아이 와 오른쪽 아 이 는 모두 뿌리 노드 앞에서 방문 된다.
void postOrder3(BinTree *root) //
{
stack s;
BinTree *cur; //
BinTree *pre=NULL; //
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<data< s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
4. 전체 프로그램의 완전한 코드
#include
#include
#include
using namespace std;
typedef struct node
{
char data;
struct node *lchild,*rchild;
}BinTree;
typedef struct node1
{
BinTree *btnode;
bool isFirst;
}BTNode;
void creatBinTree(char *s,BinTree *&root) // ，s A(B,C(D,E))
{
int i;
bool isRight=false;
stack s1; //
stack s2; //
BinTree *p,*temp;
root->data=s[0];
root->lchild=NULL;
root->rchild=NULL;
s1.push(root);
i=1;
while(i {
if(s[i]=='(')
{
s2.push(s[i]);
isRight=false;
}
else if(s[i]==',')
{
isRight=true;
}
else if(s[i]==')')
{
s1.pop();
s2.pop();
}
else if(isalpha(s[i]))
{
p=(BinTree *)malloc(sizeof(BinTree));
p->data=s[i];
p->lchild=NULL;
p->rchild=NULL;
temp=s1.top();
if(isRight==true)
{
temp->rchild=p;
cout<data< }
else
{
temp->lchild=p;
cout<data< }
if(s[i+1]=='(')
s1.push(p);
}
i++;
}
}
void display(BinTree *root) //
{
if(root!=NULL)
{
cout<data;
if(root->lchild!=NULL)
{
cout< display(root->lchild);
}
if(root->rchild!=NULL)
{
cout< display(root->rchild);
cout< }
}
}
void preOrder1(BinTree *root) //
{
if(root!=NULL)
{
cout<data< preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
void inOrder1(BinTree *root) //
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<data< inOrder1(root->rchild);
}
}
void postOrder1(BinTree *root) //
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
cout<data< }
}
void preOrder2(BinTree *root) //
{
stack s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<data< s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
void inOrder2(BinTree *root) //
{
stack s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<data< s.pop();
p=p->rchild;
}
}
}
void postOrder2(BinTree *root) //
{
stack s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) // ，
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //
{
cout<btnode->data< p=NULL;
}
}
}
}
void postOrder3(BinTree *root) //
{
stack s;
BinTree *cur; //
BinTree *pre=NULL; //
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<data< s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
int main(int argc, char *argv[])
{
char s[100];
while(scanf("%s",s)==1)
{
BinTree *root=(BinTree *)malloc(sizeof(BinTree));
creatBinTree(s,root);
display(root);
cout< preOrder2(root);
cout< inOrder2(root);
cout< postOrder2(root);
cout< postOrder3(root);
cout< }
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
