实验作业三：树和二叉树
1. 已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。试设计一个算法，从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。
2二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。
编写实习报告要求： 一、需求分析 二、概要设计
编程语言：C语言或C++语言
实习报告提交方式：下次上机前，将实习报告(.doc)和源程序(.cpp)压缩成一个rar文件，文件名称为学号_班级_姓名_第几次作业。例如：3010216155_六班_张三_第三次作业.rar。实习报告作为本课程的平时成绩。
抄袭、雷同，双方均为0分。
1.抽象数据类型 2.算法
程序代码（注释）
调试过程中所做的工作，时间复杂度等 输入数据和输出数据示例
三、详细设计 四、调试分析 五、测试结果 六、说明（如果有）
第一题：
需求分析
题目需要建立一个二叉链表，根据完全二叉树的建立方式，利用一个一维数组里的数据来建立完全二叉树的二叉链表。
二、概要设计
1.抽象数据类型 typedef struct tree{
typedef tree * node; 2.算法
（1）.创建一维数组。 char x[n];
for(int a=0;a { } cin>>x[a]; char data; struct tree *lchild,*rchild; }tree; （2）.创建完全二叉树的二叉链表。 int createtree(node T,char x[],int l,int i){ int pr; if(i<=l) { } else T=NULL; return 1; } if(!(T=(node)malloc(sizeof(node)))) return 0; T->data=x[i-1]; pr=createtree(T->lchild,x,l,i*2); pr=createtree(T->rchild,x,l,i*2+1); 三、详细设计 #include using namespace std; typedef struct tree{ //定义二叉链表的结点 typedef tree * node; //类型替换 int createtree(node T,char x[],int l,int i){ //创建完全二叉树的二叉链表 int pr; if(i<=l) { } else T=NULL; return 1; } int main(){ int a,b,n; char x[n]; node T; cout<<\请输入完全二叉树一维数组的位数：\cin>>n; cout<<\请输入数组的值：\ for(a=0;a if(!(T=(node)malloc(sizeof(node)))) return 0; T->data=x[i-1]; pr=createtree(T->lchild,x,l,i*2); pr=createtree(T->rchild,x,l,i*2+1); char data; struct tree *lchild,*rchild; }tree; } } cin>>x[a]; b=0; b=createtree(T,x,n,1); //建立链表 if(b==1) //判断链表是否建立成功 cout<<\完全二叉树建立成功！\else cout<<\完全二叉树建立失败！\ system(\return 0; 四、调试分析 根据visual C++6.0编译器的提醒，修正代码错误，然后输入数据进行调试。输入数据，进行校验。 五、测试结果 示例1： 示例2： 六、说明（如果有） 第二题： 一、 需求分析 程序要求采用双序遍历访问二叉树。则首先建立以二叉树，然后采用双序遍历的方法访问二叉树。 二、概要设计 1.抽象数据类型 typedef struct work{ typedef work * node; 2.算法 char data; struct work *lchild,*rchild; }work; （1）.建立二叉树链表。 void create( node &T ){ char x; cout<<\请按先序输入二叉树的结点内容（若没有孩子，请输入*）：cin>>x; if ( x=='*' ) T=NULL; //读入根结点的值 else{ T=( node ) malloc ( sizeof( work )); if (!T) return; //建立根结点 create( T->lchild ); T->data=x; create( T->rchild ); \ } } （2）．双序遍历二叉树链表。 void double_visit(node &T){ cout<< T->data < if (T->lchild->data!='*') double_visit(T->lchild); cout<< T->data < if (T->rchild->data!='*') double_visit(T->rchild); } 二、 详细设计 #include