目录
题目一.二叉树操作（1）二.算术表达式求 (1)
一、课程设计的目的 (1)
二、课程设计的内容和要求 (1)
三、题目一设计过程 (2)
四、题目二设计过程 (6)
五、设计总结 (17)
六、参考文献 (18)
题目一.二叉树操作（1）二.算术表达式求
一、课程设计的目的
本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。
（1）题目一的目的：
1、掌握二叉树的概念和性质
2、掌握二叉树的存储结构
3、掌握二叉树的基本操作
（2）题目二的目的：
1、掌握栈的顺序存储结构和链式存储结构
2、掌握栈的先进后出的特点
3、掌握栈的基本运算
二、课程设计的内容和要求
（1）题目一的内容和要求：
1、编写已知二叉树的先序、中序序列，恢复此二叉树的程序
2、编写求二叉树深度的程序
（2）题目二的内容和要求：
1、算术表达式由操作数、运算符和界限符组成。操作数是正整数，运算符为
加减乘除，界限符有左右括号和表达式起始
2、将一个表达式的中缀形式转化为相应的后缀形式
3、依据后缀表达式计算表达式的值
三、题目一设计过程
1、题目分析
现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！
由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后返回其中大的那个值加一，则求出数的高度。这里用递归实现！
2、算法描述
main ( )（主函数）
先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。
void CreateBiTree(BiTree *T,char *pre,char *in,int len)（由先序序列和中序序列构造二叉树）
根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序列为左子树, 后边的序列为右子树。设根前边有n个元素，则又有, 在前序序列中，紧跟着根(root)的n个元素序列(即pre[1...n]) 为左子树, 在后边的为右子树，而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为pre[1...n]), 中序序列为in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现！
int Depth(BiTree T)（求树的深度）
当所给的参数T是NULL时，返回0。说明这个树只有一个叶子节点深度为0，当所给的参数不是NULL时，函数调用自己看看这个参数的左分支是不是NULL，
如果不是继续调用自己看看左分支的左分支是不是NULL，直到最后一个的左分支是NULL。然后看与最后一个左分支并列的右分支是不是NULL，不是的话自动调用自己，直到是NULL。同理求出右分支，然后左分支深度和右分支深度比较，返回值大的作为深度。
3、源代码
#include
#include
typedef struct Node
{
char data;
struct Node *lchild;
struct Node *rchild;
}*BiTree,BitNode;
void InitBitTree(BiTree *T);//初始化一棵树
void CreateBiTree(BiTree *T,char *pre,char *in,int len);//由先序序列和中序序列构造二叉树
int Depth(BiTree T);//求树的深度
void main()
{
BiTree T;
InitBitTree(&T);
char a[50],b[50];
int i,len=0,j;
printf("请输入一棵二叉树的先序序列：");
gets(a);
printf("请输入一棵二叉树的中序序列：");
gets(b);
for(i=0;i<50;i++)
{
if(a[i]!='\0')
len++;
else
break;
}
CreateBiTree(&T,a,b,len);
j=Depth(T);
printf("这棵树的深度是：%d\n",j);
}
void InitBitTree(BiTree *T)//初始化一棵树
{
*T=NULL;
}
void CreateBiTree(BiTree *T,char *pre,char *in,int len)//由先序序列和中序序列构造二叉树
{
int k;
char *temp;
if(len<=0)
{
*T=NULL;
