데이터 구조 와 알고리즘 분석 수확 총화 제6 장 트 리

솔직히 책 에 빈 필 기 를 보 니 선생님 이 이 장 을 말 하지 않 은 줄 알 았 다. 만 료 말 시험 범위 에 이 장 이 있 는 것 을 보 니 또 자기가 수업 할 때 물 을 젓 는 것 같다 는 것 을 깨 달 았 다.보 니 내용 이 많 지 않 아서 다행히 10 페이지 가 끝났다.중점: 1. 나무의 앞 순서 (뿌리) 를 배 워 서 옮 겨 다 니 고, 뒤 순 서 는 옮 겨 다 니 며, 이 진 트 리 와 차이 가 많 지 않다.중간 순 서 를 파악 할 필요 가 없습니다. 예 를 들 어 앞 순 서 는 인쇄 트 리 의 노드 를 옮 겨 다 닙 니 다.

void printhelp(GTNode<E>*root){
  if(root->isLeaf())cout<<"Leaf:";
  else cout<<"Internal:";
  cout<<root->value()<<"
";
  //        ，          ，            next    NULL  
  for (GTNode<E>temp=root->leftmostChild();temp!=NULL;temp->rightSibling())
  printhelp(temp);
}

2. 부모 지침 표현법: 각 결점 은 하나의 지침 역 만 저장 하고 부모 의 결점 을 가리 키 며 서로 교차 하지 않 는 집합 에 대해 두 가지 조작 을 제공 하고 자 합 니 다. (1) 두 결점 이 같은 집합 에 있 는 지 판단 합 니 다. FIND (2) 두 집합 을 병합 합 니 다. UNION 과 알고리즘 은 하나의 트 리 로 하나의 집합 을 대표 하고 함수 differ 를 통 해 하나의 등가 쌍 중의 두 요소 가 같은 나무 에 있 는 지 확인 합 니 다.만약 그렇다면, 그것들 은 이미 같은 등가 류 에 있 기 때문에 변동 할 필요 가 없다.그렇지 않 으 면 UNION 으로 두 개의 등가 류 를 합 친다.(어떤 두 결점 사이 에 하나의 통로 가 있 는데 이 두 결점 이 등가 라 고 생각 합 니 다. 등가 변 즉 연 결 된 변 집합 부분 을 연결 지점 이 라 고 부 릅 니 다. 등가 대 는 그림 속 변 의 집합 이 고 집합 목적 은 결점 집합 을 연결 지점 을 대표 하 는 불 교차 집합 으로 신속하게 나 누 는 것 이 며 계산 그림 의 최소 생 성 트 리 에 사용 하 는 Kruskal 알고리즘 입 니 다)등가 류 처리 와 경로 압축 을 잘 모 르 고 전략 적 으로 포기 하 였 습 니 다. 3. 나무의 실현: (1) 자 결점 표 표시 법 P136 하 표 Value Par.. (2) 왼쪽 자 결점 / 오른쪽 형제 결점 표시 법 하 표 left value par right (3)동적 결점 표현법 은 링크 표현법 을 트 리 i. 나무의 동적 결점 표현법 val size 로 확장한다.모든 자결 점 은 하나의 빈 영역 - 지침 의 지침 에 의 해 가리 키 고 있 습 니 다.이 진 트 리 - > 나무: 즉, 반 과정, 오른쪽 방향 으로 아버지 와 연결, 형제 와 부 러 짐 (4) 이 진 트 리 - > 숲: 뿌리 오른쪽 나무 가 모두 부 러 짐 5. K 진 트 리: 이 진 트 리 와 유사 6. 나무의 순서 표시 법

         A
   B         C
     D     E    F
          G    H I

i. 가정 / 대표 빈 포인터 NULL: AB / D / CEG / / / FH / / I / / ii. A 'B' / DC 'E' G / F 'HI (무' 표시 무 자 결점) ii. 11001000

   
         R
    A          B
  C D E        F         

ii. 특수 표기) 로 자 결점 표 의 끝 을 표시 합 니 다. 모든 잎 결점 뒤에 하나 가 있 습 니 다.) 자 결점 이 없 기 때 문 입 니 다. 만약 에 한 자 결점 이 아버지 결점 의 마지막 자 결점 이 라면 그 뒤에 두 개 이상 연속 적 인) RAC) D) E) F 뒤에 세 개가 있 습 니 다. 이것 은 잎 결점 이자 B 의 가장 오른쪽 자 나무의 마지막 결점 이기 때 문 입 니 다.동시에 R 의 가장 오른쪽 나무의 마지막 결산 점 이다.