数据结构之博弈树搜索(深度优先搜索)

简介: 本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。


1 博弈树搜索(深度优先搜索)

博弈树搜索是人工智能领域中一种重要的算法,常用于制定决策和策略的制定,特别是在博弈和决策问题中。这种搜索方法基于树形结构,其中每个节点表示一个游戏状态或决策点,而边则代表可能的行动或决策。通过深度优先搜索或广度优先搜索,算法可以遍历博弈树,评估每个节点的价值,并最终选择最优的决策路径。

    在博弈树搜索中,常见的应用场景包括棋类游戏(如国际象棋、围棋、井字棋等)和其他多人参与的博弈情境。算法的目标是为当前玩家找到一种最优的策略,使得在对手采取最佳应对的情况下,当前玩家能够取得最大的收益。

    每个节点的状态由游戏中的各种因素确定,例如棋盘上的布局、剩余的游戏步数、玩家的分数等。通过递归地评估每个可能的决策,博弈树搜索能够构建一个全面的决策树,其中包含了游戏中所有可能的决策路径。

     博弈树搜索的核心思想是利用深度优先或广度优先搜索算法,通过递归地遍历树结构,评估每个节点的局势,并根据评估结果选择最有利的决策。在这一过程中,算法需要考虑到对手的最佳应对,以确保制定的策略在各种情况下都具有鲁棒性。

    在实际应用中,博弈树搜索为计算机在复杂决策问题中找到最优解提供了一种强大而灵活的方法。通过不断优化算法和引入剪枝等技术,博弈树搜索在人工智能领域的许多成功案例中发挥着重要作用。




二叉树:表示初始化和创建二叉树节点的过程



执行深度优先搜索:表示深度




表示从二叉树构建链表的过程      表示链接中的值打印
AI 代码解读

3 核心代码

struct TreeNodestruct ListNode

这些结构定义了二叉树和链表的基本构建块:



深度优先搜索

dfs是一个递归深度优先搜索函数,它遍历二叉树并按预序打印节点的值。



构建链表函数(buildLinkedList)

根据二叉树的深度优先搜索顺序构造链表。它返回链表的头部。
AI 代码解读

4 代码结果

深度优先搜索 (DFS) 输出: 1 2 4 5 3 6 7

显示二叉树的深度优先搜索遍历的结果。顺序是预序遍历(root、left、right)。

单链表的节点值: 1 2 4 5 3 6 7

显示链表节点的值。链表是根据深度优先搜索期间访问的节点顺序构建的。
AI 代码解读

5 算法优缺点

该算法在二叉树上执行深度优先搜索(DFS)遍历,并根据DFS遍历的顺序构造链表。以下是优点和缺点以及时间复杂度:

优势:

单纯:该算法相对易于理解和实现。

   内存效率:该算法不需要额外的空间来存储中间结果(除非在 DFS 期间考虑递归调用堆栈)。链表的构造方式直接使用现有的树节点。
AI 代码解读

弊端:

内存管理:该算法使用手动内存管理 ( 和 ) 来构建和删除节点。这可能容易出错,如果不小心操作,可能会导致内存泄漏或分段错误。现代 C++ 提供了智能指针等工具来缓解这些问题。newdelete

时间复杂度:

     DFS 遍历的时间复杂度为 O(N),其中 N 是二叉树中的节点数。每个节点访问一次。

    构建链表的时间复杂度也是 O(N),其中 N 是节点数。这是因为每个节点都访问一次,并且每个节点都会完成恒定的工作量。
AI 代码解读

6 附件之源代码

#include <iostream>



// 节点结构

struct TreeNode {
   

    int value;

    TreeNode* left;

    TreeNode* right;



    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {
   }

};



// 单链表结构

struct ListNode {
   

    TreeNode* node;

    ListNode* next;



    ListNode(TreeNode* n) : node(n), next(nullptr) {
   }

};



// 深度优先搜索函数

void dfs(TreeNode* node) {
   

    if (node == nullptr) {
   

        return;

    }



    std::cout << node->value << " ";



    dfs(node->left);

    dfs(node->right);

}



// 根据深度优先搜索构建单链表

ListNode* buildLinkedList(TreeNode* root) {
   

    if (root == nullptr) {
   

        return nullptr;

    }



    ListNode* head = new ListNode(root);

    ListNode* current = head;



    if (root->left != nullptr) {
   

        current->next = buildLinkedList(root->left);

        while (current->next != nullptr) {
   

            current = current->next;

        }

    }



    if (root->right != nullptr) {
   

        current->next = buildLinkedList(root->right);

    }



    return head;

}



// 释放单链表内存

void deleteLinkedList(ListNode* head) {
   

    while (head != nullptr) {
   

        ListNode* temp = head;

        head = head->next;

        delete temp->node; // 释放节点内存

        delete temp;       // 释放链表节点内存

    }

}



int main() {
   

    // 构建一个简单的二叉树

    TreeNode* root = new TreeNode(1);

    root->left = new TreeNode(2);

    root->right = new TreeNode(3);

    root->left->left = new TreeNode(4);

    root->left->right = new TreeNode(5);

    root->right->left = new TreeNode(6);

    root->right->right = new TreeNode(7);



    // 深度优先搜索

    std::cout << "深度优先搜索: ";

    dfs(root);

    std::cout << std::endl;



    // 构建单链表

    ListNode* linkedList = buildLinkedList(root);



    // 输出单链表的节点值

    std::cout << "单链表的节点值: ";

    ListNode* current = linkedList;

    while (current != nullptr) {
   

        std::cout << current->node->value << " ";

        current = current->next;

    }

    std::cout << std::endl;



    // 释放内存

    deleteLinkedList(linkedList);

    delete root;



    return 0;

}

​
AI 代码解读
目录
打赏
0
0
0
0
69
分享
相关文章
数据结构之网络攻击路径(深度优先搜索)
本文介绍了如何使用深度优先搜索(DFS)算法分析网络攻击路径。在网络安全领域,DFS用于检测网络中潜在的攻击路径,帮助安全人员及时发现并阻止威胁。文中详细描述了网络图的构建、节点间的连接关系以及DFS的实现过程。通过一个具体的例子,展示了如何检测从一个普通节点到关键节点的攻击路径,并讨论了DFS算法的优缺点。提供的C++代码实现了网络图的构建和攻击路径的检测功能。
88 24
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
62 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
49 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
47 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
53 2
|
3月前
|
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
149 23
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
|
3月前
|
数据结构之环境监测系统(深度优先搜索)
环境监测系统采用深度优先搜索(DFS)算法,实现实时监测和分析环境参数,如温度、湿度等。系统通过构建传感器网络图结构,利用DFS遍历网络,检测异常数据。当温度超过预设阈值时,系统将发出警告。此系统适用于工业生产、室内空调控制、农业温室管理等多种场景,提供高效的环境监测解决方案。
68 12
|
3月前
|
数据结构之文件系统模拟(树数据结构)
本文介绍了文件系统模拟及其核心概念,包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境,模拟文件的创建、删除、移动、搜索等操作,展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现,包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性,如灵活性高但节点移除效率低等问题。
93 0
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
348 9
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等