"2021春-树的基本概念、遍历与性质"

第三章：树-2021-21；（1）概念、定义、性质；（2）二叉树的遍历（ADT操作） 树（Tree）是一种重要的数据结构，被广泛应用于计算机科学与技术领域。树是由节点（Node）和边（Edge）组成的非线性数据结构，节点之间通过边相连，形成层次结构。树的每个节点都可以有零个或多个子节点。根节点是树的顶端节点，它没有父节点；叶子节点是没有子节点的节点；其他节点则是一个或多个子节点的父节点。树非常适用于表示层次关系，比如文件系统的目录结构、组织架构等。 在树的分类中，二叉树是一种特殊的树结构，它的每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树的遍历是一种重要的操作，它可以按照一定的规则访问树中的每个节点，将节点的值进行处理或输出。常见的二叉树遍历方式有先根顺序遍历、中根顺序遍历和后根顺序遍历。先根顺序遍历（Preorder Traversal）先访问根节点，然后按照先根顺序递归遍历左子树和右子树。中根顺序遍历（Inorder Traversal）先递归遍历左子树，然后访问根节点，最后递归遍历右子树。后根顺序遍历（Postorder Traversal）先递归遍历左子树和右子树，最后访问根节点。 一个二叉树可以通过先根顺序遍历、中根顺序遍历和后根顺序遍历这三种方式的结果来唯一确定。这是因为先根顺序遍历和后根顺序遍历可以确定根节点，而中根顺序遍历可以确定左子树和右子树的节点位置，从而得到完整的二叉树结构。 对于二叉树的性质，我们可以总结如下： 性质1：在二叉树中的第 i 层的结点数最多为2^i-1。这意味着树的底层节点数是前面各层节点数之和再加1。 性质2：高度为k的二叉树其节点总数最多为2^k-1 (k ≥ 1)。通过这个性质，我们可以得知树的高度和节点数的关系。 性质3：对任意的非空二叉树T，如果叶节点的个数为n0，而其度为2的节点数为n2，则：n0 = n2 + 1。这个性质说明了二叉树中叶子节点和度为2的节点的关系。 性质4：具有n个节点的完全二叉树的深度为log2n + 1的向下取整。完全二叉树是指除了最后一层节点可能不满之外，其他层均满足节点数最多的规律。 性质5：如果对一棵有n个节点的完全二叉树的节点按层序编号，则对任一节点i有：⑴ 如果i=1，则节点i是二叉树的根，无双亲；⑵ 如果i＞1，则其双亲节点是向下取整(i/2)。 以上是关于树及二叉树的概念、定义和性质的总结。树作为一种重要的数据结构，在计算机科学与技术领域有广泛的应用。对于二叉树的遍历，我们可以通过先根顺序遍历、中根顺序遍历和后根顺序遍历来访问树中的每个节点。同时，了解二叉树的性质能够帮助我们更好地理解和应用这种数据结构。通过对树的学习和掌握，我们可以更高效地解决各种计算问题。