【数据结构】4. 树与二叉树

发布时间：2021-03-31 18:08:55 所属栏目：安全来源：网络整理

导读：目录 4.1 树的基本概念 4.1.1 树的定义 4.1.2 基本术语 4.1.3 树的性质 4.2 二叉树的概念 4.2.1 二叉树的定义及其主要特性（1）二叉树的定义（2）几个特殊的二叉树（3）二叉树的性质 4.2.2 二叉树的存储结构（1）顺序存储结构（2）链式存储结构 4.3 二

三种遍历算法中递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。
不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是 (mathcal{O}(n))。
在递归遍历中，递归工作找的栈深恰好为树的深度，所以在最坏的情况下，二叉树是有 n 个结点且深度为 n 的单
支树，遍历算法的空间复杂度为 (mathcal{O}(n))。