제5 장 학습 소결

제5 장 우 리 는 새로운 데이터 구조, 즉 나 무 를 배 웠 다.전에 배 운 내용 과 비교 하면 나 무 는 더욱 복잡 하 다 고 생각한다.
이 진 트 리 를 배 우 는 과정 에서 나무의 조작 과정 에서 많은 반복 적 인 조작 은 재 귀 를 통 해 이 루어 져 야 한다. 저 는 재 귀 하 는 사상 에 대해 더욱 깊이 알 게 되 었 습 니 다.
우리 도 많은 이 진 트 리 의 성질 을 배 웠 다. 예 를 들 어:
이 진 트 리 의 성질:
1: 이 진 트 리 의 i 층 에는 많아야 2 ^ (i - 1) 개의 결점 이 있다.
2: 깊이 가 k 인 이 진 트 리 는 많아야 2 ^ k - 1 개의 결점 이 있 습 니 다.
완전 이 진 트 리 의 성질:
1: 결점 i 의 자 결점 은 2 * i 와 2 * i + 1 이다.
2: 결점 i 의 부 결점 은 i / 2 
이 진 트 리 를 옮 겨 다 니 는 3 가지 방법 도 배 웠 다.
1: 뿌리 - > 왼쪽 트 리 - > 오른쪽 트 리
2: 가운데 순서: 왼쪽 하위 트 리 - > 뿌리 - > 오른쪽 하위 트 리
3: 뒤 순 옮 겨 다 니 기: 왼쪽 트 리 - > 오른쪽 트 리 - > 뿌리
이 진 트 리 의 저장 구 조 는 체인 구조 (링크 법 사용), 순서 구조 (배열 사용) 가 있 고 개인 적 으로 감각 순서 구 조 를 사용 하 는 것 이 더욱 편리 하 다.
호 프 만 트 리 의 구축 과 계산 도 배 웠 습 니 다.
(1) 각 노드 를 가중치 에 따라 작은 것 에서 큰 것 으로 정렬 한다.(2) 최소 가중치 의 두 노드 를 취하 고 부모 노드 를 이 두 노드 의 부모 로 새로 만 듭 니 다. 부모 노드 의 가중치 는 하위 노드 의 가중치 의 합 이 고 이 부모 노드 를 원래 의 대기 열 에 넣 습 니 다.(3) 대기 열 에 노드 가 하나 밖 에 없 을 때 까지 (2) 절 차 를 반복 합 니 다. 이 노드 는 루트 노드 입 니 다.
그룹 합작 에서 우리 팀 의 초기 코드 는 다음 과 같다.

#include
using namespace std;
typedef struct {//      
    int parent=-1;//          
    int k=0;//         
}Node;
typedef struct {//     
    Node data[100001];
    int root;//root     
}*tree, Tree;
void creattree(tree& T, int n)//   
{
    int m, a, b[100001] = { 0 };
    for (int i = 1; i <= n; i++)
    {
        cin >> m;
        if (m == 0)//         
            T->data[i].k = 1;
        else
        for (int k = 0; k < m; k++)
        {
            cin >> a;
            T->data[a].parent = i;
            b[a]=1;
        }
    }
    for (int i = 1; i <= n; i++)//       
        if (b[i] == 0)
        {
            T->root = i;
            T->data[i].parent = -1;
            break;
        }
}
void searchleaf(tree T, int n)//       
{
    int k = 0, m = 0, M = 0;
    for (int i = 1; i <= n; i++)
    {
        if (T->data[i].k == 1)//         
        {
            int a = i;
            while (T->data[a].parent != -1)//         
            {
                k++;
                a = T->data[a].parent;
            }
            if (k == n - 1)//  k           
            {
                M = i;
                break;
            }
            else if (k > m)
            {
                M = i;
                m = k;
            }
        }
        k = 0;
    }
    cout << M;
}
int main()
{
    tree T = new Tree;
    int n;
    cin >> n;
    creattree(T, n);
    if (n == 1)
        cout << 1;
    else
        searchleaf(T, n);
}

 
다음 과 같은 문제 가 있 습 니 다.
1. 마지막 테스트 지점 에 시간 초과 가 발생
2. 알고리즘 은 잎 결점 에서 위로 뿌리 노드 를 찾 는 것 으로 깊이 가 있 고 시간 복잡 도가 너무 크다.
3. 방출 공간 없 음
알고리즘 에 문제 가 생 겨 서 전체 코드 가 통과 하지 못 했 습 니 다. 나중에 많은 개선 을 시 도 했 습 니 다. 예 를 들 어 하나의 배열 로 잎 결 점 을 기록 하고 마지막 테스트 점 을 넘 지 못 했 습 니 다.잎 결점 을 위로 향 해 뿌리 노드 를 찾 는 알고리즘 은 잎의 깊이 를 찾 는 데 있어 시간 복잡 도 는 O (n ^ 2) 이 고 층 차 는 O (n) 이다.
앞으로 팀 이 업 무 를 전개 하기 전에 이번 교훈 을 받 아들 여 방법의 시간 복잡 도 를 자세하게 토론 하고 이런 문제 가 발생 하지 않도록 해 야 한다.