C++ データ構造における再帰の素晴らしい使用法: スタックとツリーの実装

C データ構造における再帰の適用: スタック: スタックは、後入れ先出し (LIFO) 構造を通じて再帰的に実装されます。ツリー: ツリーは階層構造を通じて再帰的に実装され、挿入や深さの計算などの操作をサポートします。再帰は、ネストされた構造を処理するための簡潔で効率的なソリューションを提供し、データ構造の実装をより直感的で保守しやすくします。

C データ構造における再帰の素晴らしい使用法: スタックとツリーの実装

再帰は強力なプログラミング テクノロジです。関数がそれ自体を呼び出して問題を解決できるようにします。再帰は、データ構造の実装、特にツリー構造や線形構造の処理に非常に役立ちます。

スタックの再帰的実装

スタックは後入れ先出し (LIFO) データ構造です。以下に示すように、再帰を使用してスタックを実装できます。

struct Node {
  int data;
  Node* next;
};

class Stack {
private:
  Node* head;

public:
  void push(int data) {
    head = new Node{data, head};
  }

  int pop() {
    if (head == nullptr) {
      throw exception("Stack is empty");
    }
    int data = head->data;
    head = head->next;
    return data;
  }

  bool empty() {
    return head == nullptr;
  }
};

実用的なケース: リンクされたリストを逆順で出力する

void printLinkedListInReverseOrder(Node* head) {
  if (head == nullptr) {
    return;
  }

  printLinkedListInReverseOrder(head->next);
  cout << head->data << " ";
}

ツリーの再帰実装

ツリーは階層データ構造です。以下に示すように、再帰を使用してツリーを実装できます。

struct Node {
  int data;
  vector<Node*> children;
};

class Tree {
private:
  Node* root;

public:
  void insert(int data) {
    if (root == nullptr) {
      root = new Node{data, {}};
    } else {
      insertHelper(root, data);
    }
  }

private:
  void insertHelper(Node* node, int data) {
    for (auto& child : node->children) {
      if (child == nullptr) {
        child = new Node{data, {}};
        return;
      }
    }

    node->children.push_back(new Node{data, {}});
  }

  void printTree() {
    printTreeHelper(root);
  }

private:
  void printTreeHelper(Node* node) {
    cout << node->data << " ";
    for (auto& child : node->children) {
      printTreeHelper(child);
    }
  }
};

実際のケース: バイナリ ツリーの深さを計算する

int calculateTreeDepth(Node* root) {
  if (root == nullptr) {
    return 0;
  }

  int maxDepth = 0;
  for (auto& child : root->children) {
    maxDepth = max(maxDepth, calculateTreeDepth(child));
  }

  return maxDepth + 1;
}

再帰により、単純かつ効率的にスタックおよび合計する ツリーなどの主要なデータ構造。再帰は、複雑な入れ子構造を処理するための強力なツールを提供し、データ構造の実装をより直感的で保守しやすくします。

以上がC++ データ構造における再帰の素晴らしい使用法: スタックとツリーの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。