电大资源网11252《数据结构》实践活动（实验4 二叉树）（课程号：02272）2025年春

　　1 二叉树的顺序存储结构和链式存储结构

　　问题描述

　　设一棵完全二叉树用顺序存储方法存储于数组tree中，编写程序：

　　（1）根据数组tree，建立与该二叉树对应的链式存储结构。

　　（2）对该二叉树采用中序遍历法显示遍历结果。

　　实验要求

　　（1）在主函数中，通过键盘输入建立设定的完全二叉树的顺序存储结构。

　　（2）设计子函数，其功能为将顺序结构的二叉树转化为链式结构。

　　（3）设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。

　　（4）通过实例判断算法和相应程序的正确性。

　　设计思路

　　（1）顺序存储的二叉树转化为链式存储结构，采用递归算法，递归函数的形式为Creab(tree,n,i,b)，其中形参：tree为顺序存储二叉树的数组，n为二叉树的结点数，i是二叉树某结点在数组tree中的下标（初始值为1），b为要建立的链式存储二叉树结点指针。转化时，首先建立*b结点，将tree[i]的值赋给*b的数据域，再调用递归函数分别构造左子树和右子树。

　　（2）中序遍历采用递归算法，即中序遍历左子树、访问根结点、中序遍历右子树。

　　实验设计

　　程序代码如下：