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

第六章主要探讨了树与二叉树的数据结构，分为以下几个部分： 1. 树的存储结构： - 双亲表示法：这是一种简单的存储方式，利用一组连续的存储空间来表示树，每个节点仅有一个双亲，因此只需要一个指针即可链接到其父节点。这种方式简单直观，但不适用于需要频繁插入或删除节点的情况。 - 孩子表示法： - 多重链表：每个节点有多个指针指向其子节点，虽然直观，但存在大量空链域的问题，导致存储效率较低。 - 单链表：将节点的孩子节点排列成线性表，节省了空间，但访问顺序受制于节点在链表中的位置。 - 孩子兄弟表示法（二叉链表）：每个节点有两个指针，一个指向第一个孩子，另一个指向兄弟节点，有助于减少空链域，提高空间利用率。 2. 树与二叉树的对应关系： - 任意一棵树可以通过二叉链表的形式进行存储，这种形式下的二叉树具有特殊的结构，例如某些节点可能只有一个左子树或右子树。 - 森林与二叉树的关系是，通过特定的转换，可以把多棵树组合成一个二叉树，比如将森林的第二棵树的根视为第一棵树的兄弟节点。 3. 树的遍历： - 树的遍历方法主要包括先根遍历和后根遍历，这两种方法在访问树的所有节点时有所不同。先根遍历首先访问根节点，然后递归地遍历每一棵子树；后根遍历则相反，从叶子节点开始，逆序访问直到根节点。 总结来说，这一章内容涵盖了树的不同存储结构及其优缺点，以及如何将树转换为二叉树，并介绍了两种基本的树遍历策略。理解这些概念对于理解和实现树相关的算法至关重要，例如搜索、排序和图的表示等。在实际编程中，选择合适的存储结构和遍历方法能极大地影响程序的性能和效率。