C语言数据结构——二叉树的顺序存储和二叉树的遍历

谁践踏了优雅 2022-12-22 08:55 157阅读 0赞

在学习顺序存储结构之前要知道：  
二叉树的结构是**非线性的**；  
每一个结点可有两个后继。

对于这种一对多的层次结构，我们应该怎么样合理的存储下来呢？

二叉树既有顺序存储又有链式存储，今天先学顺序存储。  
方法:  
使用一组连续的存储单元来存放二叉树的数据元素。  
使用结点之间的相对位置表示结点之间的关系。  
对于满二叉树和完全二叉树来说，可以按照对满二叉树结点连续编号，将各结点数据存放到一组连续的存储单元中，将二叉树中编号为i的结点存放在数组的第i号元素中。

**编号规则：**  
根结点的编号为1；对于编号为i的结点，  
左孩子如果存在，则编号为2i；  
右孩子如果存在，则编号为2i+1。  
如果结点编号为i，则双亲的编号为i/2。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]  
注意：空结点在存储时也一定要标出来，NULL。  
这种情况显然会造成空间的浪费，因为存在空的存储位置。下面这个例子更明显，开辟了15个有效空间，但实际存储的有效元素只有4个。存储密度较低。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]  
总结：顺序存储只适用于满二叉树和完全二叉树。

**二叉树的遍历：**  
顺着某一条搜索路径**巡访**二叉树中的每个结点，使得**每个结点均被访问一次**，而且**仅被访问一次。**  
将非线性化结构按照一定的规律变成线性化的序列。  
由二叉树的定义可知：  
二叉树的基本结构是由根结点、左子树和右子树三部分构成。左右子树也必须符合二叉树的定义。所以，二叉树本身也就符合递归的定义！  
**有三种遍历策略：**  
1.先上后下的层次遍历；  
2.先左子树后右子树的深度遍历；  
3.先右子树后左子树的深度遍历。  
注意：下面的D代表根；L代表左子树；R代表右子树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]  
**一、先序遍历的具体思想方法**：  
（对每一棵子树都采取先序遍历的方法，遍历时一定要遵循先左后右的原则。）  
![在这里插入图片描述][20201118212233427.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]  
代码实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 7]  
**二、中序遍历的具体思想方法**  
先遍历左子树，再遍历根，最后遍历右子树。记住：每一个子树依旧采取中序遍历算法。  
![在这里插入图片描述][20201118214434855.png_pic_center]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 8]  
代码实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 9]  
**三、后序遍历的具体思想方法：**  
![在这里插入图片描述][20201118214739100.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 10]  
代码实现：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 11]  
由此可以总结出：  
所谓的先、中、后，其实就是根结点遍历的顺序，如果根结点先遍历，就是先序遍历；如果遍历左子树后再遍历根结点，就是中序遍历；如果根结点在左子树和右子树遍历结束后在遍历，就是后序。但对于左子树和右子树而言，一直是先左后右的原则！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/852dbb35e1f44ff68c9c79800d10f9a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/26e07cb98e9240caa5c88b68238b784c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/93b6733b4eb9457b98e322ef3b19f338.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/c9559ad241e54410948acb4b89796e21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/f66e16b5e6d0498eb135610b08acebc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/ff85d4f350654e03970f02a85b4fdd5c.png
[20201118212233427.png_pic_center]: /images/20221120/541f84b575fe462b9e61429df36a163d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221120/966153178da74273b0dea7f8b2acabf6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221120/44b2c8be1d61448f80fb65944540080d.png
[20201118214434855.png_pic_center]: /images/20221120/bd167fbbb126417bb4c6f9514c4271e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221120/02255d6e55be4cbfafd3e9fcc7bebfd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221120/dfecaac943ec4497b344f1020297af41.png
[20201118214739100.png_pic_center]: /images/20221120/8e817515336f4e5db57f62c440ada94b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221120/31bc2959f8a64423ac6c8062c92ceba3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221120/be281ef075d64b11b658a4c35f6ff8be.png