트리 데이터 구조에 C++ 재귀 함수를 적용합니까?-C++-php.cn

트리 데이터 구조에 C++ 재귀 함수를 적용합니까?

PHPz

풀어 주다： 2024-04-17 16:48:01

원래의

1060명이 탐색했습니다.

재귀 함수는 트리 데이터 구조를 처리할 때 다음과 같이 적용됩니다. 기본 개념: 재귀 함수는 자신을 호출하여 큰 문제를 더 작은 문제로 분해합니다. 트리 구조 탐색: 선주문 탐색: 노드를 방문하기 전에 자식 노드를 방문합니다. 후위 순회: 노드를 방문한 후 하위 노드를 방문합니다. 실제 사례: 이진 트리의 순회와 이진 트리의 출력 노드 값을 선주문합니다.

C++ 递归函数在树数据结构中的应用？

트리 데이터 구조에서 C++ 재귀 함수 적용

재귀 함수는 트리 데이터 구조를 처리할 때 매우 유용합니다. 트리 구조는 각 노드가 여러 개의 하위 노드를 가질 수 있는 비선형 데이터 구조입니다. 트리 구조의 특성으로 인해 재귀 함수는 이러한 구조를 쉽게 탐색하고 조작할 수 있습니다.

기본 개념

재귀 함수는 자신을 호출하는 함수입니다. 이를 통해 함수는 문제를 분해하여 더 작은 하위 문제로 변환할 수 있습니다. 기본 사례에 도달할 때까지 프로세스가 계속된 다음 재귀 호출이 반환되기 시작합니다.

트리 구조 탐색

재귀 함수를 사용하여 트리 구조를 탐색할 수 있습니다. 이는 두 가지 주요 방법으로 달성할 수 있습니다:

선주문 순회: 노드를 방문하기 전에 노드의 하위 노드를 먼저 방문합니다.
사후 순회: 노드를 방문한 후 해당 하위 노드를 방문합니다.

실용 사례: 이진 트리의 선주문 순회

각 노드가 정수를 포함하는 이진 트리가 있다고 가정합니다. 다음 C++ 코드는 선주문 순회를 위해 재귀 함수를 사용하는 방법을 보여줍니다.

struct Node {
    int data;
    Node* left;
    Node* right;
};

void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }
    
    // 访问当前节点
    cout << root->data << " ";
    
    // 递归遍历左子树
    preorderTraversal(root->left);
    
    // 递归遍历右子树
    preorderTraversal(root->right);
}

int main() {
    // 创建二叉树结构：
    //    1
    //   / \
    //  2   3
    // / \
    //4   5
    Node root = {1, nullptr, nullptr};
    Node left1 = {2, nullptr, nullptr};
    Node right1 = {3, nullptr, nullptr};
    Node left2 = {4, nullptr, nullptr};
    Node right2 = {5, nullptr, nullptr};

    root.left = &left1;
    root.right = &right1;
    left1.left = &left2;
    left1.right = &right2;

    // 前序遍历二叉树
    preorderTraversal(&root);
    
    return 0;
}

로그인 후 복사