데이터 구조 제5 장 소결

내용 소결
제5 장 에서 배 웠 습 니 다. 나무 (재 귀 사상 이 가장 많 습 니 다) 는 주로 이 진 트 리 의 각종 알고리즘 과 하 프 만 트 리 의 분석 을 배 웠 습 니 다.
1) 이 진 트 리 의 여러 가지 성질 감각 은 이 장 에서 비교적 중요 하 다. 첫 번 째 는 이 진 트 리 의 l 층 에 많 게 는 2 ^ (i - l) 개의 결점 이 있 고, 두 번 째 는 깊이 가 K 인 이 진 트 리 는 많 게 는 2k - 1 개의 결점 이 있 으 며, 세 번 째 는 n0 (도 0 의 결점) = n2 (도 2 의 결점) + 1 (또 하나의 점: 결점 총수 = 분기 총수 + 1) 이다.
 
2) 하프 만 트 리 (권한 경로 길이 가 가장 짧 은 트 리)의 구조: 방법: 먼저 두 개의 가중치 가 가장 작은 것 을 결점 으로 합병 하여 하나의 나무의 가 지 를 형성 한 다음 에 이 두 노드 의 가중치 를 뿌리 노드 의 가중치 로 더 한 다음 에 아버지 노드 를 다른 최소 가중치 와 합병 시 켰 다. 방법 은 예전 과 마찬가지 로 뒤의 것 은 이런 식 으로 유추 하여 소유권 치 를 모두 사용 할 때 까지 최종 적 으로 하 프 만 나 무 를 구성 했다.. 권한 경로 길이 WPL = 모든 잎 결점 은 각각 나무 뿌리 에서 그들의 경로 길이 (즉 변수) 를 곱 한 다음 에 덧붙인다.
 
2. 실수 하기 쉽다.
1. 나 무 를 처음 배 웠 을 때 나 는 잎의 결점 (잎의 결점) 과 결점 의 차 이 를 구분 하지 못 했다. 이 제 는 잎의 결점 은 아이의 결점 이 없 는 것 을 가리 키 고 결점 은 잎의 결점 을 포함 하 며 결점 은 아이 가 있 을 수 있다 는 것 을 알 게 되 었 다.
 
2. 이 진 트 리 의 선 순위, 중 순위, 후 순위 순 서 는 헷 갈 리 기 쉽 습 니 다. 먼저 뿌리 를 옮 겨 다 니 고 왼쪽 하위 트 리 를 옮 겨 다 니 며 마지막 으로 오른쪽 하위 트 리 를 옮 겨 다 니 는 것 입 니 다. 중 순 서 는 먼저 왼쪽 에서 마지막 으로 오른쪽 입 니 다. 후 순 서 는 먼저 왼쪽 에서 오른쪽 마지막 뿌리 입 니 다.(형용 하기 어 려 울 것 같 지만 나 자신 은 알 고 있다)
 
3. int n; cin > > n; int * a = new int [n]; / / 쌓 기 신청 공간 에서 길이 n 의 int 유형 배열, 문법 정확 (인공 분배, 인공 회수)
  int n; cin >> n; int a[n] ; // 배열 을 정의 할 때 배열 의 길 이 는 변수 이지 만 n 의 값 은 스 택 공간의 크기 를 초과 할 수 있 습 니 다. C 언어 는 정확 하지만 C + + 는 지원 되 지 않 습 니 다.
 
4、typedef TElemType SqBiTree[MAXTSIZE];
// 새로운 유형 을 정 의 했 습 니 다. 이름 은 SqBiTree 입 니 다. 그 본질은 하나의 배열 입 니 다. 배열 요소 유형 은 TElem Type 이 고 길 이 는 MAXTSIZE 입 니 다.
예 를 들 어 int a [100]; int b [100] typedef int Num [100]; Num a, b;
 
3. 중점 알고리즘:
1. 스 트 리밍 알고리즘: (이 진 트 리 기반)
층 차 를 편력 하 다

typedef struct
{
    int lch;
    int rch;
}Node;

typedef struct
{
    Node data[10];
    int root;//    
}Tree;

void LevelOrder(Tree T)
{
    queue<int> Q;//   
    Q.push(T.root);//     
    int k;
    bool flag =false;
    while(!Q.empty())//       
    {
        k = Q.front();//     
        Q.pop();//       （       ） 
        if(T.data[k].lch==-1 && T.data[k].rch==-1)//    
        {
          if(flag==false)
          { 
            cout << k;
            flag =true;
          } 
          else cout << " "<< k;
        }
        else 
        {
            if(T.data[k].lch!=-1) Q.push(T.data[k].lch);
             if(T.data[k].rch!=-1) Q.push(T.data[k].rch);
        }
    } 
}

중간 순서 로 옮 겨 다 닌 다.

void InOrder(BiTree T)//       
{
    if(T)
    {
        InOrder(T->lchild);//      ①
        cout << T->data;//      ②
        InOrder(T->rchild);//      ③
        
    }
}

선서 와 후 서 는 중 서 와 차이 가 많 지 않 으 며 좌우 자 수 를 옮 겨 다 니 는 위치 가 다르다 (① ② ③ 다르다). 선서: ② ① ③ 후 순 ① ③ ②
 
2. 먼저 이 진 트 리 만 들 기

void creat(BiTree &T)
{
    T=new BiTNode; 
    cin >> T->data;
    if(T->data=='#') T= NULL;
    if(T!=NULL)//  T    
    {
    creat(T->lchild);//      
    creat(T->rchild);//      
    } 
}

3. 아이 부모 표현 법
 

typedef struct CNode//     
{
    int child;//     
    CNode* next;
}CNode;
typedef struct PNode//     
{
    int parent;
    char data; 
    CNode* fchild;//             
}PNode;
typedef struct
{
    PNode a[MAXSIZE];
    int root;//      
    int n;//     
}Tree;

 
4. 아이 형제 표현 법
 

typedef struct CSNode{
    int data;
    CSNode* firstchild;//  
    CSNode* nextsibling;//  
}CSNode;

5. 하 프 만 트 리 노드 유형 정의
 

typedef struct { 
    int weight; //  
   int parent, lch, rch;
 } *HuffmanTree;

 
 
소감
트 리 라 는 장 은 보기 만 하고 코드 를 쓰 지 않 으 면 이해 하기 쉬 운 것 같 습 니 다. 하지만 정말 코드 를 쓸 때 유형 정의 와 재 귀적 인 부분 (특히 트 리 를 만 드 는 함수) 은 손 이 닿 지 않 을 때 가 있 습 니 다. 자신 이 많이 써 야 할 수도 있 습 니 다. 그리고 이번 작은 팀 의 합작 을 통 해 기억 하지 못 하 는 지식 이 있 습 니 다 (예 를 들 어 위 에서 틀 리 기 쉬 운 점 3).그리고 한시 적 인 임 무 를 수행 할 때 는 자신 이 익숙 하지 않 은 것 (링크) 을 사용 하지 않 는 것 이 좋다.