C 언어 이 진 트 리 의 몇 가지 옮 겨 다 니 는 방법 에 대한 상세 한 설명 과 인 스 턴 스

이 진 트 리 의 개념
이 진 트 리 는 각 노드 마다 최대 두 개의 키 트 리 가 있 는 트 리 저장 구조 다.먼저 위의 그림 을 그 려 서 뒤의 분석 을 편리 하 게 하 다.

 1.이 진 트 리 와 완전 이 진 트 리 
위의 그림 은 전형 적 인 이 진 트 리 인 데 그 중에서 왼쪽 그림 은 만 이 진 트 리 라 고도 부 르 고 오른쪽 은 완전 이 진 트 리 이다.그런 후에 우 리 는 이 진 트 리 가 완전히 이 진 트 리 라 는 결론 을 얻 을 수 있 지만 반대로 꼭 그렇지 는 않다.만 이 진 트 리 의 정 의 는 잎 결 점 을 제외 하고 다른 결 점 은 아이들 이 모두 있 고 깊이 가 k 인 만 이 진 트 리 이 며 결 점 수 는 2 의 k 제곱 1 이다.완전 이 진 트 리 는 모든 결점 이 깊이 가 k 인 만 이 진 트 리 에서 번호 가 1 에서 n 까지 일일이 대응 하 는 것 이다.
 2 나무의 깊이
나무의 가장 큰 층 차 는 바로 깊이 이다.예 를 들 어 위의 그림,깊이 는 4 이다.깊이 가 k 인 나 무 는 가지 고 있 는 최대 결 점 수 는 2 의 k 차방 에서 1 을 줄 인 다 는 것 을 쉽게 알 수 있다.
 3 나무의 아이,형제,부모
위의 그림 에서 B,C 는 A 의 아이 이 고 B,C 는 서로 형제 이 며 A 는 B,C 의 양친 이다.
 2.이 진 트 리 를 만 드 는 방법
먼저 이 진 트 리 의 저장 구 조 를 말 해 보 세 요.많은 다른 모델 과 마찬가지 로 순서 와 체인 두 가지 방식 도 있 습 니 다.전 자 는 간단 하지만 공간 을 낭비 하 는 문제 가 존재 합 니 다.예 를 들 어 다음 그림 의 이 진 트 리 는 순서대로 저장 합 니 다(0 은 비어 있 고 하위 트 리 가 없습니다).
1 2 3 4 5 6 7 0 0 0 0 8 0 0 0

 공간 낭비 되 는 거 아니 야?
 체인 구 조 는 다음 과 같이 정의 할 수 있다.

typedef struct _BiTNode 
{ 
  int data; 
  _BiTNode *leftChild; 
  _BiTNode *rightChild; 
}BiTNode, *pBiTree; 

그 다음 에 함수 하 나 를 써 서 이 진 트 리 를 만 들 수 있 습 니 다.과정 은 콘 솔 에 a 를 입력 하여 현재 이 층 을 종료 하고 이 층 에 좌우 아 이 를 만 들 지 않 겠 다 는 것 입 니 다.다른 알파벳 을 입력 하면 계속 만 들 겠 습 니 다.예 를 들 어 아래 의 입력 시퀀스:

 다음 구조의 이 진 트 리 를 만 들 었 습 니 다.

 각 노드 의 수 치 는 100 보다 작은 숫자 를 무 작위 로 생 성 한다.동시에 나 도 자동 명령 시퀀스 함 수 를 써 서 테스트 하기 편리 하고 수 동 으로 입력 하지 않 아 도 된다.비 자동 과 자동 으로 생 성 된 함 수 는 다음 과 같다.

//     ,      
int CreateBiTree(pBiTree *root) 
{ 
  char ch = 0; 
  fflush(stdin); 
  if ((ch = getchar()) == 'a')//       
  { 
    *root = NULL; 
  } 
  else 
  { 
    *root = (BiTNode *)malloc(sizeof(BiTNode)); 
    if (!(*root)) 
    { 
      return RET_ERROR; 
    } 
    (*root)->data = GetRandom(); 
    CreateBiTree(&(*root)->leftChild); 
    CreateBiTree(&(*root)->rightChild); 
  } 
  return RET_OK; 
} 
 
int g_i = 0; 
//     ,    ，     
int CreateBiTreeAuto(pBiTree *root) 
{ 
  char szOrder[] = "bbaabaa"; 
  char ch = 0; 
  if (szOrder[g_i++] == 'a')//       
  { 
    *root = NULL; 
  } 
  else 
  { 
    *root = (BiTNode *)malloc(sizeof(BiTNode)); 
    if (!(*root)) 
    { 
      return RET_ERROR; 
    } 
    (*root)->data = GetRandom(); 
    CreateBiTreeAuto(&(*root)->leftChild); 
    CreateBiTreeAuto(&(*root)->rightChild); 
  } 
  return RET_OK; 
} 

트 리 플 순서
선착순
먼저 순 서 를 옮 겨 다 니 는 것 은 먼저 뿌리 노드 에 접근 한 다음 에 왼쪽 서브 트 리,그리고 오른쪽 서브 트 리 입 니 다.예 를 들 어 그림 1 의 오른쪽 그림,먼저 옮 겨 다 니 는 출력 은 다음 과 같 습 니 다.
A,B,D,H,I,E,J,K,C,F,G
위의 사상 에 따 르 면 재 귀적 인 형식 으로 먼저 옮 겨 다 니 는 코드 를 쓰기 쉽다.

//     
int PreOrderVisitTree(pBiTree T, VisitType pFuncVisit) 
{ 
  if (T) 
  { 
    (*pFuncVisit)(T->data); 
    if (PreOrderVisitTree(T->leftChild, pFuncVisit) == RET_OK) 
    { 
      if (PreOrderVisitTree(T->rightChild, pFuncVisit) == RET_OK) 
      { 
        return RET_OK; 
      } 
    } 
    return RET_ERROR; 
  } 
  else 
  { 
    return RET_OK; 
  } 
} 

중간 순서 와 뒷 순 서 를 옮 겨 다 닙 니 다.
선조의 경험 이 있 으 면 이 두 가 지 는 잘 이해 할 수 있다.중 서 는 먼저 왼쪽 나 무 를 방문 한 다음 에 뿌리 가 맺 힌 다음 에 오른쪽 나 무 를 방문 하고 그 다음 에 왼쪽 나 무 를 방문 한 다음 에 오른쪽 나 무 를 방문 한 다음 에 뿌리 가 맺 힌 다.코드 가 더 쉬 워 요.호출 순 서 를 바 꾸 기만 하면 돼 요.
하지만 나 에 게 는 비 재 귀적 인 실현 을 제시 했다.재 귀 는 분명 하지만 효율 이 낮은 문제 가 존재 합 니 다.재 귀 하지 않 는 방안 은 스 택 구조 로 결산 정 보 를 저장 하고 스 택 방문 을 통 해 이 진 트 리 를 옮 겨 다 닙 니 다.창고 꼭대기 에 있 는 바늘 이 비어 있 지 않 을 때 왼쪽 나무,즉 왼쪽 나무 뿌리의 바늘 이 창고 에 들어간다.창고 꼭대기 바늘 이 비어 있 을 때 는 윗 층 으로 물 러 나 야 합 니 다.왼쪽 나무 에서 돌 아 왔 다 면 현재 층,즉 창고 꼭대기 의 뿌리 바늘 결점 을 방문 하 십시오.오른쪽 하위 트 리 에서 돌아 오 면 현재 층 이 옮 겨 다 니 고 있 음 을 설명 합 니 다.계속 스 택 을 반환 합 니 다.코드 는 다음 과 같 습 니 다:

//    ,       
int InOrderVisitTree(pBiTree T, VisitType pFuncVisit) 
{ 
  ponyStack binaryTreeStack; 
  InitStack(&binaryTreeStack, 4); 
  Push(&binaryTreeStack, &T); 
  pBiTree pTempNode; 
 
  while (!IsEmptyStack(binaryTreeStack)) 
  { 
    while((GetTop(binaryTreeStack, &pTempNode) == RET_OK) && (pTempNode != NULL)) 
    { 
      Push(&binaryTreeStack, &(pTempNode->leftChild)); 
    } 
    Pop(&binaryTreeStack, &pTempNode); 
    if (!IsEmptyStack(binaryTreeStack)) 
    { 
      Pop(&binaryTreeStack, &pTempNode); 
      (*pFuncVisit)(pTempNode->data); 
      Push(&binaryTreeStack, &(pTempNode->rightChild)); 
    } 
  } 
  return RET_OK; 
} 

코드 다운로드 주소:http://xiazai.jb51.net/201701/yuanma/BinaryTreeDemo-master(jb51.net).rar
읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!