두 갈래 나무의 매 결점의 왼쪽 아이와 오른쪽 아이를 교환하여 ~2020.8.13~ 학습노트

제목 설명:


두 갈래 체인 시계를 두 갈래 나무의 저장 구조로 삼아 두 갈래 나무의 각 결점의 왼쪽 아이와 오른쪽 아이를 교환한다.

형식 입력:


두 갈래 나무의 순서를 입력하십시오.알림: 두 갈래 나무의 순서 서열은 문자열입니다. 문자가'#'이면 이 두 갈래 나무는 빈 나무입니다. 그렇지 않으면 해당 결점의 데이터 요소입니다.

출력 형식:


출력은 두 줄이 있습니다. 첫 번째 줄은 원 두 갈래 나무의 중차 역행 서열입니다.두 번째 줄은 교환된 두 갈래 나무의 중차 역행 서열이다.

샘플 입력:


ABC##DE#G##F###

내보내기 예제:


CBEGDFA AFDGEBC

확인:


두 갈래 트리 구조 정의:
struct node{
     
 char data;
 node *lchild,*rchild;
};

두 갈래 트리의 귀속 함수를 만들고 트리 열의 주소 찾기 문자를 주의하십시오.
void SetBiTree(node* &t){
     
 char c;
 cin>>c;
 if(c=='#'){
     
  t = NULL;
 }
 else{
     
  t = new node;
  t->data = c;
  SetBiTree(t->lchild);
  SetBiTree(t->rchild);
 }
}

중역:
void Traverse(node *t){
     
 if(t == NULL) return;
 Traverse(t->lchild);
 cout<<t->data;
 Traverse(t->rchild);
}

두 갈래 나무의 모든 결점을 교환하는 좌우 아이: 마찬가지로 귀속적인 사상을 사용했다. 만약에 좌우 아이가 모두 비어 있다면 처리하지 않고 그렇지 않으면 교환을 하고 각각 왼쪽 아이의 결점과 오른쪽 아이의 결점에 들어간다.이 교환은 C++가 가지고 있는 swap 교환 도구를 사용합니다. iostream 헤더 파일과 std 이름 공간이 필요합니다.
void change(node* &t){
     
 if( t->lchild == NULL && t->rchild == NULL ){
     
  return;
 }
 
 swap(t->lchild,t->rchild);
 if(t->lchild){
     
  change(t->lchild);
 }
 if(t->rchild){
     
  change(t->rchild);
 }
}

주 함수:
int main()
{
     
 node *root;
 SetBiTree(root);
 Traverse(root);
 cout<<endl;
 change(root);
 Traverse(root);
 return 0;
}

성공 AC

좋은 웹페이지 즐겨찾기