计算机考研 数据结构-树--总结者：刘尧涛

树型结构是一类重要的非线性结构。树是n(n>=0)个结点的有限集T 结点 数据元素的内容及其指向其子树根的分支统称为结点。 结点的度 结点的分支数。 终端结点（叶子） 度为0的结点。 非终端结点 度不为0的结点。 结点的层次 树中根结点的层次为1，根结点子树的根为第2层，以此类推。 树的度 树中所有结点度的最大值。 树的深度 树中所有结点层次的最大值。 有序树、无序树 如果树中每棵子树 计算机科学中的数据结构是编程的基础，树作为一种非线性数据结构，尤其在处理复杂的数据组织和操作时扮演着重要角色。树形结构是由n个节点（n >= 0）组成的有限集，每个节点包含数据元素以及指向其子树根的分支。节点的“度”指的是它拥有的子树数量，分为终端节点（叶子节点），度为0，没有子树；非终端节点（内部节点），度不为0，至少有一个子树。 节点的“层次”从根节点开始计算，根节点层次为1，其子节点为第2层，依此类推。树的“度”是所有节点度的最大值，反映树的最大分支数。而“深度”是树中所有节点层次的最大值，表示树的最高层级。 有序树和无序树的区别在于子树的排列顺序，有序树的子树有特定的左到右顺序，不能互换，无序树则没有这种限制。此外，树还可以扩展成森林，即由多个互不相交的树组成的集合。 二叉树是特殊的树形结构，每个节点最多有两个子节点，分为左子树和右子树。二叉树有三个重要的遍历方法：前序遍历（根-左-右），中序遍历（左-根-右）和后序遍历（左-右-根）。满二叉树是深度为k且有2^k-1个节点的二叉树，完全二叉树则是在满二叉树的基础上，允许最后一层不满但所有节点靠左排列。 二叉树的存储结构有多种方式，包括顺序存储（适用于完全二叉树）、二叉链表、三叉链表以及线索链表。线索链表通过在节点中添加前驱和后继指针，使得在遍历时可以直接找到相邻节点。二叉树的深度可以通过递归计算左、右子树的深度来得到。 在实际应用中，如文件系统、编译器、数据库索引等，都会用到树和二叉树的概念。例如，二叉搜索树是一种特殊的二叉树，其中每个节点的左子树只包含小于当前节点的元素，右子树包含大于当前节点的元素，这使得查找、插入和删除操作的效率非常高。 此外，森林到二叉树的转换、二叉树到森林的转换以及树和二叉树的相互转换，这些都是在数据结构学习中需要掌握的重要内容。这些转换有助于理解和操作复杂的树结构，比如在算法设计和实现中，通过二叉树的形式往往可以简化问题的处理。 理解并熟练掌握树和二叉树的特性、操作以及它们的转换方法，对于计算机科学的学习者和从业者来说至关重要，因为这些知识是构建高效算法和数据结构的基础。