이 진 트 리 의 구축 과 세 가지 옮 겨 다 니 기

이 진 트 리 의 구축 과 옮 겨 다 니 기 작업 (1) 이 진 트 리 의 구축 순서 에서 이 진 트 리 를 옮 겨 다 니 며 만 듭 니 다. 이 진 트 리 의 앞 순서 에서 첫 번 째 요 소 는 항상 나무의 뿌리 노드 의 값 입 니 다.중간 순서 로 서열 을 옮 겨 다 니 며 왼쪽 서브 트 리 의 노드 값 은 뿌리 노드 의 값 왼쪽 에 있 고 오른쪽 서브 트 리 의 노드 값 은 뿌리 노드 의 값 오른쪽 에 있 습 니 다.재 귀적 해법: (1) 앞 순서 가 비어 있 거나 중간 순서 가 비어 있 거나 노드 개수 가 0 보다 적 으 면 NULL 로 돌아 갑 니 다.(2) 루트 노드 를 만 듭 니 다.앞 순 서 를 옮 겨 다 니 는 첫 번 째 데 이 터 는 바로 뿌리 노드 의 데이터 입 니 다. 중간 순 서 를 옮 겨 다 니 면서 뿌리 노드 의 위 치 를 찾 으 면 왼쪽 서브 트 리 와 오른쪽 서브 트 리 의 앞 순서 와 중간 순 서 를 알 수 있 고 왼쪽 서브 트 리 를 재건 할 수 있 습 니 다.
중간 순서 후 순서 로 이 진 트 리 를 만 듭 니 다. 이 진 트 리 의 순서 로 서열 을 옮 깁 니 다. 왼쪽 서브 트 리 의 노드 값 은 뿌리 노드 의 값 왼쪽 에 있 고 오른쪽 서브 트 리 의 노드 값 은 뿌리 노드 의 값 오른쪽 에 있 습 니 다.뒷 순 서 는 시퀀스 에서 왼쪽 하위 트 리 의 노드 값 은 오른쪽 하위 트 리 노드 의 값 왼쪽 에 있 고 오른쪽 하위 트 리 의 노드 값 은 뿌리 노드 의 값 왼쪽 에 있 습 니 다.
재 귀적 해법: (1) 중간 순서 가 비어 있 거나 뒷 순서 가 비어 있 거나 노드 개수 가 0 보다 적 으 면 NULL 로 돌아 갑 니 다.(2) 루트 노드 를 만 듭 니 다.뒷 순 서 를 옮 겨 다 니 는 마지막 데 이 터 는 바로 뿌리 노드 의 데이터 입 니 다. 중간 순 서 를 옮 겨 다 니 면서 뿌리 노드 의 위 치 를 찾 으 면 왼쪽 서브 트 리 와 오른쪽 서브 트 리 의 중간 순서 와 뒷 순 서 를 각각 알 수 있 고 왼쪽 서브 트 리 를 재건 할 수 있 습 니 다.
(2) 이 진 트 리 의 옮 겨 다 니 는 순서: a. 이 진 트 리 가 비어 있 으 면 빈 작업 b. 이 진 트 리 가 비어 있 지 않 으 면 뿌리 노드 에 접근 하고 앞 순 서 는 왼쪽 트 리 를 옮 겨 다 니 며 앞 순 서 는 오른쪽 트 리 를 옮 겨 다 닌 다. a. 이 진 트 리 가 비어 있 으 면 빈 작업 을 한다.b. 이 진 트 리 가 비어 있 지 않 으 면 중간 순 서 는 왼쪽 하위 트 리 를 옮 겨 다 니 고 뿌리 노드 에 접근 합 니 다. 중간 순 서 는 오른쪽 하위 트 리 를 옮 겨 다 니 며 순서대로 옮 겨 다 닙 니 다. a. 이 진 트 리 가 비어 있 으 면 빈 작업 b. 이 진 트 리 가 비어 있 지 않 으 면 왼쪽 하위 트 리 를 옮 겨 다 니 고 뒤의 순 서 는 오른쪽 하위 트 리 를 옮 겨 다 니 며 뿌리 노드 의 순서 에 접근 합 니 다. 넓 은 검색 에 해당 하고 대기 열 을 사용 하여 이 루어 집 니 다.대기 열 을 초기 화하 고 루트 노드 를 대기 열 에 눌 러 넣 습 니 다.대기 열 이 비어 있 지 않 으 면 다음 과 같은 작업 을 수행 합 니 다. 한 노드 를 팝 업 하고 접근 합 니 다. 왼쪽 노드 나 오른쪽 노드 가 비어 있 지 않 으 면 대기 열 에 눌 러 넣 습 니 다.이전에 책 에 묘 사 된 대로 재 귀 를 통 해 이 진 트 리 를 만 든 후에 입력 할 때 순환 하 는 것 을 발견 하면 자신의 프로그램 이 잘못 되 었 다 고 생각 한 후에 자신의 프로그램 이 잘못 되 지 않 았 고 자신 이 이 진 트 리 에 대한 정의 가 깊 지 않다 는 것 을 알 게 되 었 다.프로그램 에서 입력 은 엄격하게 정확 한 순서에 따라 야 끝 날 수 있 습 니 다. 여기 서 이 진 트 리 의 한 가지 성질 을 사용 해 야 합 니 다. 즉, n 개의 노드 가 있 는 이 진 트 리 에 대해 n + 1 개의 공역 이 있 습 니 다. 여기 서 n 개의 요 소 를 입력 하면 n + 1 개의 \ # 가 있어 야 교체 과정 을 끝 낼 수 있 습 니 다. 예 를 들 어 abcd \ # \ # \ # # \ # # # 를 입력 해 야 완전히 끝 날 수 있 습 니 다. 재 귀적 호출 프로그램 은 매우 간결 합 니 다.프로그램 이 작고 효율 적 인 요구 가 높 지 않 은 상황 에서 재 귀 를 적 절 히 사용 하 는 것 은 가 부 를 말 하지 않 는 다.ACM 에 서 는 재 귀 를 적 절 히 사용 하면 Maybe 성적 이 좋 을 것 입 니 다.

#include"stdio.h"
#include"stdlib.h"
#include"conio.h"
#define ElemType char
/*writer Liu*/
typedef struct Node
{
        char data;
        struct Node* Lchild;
        struct Node* Rchild;
        struct Node* parent;    
}BiTNode,*BiTree;
BiTree CreateBiTree(){
    char ch;
    BiTree T;
    scanf("%c",&ch);
//  getchar();
    if(ch=='#') T=NULL;         /*                   .             ,      n       ,  n+1   ,           n   ,      n+1 #        .*/ 
    else                        /*  1234#####    ！*/ 
    {
        T =(BiTree)malloc(sizeof(BiTNode));
        T->data = ch;
        T->Lchild = CreateBiTree();
        T->Rchild = CreateBiTree();

    }
    return T;//return root node 
}
//       
 void PreOrderTraverse(BiTree T)
 {
    if(T)
    {
        printf("%c",T->data);
        PreOrderTraverse(T->Lchild);
        PreOrderTraverse(T->Rchild);
     }
 }
 //       
 void InOrderTraverse(BiTree T)
 {
    if(T)
    {
        InOrderTraverse(T->Lchild);
        printf("%c",T->data);
        InOrderTraverse(T->Rchild);
     }
  } 
  //       
  void PostOrderTraverse(BiTree T)
  {
    if(T)
    {
        PostOrderTraverse(T->Lchild);
        PostOrderTraverse(T->Rchild);
        printf("%c",T->data);
      }
   } 

int main()
 {
    BiTree T;
    T = CreateBiTree();
    PreOrderTraverse(T);
    printf("
");

    InOrderTraverse(T); 
    printf("
"); 
    PostOrderTraverse(T); 

 }