二叉树存储结构与遍历详解

"二叉树的存储结构-二叉树讲义" 二叉树是一种重要的非线性数据结构，它由n（n≥0）个节点组成，这些节点通过分支关系形成一个层次结构。在二叉树中，有一个特殊的节点称为根节点，除了根节点外，其他每个节点都有一个父节点，同时可以有0到2个子节点，分别被称为左子节点和右子节点。二叉树的节点度数可以是0、1或2，其中度为0的节点称为叶子节点，度不为0的节点称为分支节点。 二叉树的存储结构主要有两种：顺序存储结构和链式存储结构。 1. **顺序存储结构**： 在顺序存储结构中，通常采用数组来存储二叉树。如果二叉树是完全二叉树，那么可以利用数组的特性来高效地存储。例如，数组大小可以预设为MaxTreeSize（如128），并用数组SqBiTree来存储二叉树的节点。在给定的例子中，数组的元素代表二叉树的节点，通过数组下标来表示节点间的关系。例如，数组下标0表示根节点，1和2分别表示根节点的左子节点和右子节点，以此类推。这种存储方式便于访问相邻节点，但对非完全二叉树可能会造成空间浪费。 2. **按完全二叉树存储**： 在这个例子中，数组的元素被用来表示一个完全二叉树的节点。完全二叉树是指每一层除了最后一层外，所有层的节点数都是满的，且最后一个层的节点尽可能地靠左排列。对于完全二叉树，数组下标与树中的层次和位置有直接对应关系，便于遍历和操作。 二叉树的遍历主要有三种方式：前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。遍历算法可以用递归或非递归方式实现，其中递归方法直观简洁，非递归方法通常借助栈来实现。线索化二叉树是在二叉链表的基础上增加指向前驱和后继节点的线索，以便在非递归遍历时快速找到相邻节点。 本章还涵盖了树的其他相关内容，包括树的定义、基本术语、不同表示方法（如嵌套集合表示法、凹入表表示法），以及树的层次、节点的度、叶子节点、分支节点等概念。此外，还包括树的遍历、二叉树的多种应用、最优树和哈夫曼编码等高级主题。 掌握二叉树的存储结构和遍历算法是理解和操作二叉树的关键，对于实际问题的解决，如数据压缩、搜索算法和图形处理等领域，都有重要的应用价值。