数据结构与算法（Python版）第2版 课件 chap7.2 树

树树的存储2双亲表示法孩子链表表示法树的二叉链表(孩子-兄弟）存储表示法

双亲表示法

3

孩子表示法

4

孩子兄弟表示法

5

树与二叉树转换6树与二叉树均可用二叉链表作为存储结构，则以二叉链表为媒介可导出树与二叉树之间的一个对应关系——即给定一棵树，可以找到唯一一棵二叉树与之对应。

树转化为二叉树7

二叉树转化为树8

二叉树深度9二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。二叉树的高度也就是深度，为二叉树中节点层次的最大值，也可以视为其左右子树高度的最大值加1

二叉树左右视图10二叉树的左视图就是层序遍历保留每一层第一个值。二叉树的右视图就是层序遍历保留每一层最后一个值。先求出二叉树的最大深度，然后求出每一层的节点列表，求每一层节点列表就相当于求距离根节点指定深度的所有节点，再将每一层的节点列表中的最左或最右节点打印出来

括号组合11【题意】给出

n

代表生成括号的对数，求出能够生成所有可能的并且有效的括号组合。例如，

n=3，生成结果为：["((()))","(()())","(())()","()(())","()()()"]【解析】采用回溯法，当只有在序列保持有效时才添加'('or')'，通过跟踪到目前为止放置的左括号和右括号的数目来执行。如果还剩一个位置，可以开始放一个左括号。如果右括号不超过左括号的数量，可以放一个右括号。

对称二叉树12二叉树

[1,2,2,3,4,4,3]对称。但是,二叉树

[1,2,2,null,3,null,3]不对称。。

二叉树在AI中应用13（1）模型结构决策树是一种基于二叉树结构的模型。在分类问题中，例如判断一个水果是苹果还是橙子，决策树的每个节点是一个决策点，根据某个特征（如颜色、形状等）进行划分。以颜色为例，如果是红色，可能进一步判断形状；如果不是红色，可能走另一个分支。这个过程类似于二叉树的遍历。

二叉树在AI中应用14（2）训练过程通过对训练数据的学习，确定每个节点的决策规则。例如，在一个简单的邮件分类任务中，训练数据是邮件内容（文本特征）和是否为垃圾邮件的标签。决策树通过分析这些数据，找到最佳的划分特征，如邮件中是否包含特定的关键词，来构建树的结构。

二叉树在AI中应用15

（3）预测过程对于新的数据，从根节点开始，按照决策规则沿着树的分支进行判断，直到到达叶子节点，叶子节点的类别标签就是预测结果。例如，对于一封新邮件，通过决策树判断它是否为垃圾邮件。

二叉树在AI中应用16（4）深度学习中的神经网络架构优化1）表示搜索空间二叉树可以用于表示神经网络架构的搜索空间。在神经架构搜索(NAS)中，神经网络的架构（如层数、每层的神经元数量、连接方式等）是需要优化的对象。可以将不同的架构选择看作二叉树中的节点和分支，通过搜索二叉树来找到最优的架构。2）进化算法应用利用进化算法在二叉树表示的搜索空间中搜索。例如，初始时生成一组随机的二叉树（代表不同的神经网络架构），然后通过交叉（交换二叉树的部分分支）和变异（改变二叉树的某个节点或分支）等操作，生成新的架构，根据在验证数据集上的性能评估来选择优秀的架构进行下一轮进化。

AI对二叉树的影响17（1）优化二叉树结构和算法以适应大数据和复杂模型随着AI处理的数据量越来越大，对二叉树的存储和操作效率提出了更高的要求。例如，在决策树模型中，当处理海量的训练数据时，需要更快的算法来构建和更新决策树。这促使研究人员开发更高效的二叉树构建算法，如基于近似算法的决策树构建，以减少计算时间和内存占用。

AI对二叉树的影响18

（2）启发新的二叉树相关理论和方法AI中的一些思想和技术也启发了二叉树相关的新研究。例如，深度学习中的梯度下降方法启发了