프로그램 3 - 이 진 트 리 의 앞 뒤 층 차 를 옮 겨 다 닙 니 다.

정의 데이터 구조

typedef struct BiTree {
  int data;
  struct BiTree *lchild, *rchild;
} BiTree;

앞 순 서 를 편력 하 다.

void PreOder(BiTree *T) {
  if( T == null ) {
    return;
  }
  stack s;
  BiTree *t = T;
  while( t != null || !s.isEmpty() ) {
    if (t != null) {
      print(t->data);
      s.push(t);
      t = t->lchild;
    }
    else {
      t = s.pop();
      t = t->rchild;
    }
  }
}

중간 순서 로 옮 겨 다 닌 다.
중간 순서 가 옮 겨 다 니 는 비 재 귀 와 앞 순서 의 차이 가 많 지 않 으 니 다시 한 번 쓰 면 능숙 하 다.

void inOder(BiTree *T) {
  if ( T == null ) {
    return;
  }
  stack s;
  BiTree *t = T;
  while ( t != null || !s.isEmpty() ) {
    if (t != null) {
      s.push(t);
      t = t->lchild;
    }
    else {
      t = s.pop();
      print(t->data);
      t = t->rchild;
    }
  }
}

뒤 순 서 를 옮 겨 다 닌 다.
후 서 는 앞의 두 가지 에 비해 좀 복잡 하 다.두 개의 창 고 를 사용 하든지, 아니면 약간 복잡 하고 어 려 운 논리 가 필요 하 다.

void postOrder(BiTree *T) {
  if (T == null) {
    return;
  }
  stack s, out;
  BiTree *t = T;
  s.push(t);
  while( !s.isEmpty() ) {
    t = s.pop();;
    out.push(t);
    if (t->lchild != null) {
      s.push(t->lchild);
    }
    if (t->rchild != null) {
      s.push(t->rchild);
    }
  }
  while( !out.isEmpty() ) {
    t = out.pop();
    print(t->data);
  }
}

두 개의 스 택 을 사용 하면 논리 가 비교적 간단 하지만 메모리 가 조금 더 사용 되 었 습 니 다. 아래 코드 는 하나의 스 택 만 사용 하여 이 루어 집 니 다.

void postOrder(BiTree *T) {
  if ( T == null ) {
    return;
  }
  stack s;
  BiTree *t = T;
  BiTree *pre = null;
  while ( t != null || !s.isEmpty() ) {
    if (t != null) {
      s.push(t);
      t = t->lchild;
    }
    else if ( s.top()->rchild == pre) { pre = s.pop(); print(pre->data); } else { t = s.top()->rchild;
      pre = null;
    }
  }
}

이러한 실현 이 비교적 이해 하기 어 려 운 것 은 바로 이 pre 입 니 다. 이 pre 는 지난번 에 방문 한 노드 를 기록 하고 있 습 니 다. 프로그램 이 처음 실 행 했 을 때 자연 pre = null 입 니 다.스 택 꼭대기 요소 의 rchild 가 pre 와 같 을 때 스 택 꼭대기 요소 의 rchild 가 이미 방문 되 었 음 을 설명 합 니 다. 스 택 꼭대기 요 소 는 스 택 에서 나 올 수 있 습 니 다.pre 와 같 지 않 으 면 rchild 에 접근해 야 합 니 다.잊 지 마 세 요. 이 진 트 리 의 정 의 는 재 귀 정의 이 고 좌우 자 트 리 는 모두 이 진 트 리 입 니 다.이렇게 하면 s. top () - > rchild 를 T 로 보고 다시 실행 할 수 있 습 니 다.
차례차례 편력 하 다
층 차 를 옮 겨 다 니 며 사용 하면 스 택 이 아니 라 대기 열 입 니 다.

void levelOrder(BiTree *T) {
  if ( T == null ) {
    return;
  }
  queue q;
  BiTree *t = T;
  q.enQueue(t);
  while (!q.isEmpty()) {
    t = q.deQueue();
    print(t->data);
    if (t->lchild)
      q.enQueue(t->lchild);
    if (t->rchild)
      q.enQueue(t->rchild);
  }
}

층 차 를 옮 겨 다 니 는 것 이 비교적 간단 하 니, 아래 에 그 변 화 를 좀 해 보 자.요구: 한 층 한 층 인쇄 노드.이 때 는 아이의 노드 의 개 수 를 기록 해 야 한다.

void levelOrder(BiTree *T) {
  if (T == null) {
    return;
  }
  BiTree *t = T;
  queue q;
  int curCount = 1;
  int nextCount = 0;
  q.enQueue(t);
  while (!q.isEmpty()) {
    t = q.deQueue();
    print(t->data);
    curCount--;
    if(t->lchild) {
      q.enQueue(t->lchild);
      nextCount++;
    }
    if(t->rchild) {
      q.enQueue(t->rchild);
      nextCount++;
    }
    if(curCount == 0) {
      print("
");
      curCount = nextCount;
      nextCount = 0;
    }
  }
}