Python数据结构与算法-第4章-树

一案例：文件系统的遍历案例：文件系统的遍历案例描述

假设你需要在电脑中查找某个文件file2.txt，但是你不知道它在哪个文件夹下，你会怎么办?一个可行的方法是从根目录开始，逐级查找直到找到你需要的文件。案例：文件系统的遍历案例实现上图为“文件系统树型结构示例”二树的概念树的概念树的基本概念上图为“树的基本概念”树的概念树的基本概念树的基本元素节点边节点间关系父节点和子节点兄弟节点祖先节点节点类型根节点叶子节点内部节点树和节点的属性概念度层次深度高度树的其他相关概念子树森林树的概念二叉树的基本概念

二叉树是一种具有特殊性质的树，它具有以下特点：二叉树要求每个节点最多有两个子节点，所以二叉树中不存在度大于2的节点。二叉树是有序树。上图为“二叉树示例”树的概念二叉树的基本概念上图为“斜树示例”上图为“满二叉树示例”上图为“完全二叉树示例”

典型的特殊的二叉树有斜树、满二叉树、完全二叉树等。具备特殊性质的二叉树还有很多，例如二叉搜索树、平衡二叉树、红黑树等，树的概念二叉树的基本概念二叉树的性质任意二叉树的第i层上最多只有2i-1个节点（i≥1）高度为n的树最多只能有2n+1-1个节点（n≥0）三二叉树的实现及基本操作二叉树的实现及基本操作二叉树节点定义

二叉树的基本单元是节点，每个二叉树节点最多有两个子节点。每个节点包含一个数据属性和两个指针属性，两个指针属性分别指向左右节点，通过python类来定义二叉树节点，其代码如下所示：

按照上述定义二叉树节点所构建二叉树将具备链式存储结构，因此我们称为“二叉链表”。二叉树的实现及基本操作二叉树的操作01构建二叉树02插入和删除节点四二叉树的遍历二叉树的遍历二叉树遍历的概念树是一种非线性数据结构，以二叉树为例，其每个节点不存在唯一的前驱和后继关系，在访问一个节点后，下一个被访问的节点面临不同的选择，这使得遍历树更加复杂。

二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中的所有节点。广度优先深度优先二叉树的遍历广度优先遍历广度优先遍历上图为“二叉树的层序遍历过程”二叉树的遍历深度优先遍历上图为“深度优先遍历原理”深度优先遍历五二叉树的应用二叉树的应用1文件系统2数据库索引3编译器中的语法树4表达式树5网络路由表6哈夫曼树7游戏中的行为树8机器学习决策树9哈希表中的平衡树六小结与习题小结与习题本章小结1树的概念234二叉树的概念二叉树的实现及基本操作二叉树的遍历小结与习题习题？在二叉树的前序遍历中，对于任意节点的访问顺序是?A.当前节点→右子树→左子树B.左子树→当前节点→右子树C.当前节点→左子树→右子树D.右子树→左子树→当前节点小结与习题习题？以下二叉树遍历方法采用广度优先策略的是?A.层序遍历

B.前序遍历C.中序遍历

D.后序遍历小结与习题习题×/√二叉树的节点数量为偶数时，一定存在一个节点具有两个子节点。×/√在二叉树的遍历中，中序遍历得到的序列与前序遍历得到的序列相同。×/√深度优先遍历（DFS）和广度优先遍历（BFS）的时间复杂度都是O(N)，其中N是树或图的节点数量。小结与习题习题

？若已知一棵二叉树的前序遍历结果是5、4、3、2、1、6，中序遍历结果是3、4、5、1、2、6，则它的后序遍历结果是____。

？若已知一棵二叉树的后序遍历结果是F、C、A、E、D、B，中序遍历结果是F、A、C、B、E、D，则它的前序遍历结构是____。七实训任务实训任务任务

在企业组织结构中，通常以树的形式表示。每个节点代表一个部门，节点之间的关系形成了组织的层级结构。请完成以下任务：1.自定义企业组织结构树的节点。2.编写一个函数：输入任意的部门