一、木の構造と概念

1.1 木の概念

木は非線形のデータ構造であり、n（n≧0）個の有限ノードが階層関係を持つ集合です。根ノードは特別なノードで、前駆ノードを持たないです。

1.2 木に関連する概念

• ノードの次数：ノードが持つ子木の数。
• 葉ノードまたは終端ノード：次数が0のノード。
• 非終端ノードまたは分岐ノード：次数が0でないノード。
• 親ノードまたは父ノード：子ノードを持つノード。
• 子ノードまたは子孫ノード：ノードの子木のルートとなるノード。
• 兄弟ノード：同じ親ノードを持つノード。
• 木の次数：木の中で最大のノードの次数。
• ノードのレベル：根から始めて、根が1番目のレベル、根の子ノードが2番目のレベル、以下同様。
• 木の高さまたは深さ：木の中で最大のレベル。

1.3 木の表現

木の構造を表現するには、値領域だけでなく、ノード間の関係も保存する必要があります。最も一般的な表現方法は、子兄弟表現法です。

typedef int DataType;
struct Node {
  struct Node* firstChild;
  struct Node* nextSibling;
  DataType data;
};

二、二叉木の構造と概念

2.1 二叉木の概念

二叉木は以下のいずれかである：

1. 空。
2. 根ノードと左子木、右子木を持つ。

2.2 特殊な二叉木

• 完全二叉木：各レベルのノード数が最大値に達している。
• 完全二叉木：深さKの二叉木で、各ノードが深さKの完全二叉木の1からnまでの番号に対応している。

2.3 二叉木の性質

• 第iレベルのノード数は最大2^(i-1)。
• 深さhの二叉木の最大ノード数は2^h - 1。
• 度数0のノード（葉ノード）の数をN0、度数2のノードの数をN2とすると、N0 = N2 + 1。
• n個のノードを持つ完全二叉木の深さはlog2(n+1)。

2.4 二叉木の格納構造

二叉木は順序構造と連鎖構造の2種類があります。

1. 順序構造：配列を使用して格納します。完全二叉木の場合に効果的です。
2. 連鎖構造：各ノードがデータ領域と左右のポインタを持つ構造です。

typedef int BTDataType;

// 二叉链
struct BinaryTreeNode {
  struct BinaryTreeNode* pLeft; // 左子ノードへのポインタ
  struct BinaryTreeNode* pRight; // 右子ノードへのポインタ
  BTDataType _data; // ノードの値
};

三、二叉木の順序構造と実装

3.1 二叉木の順序構造

通常の二叉木は配列で格納すると空間の無駄が生じますが、完全二叉木は適しています。

3.2 ヒープの概念構造と実装

ヒープは一種の二叉木であり、通常は順序構造の配列で格納されます。

四、二叉木の連鎖構造の実装

4.1 前提説明

二叉木の基本操作を学ぶ前に、まず二叉木を作成する必要があります。

typedef int BTDataType;

typedef struct BinaryTreeNode {
  BTDataType val;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
} BTNode;

static BTNode* BinaryTreeNodeCreate(const BTDataType value) {
  BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
  if (newNode == NULL) {
    perror("malloc");
    exit(-1);
  }
  newNode->val = value;
  newNode->left = newNode->right = NULL;
  return newNode;
}

4.2 二叉木の巡回

4.2.1 先行、中間、後行巡回の概念と過程

二叉木の巡回は、特定の規則に従って二叉木のノードを順に訪問し、それぞれのノードに対して操作を行うことです。

1. 先行巡回：根→左子木→右子木
2. 中間巡回：左子木→根→右子木
3. 後行巡回：左子木→右子木→根

4.2.2 先行、中間、後行巡回の実装

void PreOrder(const BTNode* root) {
  if (root) {
    printf("%d ", root->val);
    PreOrder(root->left);
    PreOrder(root->right);
  } else {
    printf("NULL ");
  }
}

void InOrder(const BTNode* root) {
  if (root == NULL) {
    printf("NULL ");
  } else {
    InOrder(root->left);
    printf("%d ", root->val);
    InOrder(root->right);
  }
}

void PostOrder(const BTNode* root) {
  if (root == NULL) {
    printf("NULL ");
  } else {
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->val);
  }
}

4.2.3 段階巡回の過程

段階巡回は、根から始めて、上から下へ、左から右へと段階的にノードを訪問します。

4.2.4 段階巡回の実装

void LevelOrder(BTNode* root) {
  if (root == NULL) {
    return;
  }

  Queue Q;
  QueueInit(&Q);

  QueuePush(&Q, root);

  while (!QueueEmpty(&Q)) {
    BTNode* front = QueueFront(&Q);
    printf("%d ", front->val);
    QueuePop(&Q);

    if (front->left) {
      QueuePush(&Q, front->left);
    }
    if (front->right) {
      QueuePush(&Q, front->right);
    }
  }
  printf("\n");

  QueueDestroy(&Q);
}

4.2.5 段階巡回の応用——完全二叉木の判定

bool BinaryTreeComplete(BTNode* root) {
  if (root == NULL) {
    return true;
  }

  Queue Q;
  QueueInit(&Q);

  QueuePush(&Q, root);

  while (!QueueEmpty(&Q)) {
    BTNode* front = QueueFront(&Q);
    if (front == NULL) {
      break;
    }

    QueuePop(&Q);
    QueuePush(&Q, front->left);
    QueuePush(&Q, front->right);
  }

  while (!QueueEmpty(&Q)) {
    BTNode* front = QueueFront(&Q);
    if (front != NULL) {
      QueueDestroy(&Q);
      return false;
    }

    QueuePop(&Q);
  }

  QueueDestroy(&Q);
  return true;
}

4.3 二叉木のノード数と葉ノード数の計算

4.3.1 二叉木のノード数の計算

size_t TreeNodeSize(const BTNode* root) {
  return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}

4.3.2 二叉木の葉ノード数の計算

size_t LeafNodesize(const BTNode* root) {
  if (root == NULL) {
    return 0;
  }
  if (root->left == NULL && root->right == NULL) {
    return 1;
  }
  return LeafNodesize(root->left) + LeafNodesize(root->right);
}

4.4 二叉木の高さとk番目のレベルのノード数の計算

4.4.1 二叉木の高さの計算

int TreeHeight(const BTNode* root) {
  if (root == NULL) {
    return 0;
  }

  int leftHeight = TreeHeight(root->left);
  int rightHeight = TreeHeight(root->right);

  return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
}

4.4.2 k番目のレベルのノード数の計算

int TreeKLevel(const BTNode* root, const int K) {
  assert(K >= 0);

  if (root == NULL) {
    return 0;
  }
  if (K == 1) {
    return 1;
  }

  return TreeKLevel(root->left, K - 1) + TreeKLevel(root->right, K - 1);
}

4.5 二叉木内の特定の値の検索

BTNode* TreeFind(BTNode* root, const BTDataType val) {
  if (root == NULL) {
    return NULL;
  }

  if (root->val == val) {
    return root;
  }

  BTNode* leftRet = TreeFind(root->left, val);
  if (leftRet != NULL) {
    return leftRet;
  }

  BTNode* rightRet = TreeFind(root->right, val);
  if (rightRet != NULL) {
    return rightRet;
  }

  return NULL;
}

4.6 二叉木の作成と破棄

4.6.1 二叉木の破棄

void BinaryTreeDestroy(BTNode* root) {
  if (root) {
    BinaryTreeDestroy(root->left);
    BinaryTreeDestroy(root->right);
    free(root);
    root = NULL;
  }
}

4.6.2 二叉木の作成

4.6.2.1 先行順で二叉木を作成

BTNode* BinaryTreeNodeCreate(char* string, int* i) {
  if (string[*i] == '#') {
    ++(*i);
    return NULL;
  }

  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  root->data = string[*i];
  ++(*i);

  root->left = BinaryTreeNodeCreate(string, i);
  root->right = BinaryTreeNodeCreate(string, i);

  return root;
}