이 진 트 리 관련 제목

목차
1.이 진 트 리 의 옮 겨 다 니 는 순 서 는 아래 에서 위로,오른쪽 에서 왼쪽 까지 의 층 차 를 옮 겨 다 니 는 순서 입 니 다.
2.이 진 트 리 가 완전 이 진 트 리 인지 판단
3.이 진 트 리 의 두 갈래 결점 의 개 수 를 통계 한다.
4.시퀀스 의 k 번 째 노드 의 값 을 우선 순위 로 옮 겨 다 니 기
5.이 진 트 리 높이 구하 기
6.이 진 트 리 가 이 진 트 리 인지 판단
7.두 갈래 정렬 트 리 의 결점 이 있 는 층수 구하 기
1.이 진 트 리 의 옮 겨 다 니 는 순 서 는 아래 에서 위로,오른쪽 에서 왼쪽 까지 의 층 차 를 옮 겨 다 니 는 순서 입 니 다.
알고리즘 사상:층 차 를 사용 하여 옮 겨 다 닌 다.이 진 트 리 의 정상 적 인 층 차 를 옮 겨 다 니 는 순 서 는 위 에서 아래로 왼쪽 에서 오른쪽으로 가 는 순서 로 제목 의 요구 와 정반 대 입 니 다.스 택 을 사용 하여 정상 적 인 층 차 를 옮 겨 다 니 며 순 서 를 거 스 르 면 됩 니 다.

void levelOrder(BiTree bt)
{   //       
    if(bt == NULL)
        return;
    InitStack(s);
    InitQueue(Q);
    BiTree p = bt;
    EnQueue(Q,p);
    while(!IsEmpty(Q))
    {
        DeQueue(Q,p);
        //visit(p);
        push(s,p);
        if(p-lchild)
            EnQueue(Q,p->lchild);
        if(p-rchild)
            EnQueue(Q,p->rchild);
        
    }//while    
     
    while(!IsEmpty(s))
    {
         pop(s,p);
         visit(p);   
    }//while

}//void

2.이 진 트 리 가 완전 이 진 트 리 인지 판단
알고리즘 사상:층 차 를 사용 하여 옮 겨 다 닌 다.결산 점 을 모두 입단 시 키 고,빈 결산 점도 입단 해 야 한다.빈 노드 를 만 났 을 때 팀 의 남 은 노드 에 빈 노드 가 있 는 지 확인 하고 있 으 면 이 두 갈래 나 무 는 완전히 두 갈래 나무 가 아니 라 없 으 면 완전히 두 갈래 나무 입 니 다.

bool levelOrder(BiTree bt)
{   //       
    if(bt == NULL)
        return true; //        
    InitQueue(Q);
    BiTree p = bt;
    EnQueue(Q,p);
    while(!IsEmpty(Q))
    {
        DeQueue(Q,p);
        if(p)
        {
            EnQueue(Q,p->lchild);
            EnQueue(Q,p->rchild);
        }
        else{
             while(!IsEmpty(Q)) 
             {
                Dequeue(Q,p);
                if(p)
                    return false;
             }
        }//else

    }//while 
  
    return true; 

}//void

3.이 진 트 리 의 두 갈래 결점 의 개 수 를 통계 한다.
귀착 하 다
알고리즘 사상:

int  DsonNodes(BiTree bt)
{
    if(bt == NULL)
        return 0;
    else if(bt-lchild!=NULL && bt->rchild!=NULL)
        return DsonNodes(bt->lchild)+DsonNodes(bt->rchild)+1;
    else
        return DsonNodes(bt->lchild)+DsonNodes(bt>rchild);
}

비 귀속
알고리즘 사상:층 차 를 사용 하여 옮 겨 다 닌 다.두 갈래 노드 의 개 수 를 기록 하기 위해 변 수 를 설정 합 니 다.두 갈래 노드 를 판단 하 는 것 은 좌우 하위 트 리 가 비어 있 는 지 여 부 를 판단 하 는 것 입 니 다.두 갈래 노드 를 만 났 을 때 이 변 수 를 하나 더 하고 옮 겨 다 닐 때 이 변 수 를 되 돌려 주면 됩 니 다.

int DsonNodes(BiTree bt)
{   //       
    if(bt == NULL)
        return 0;
    int count = 0; //          
    InitQueue(Q);
    BiTree p = bt;
    EnQueue(Q,p);
    while(!IsEmpty(Q))
    {
        DeQueue(Q,p);
        //visit(p);
        if(p->lchild)
            EnQueue(Q,p->lchild);
        if(p->rchild)
            EnQueue(Q,p->rchild);
        if(p->lchild && p->rchild)//        
            count ++;
    }//while    
    
    return count;
}//void

4.시퀀스 의 k 번 째 노드 의 값 을 우선 순위 로 옮 겨 다 니 기
귀착 하 다
알고리즘 사상:우선 순 서 를 재 귀적 으로 옮 겨 다 니 며 전체 변 수 를 설정 하고 현재 노드 의 번 호 를 기록 하 며 k 번 째 노드 에 접근 할 때 이 노드 의 값 을 되 돌려 줍 니 다.

int i = 1;
elemType preNode(BiTree bt, int k)
{
    if(b == NULL)
        return "#"
    if(i == k)
        return b->data;
    i++;
    ch = preNode(b->lchild,k);
    if(ch != "#")
        return ch;
    ch = preNode(b->rchild,k);
    return ch;
}

비 귀속
알고리즘 사상:선착순 으로 옮 겨 다 니 기.현재 방문 한 노드 번 호 를 기록 하기 위해 변 수 를 설정 합 니 다.k 번 째 노드 에 접근 할 때 이 노드 의 값 을 되 돌려 줍 니 다.

elemType preOrder2(BiTree bt, int k)
{   //       
    if(bt == NULL || k <= 0)
        return " ";
    int n = 0;
    InitStack(s);
    BiTree p = bt;
    push(s,p);
    while(!IsEmpty(s))
    {
        pop(s,p);
        //visit(p);
        n++;
        if(n == k)
            return p->data;
        if(p->rchild)
            push(s,p->rchild);//      ，         ，        
        if(p->lchild)
            push(s,p->lchild);
 
    }//while
    return " ";//k           ，  " ";
}//void

5.이 진 트 리 높이 구하 기
귀착 하 다
알고리즘 사상:나무 가 비어 있 으 면 0 으로 돌아 갑 니 다.그렇지 않 으 면 왼쪽 나무 오른쪽 나무의 높이 를 재 귀적 으로 계산 한 다음 에 왼쪽 나무의 높이 를 비교 하고 높이 가 비교적 큰 값 으로 1 을 더 합 니 다.

int BTdepth(BiTree bt)
{
    if(bt == NULL)
        return 0;
    ldep = BTdepth(bt->lchild);
    rdep = BTdepth(bt->rchild);
    if(ldep > rdep)
        return ldep+1;
    else
        return rdep+1;
}

비 귀속
알고리즘 사상:층 차 를 사용 하여 옮 겨 다 닌 다.변수 level 을 설정 하여 현재 노드 가 있 는 층 수 를 기록 하고 변수 last 를 설정 하여 현재 층 의 가장 오른쪽 노드 를 기록 합 니 다.매번 층 차 를 옮 겨 다 닐 때 last 포인터 와 비교 합 니 다.같 으 면 층 수 를 하나 더 하고 last 가 다음 층 의 가장 오른쪽 노드 를 가리 키 도록 합 니 다.반복 이 끝 날 때 까지 변수 level 을 되 돌려 줍 니 다.

int BTdepth2(BiTree bt)
{
    if(!bt)
        return 0;
    int front = -1, rear = -1;
    int last = 0, level = 0;
    BiTree Q[maxSize];
    Q[rear++] = bt;
    BiTree p;
    while(front < rear){
        p = Q[++front];
        if(p->lchild)
            Q[++rear] = p->lchild;
        if(p->rchild)
            Q[++rear] = p->rchild;
        if(front == last)
        {
            level ++;
            last == rear;
        }
    }//while
    return level;

}//void

6.이 진 트 리 가 이 진 트 리 인지 판단
알고리즘 사상:이 진 트 리 를 중간 순서 로 옮 겨 다 니 며 앞의 숫자 가 뒤의 숫자 보다 작 으 면 이 진 트 리 임 을 나타 낸다.
귀착 하 다

KeyType predt = -32767;

int JudgeBST(BiTree bt)
{
    int b1, b2;
    if(bt == NULL)
        return 1;
    else{
        b1 = JudgeBST(bt->lchild);
        if(b1 == 0 || predt >= bt->data)
            return 0;
        predt = bt->data;
        b2 = JudgeBST(bt->rchild);
        return b2;
    }//else
    
}//int 

비 귀속

bool JudgeBST(BiTree bt)
{
    if(!bt)
        return true;
    InitStack(s);
    InitQueue(Q);
    while(p||!IsEmpty(s)){
        if(p)
        {
            push(s,p);
            p = p->lchild;
        }
        else{
            pop(s,p);
            EnQueue(Q,p);
            p = p->rchild;
        }
    }//while
    DeQueue(Q,temp);
    while(!IsEmpty(Q)){
        DeQueue(Q,p);
        if(p->data > temp->data){
            temp = p;
        }
        else
            return false;
    }//while
    return true;   
}//bool

7.두 갈래 정렬 트 리 의 결점 이 있 는 층수 구하 기
알고리즘 사상:이 진 트 리 의 검색 과 비슷 합 니 다.현재 노드 의 층 수 를 기록 하 는 변 수 를 추가 해 야 합 니 다.

int level(BiTree bt, BSTNode *p)
{
    if(bt == NULL)
        return -1;
    int n=1;
    BiTree t = bt;
    while(t->data!=p->data){
        if(t->data < p->data)
            t = t->lchild;
        else
            t = t->rchild;
        n++;
    }
    return n;
}