19 - 두 갈래 나무의 거울

1. 제목 설명


함수를 완성하고 두 갈래 트리를 입력하십시오. 이 함수는 거울을 출력합니다. 예를 들어 8 --- 두 갈래 트리 A/\6 10/\/\5 7 9 11 ----------------------------- 8 --- 거울 두 갈래 트리/\10 6/\/
  11 9 7  5

2. 문제 풀이 사고방식

거울 두 갈래 나무의 특징을 분석: 뿌리 노드가 변하지 않고 아이의 결점 교환 위치를 좌우한다
      8                                         8                                              8
/\1층 정도 아이를 교환합니다/\2층 정도 아이를 교환합니다/\
    10  6           --->                 6   10     --->                           6   10
   /\/\                                 /\ /\                                      /\ /\
  11 9 7  5                             7  5 11  9                                 5  7 9  11
    (A)                                 (B)                                         (C)
지금 A와 C가 미러링 트리입니다.
그래서 돌아가는 생각은
1. 현재 결점의 좌우 아이가 존재하면 좌우 아이의 결점을 교환한다
2. 현재 결점 좌우에 아이가 존재하지 않는다면(귀속 수렴 조건)return
3. 현재 결점이 비어 있으면return

3. 문제 풀이 알고리즘

/***************************************************************
Author:tmw
date:2018-6-30
****************************************************************/
#include 
#include 

typedef struct BiTreeNode
{
    int data;
    struct BiTreeNode* lchild;
    struct BiTreeNode* rchild;
}BiTreeNode;


/**
*  
* @param *TreeRoot
*
*  : , 
*/
void MirrorBiTree( BiTreeNode* TreeRoot )
{
    /** **/
    if( TreeRoot == NULL ) return;

    /** **/
    if( TreeRoot->lchild == NULL && TreeRoot->rchild == NULL )
        return;

    /** **/
    BiTreeNode* temp = TreeRoot->lchild;
    TreeRoot->lchild = TreeRoot->rchild;
    TreeRoot->rchild = temp;
    free(temp);

    /** **/
    if( TreeRoot->lchild )
        MirrorBiTree(TreeRoot->lchild);
    if( TreeRoot->rchild )
        MirrorBiTree(TreeRoot->rchild);
}

꿈은 있어야지 만일 이루어진다면 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~

좋은 웹페이지 즐겨찾기