要求
二叉树的链式存储结构创建
二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历
主函数功能菜单创建
二叉树的遍历算法可以使用递归的思想来实现。递归是一种自我调用的算法设计方法，适用于解决问题具有相同子问题结构的情况。
前序遍历的递归思想：
- 如果当前节点为空，直接返回。
- 访问当前节点。
- 递归地前序遍历左子树。
- 递归地前序遍历右子树。
中序遍历和后序遍历的递归思想也类似，在访问当前节点的位置不同而已。可以通过类似的递归思想实现中序遍历和后序遍历的算法。
使用递归思想实现二叉树的遍历，可以简化代码的实现，并且符合二叉树的自然结构。但是在实际应用中，如果二叉树的高度很大，递归的层次也会相应增加，可能会导致栈溢出的问题。因此，在处理大规模二叉树时，需要考虑使用迭代或其他非递归的方法来实现遍历算法。
代码实现及运行结果
（1）源程序代码
代码语言：c复制#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
int data; // 存放数据域
struct Tree *lchild; // 遍历左子树指针
struct Tree *rchild; // 遍历右子树指针
}Tree,*BitTree;
BitTree CreateLink()
{
int data;
int temp;
BitTree T;
scanf("%d",&data); // 输入数据
temp=getchar(); // 吸收空格
if(data == -1){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建
return NULL;
}else{
T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间
T->data = data; // 把当前输入的数据存入当前节点指针的数据域中
printf("请输入%d的左子树: ",data);
T->lchild = CreateLink(); // 开始递归创建左子树
printf("请输入%d的右子树: ",data);
T->rchild = CreateLink(); // 开始到上一级节点的右边递归创建左右子树
return T; // 返回根节点
}
}
// 先序遍历
void ShowXianXu(BitTree T) // 先序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层节点
{
return;
}
printf("%d ",T->data);
ShowXianXu(T->lchild); // 递归遍历左子树
ShowXianXu(T->rchild); // 递归遍历右子树
}
// 中序遍历
void ShowZhongXu(BitTree T) // 先序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层节点
{
return;
}
ShowZhongXu(T->lchild); // 递归遍历左子树
printf("%d ",T->data);
ShowZhongXu(T->rchild); // 递归遍历右子树
}
// 后序遍历
void ShowHouXu(BitTree T) // 后序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层节点
{
return;
}
ShowHouXu(T->lchild); // 递归遍历左子树
ShowHouXu(T->rchild); // 递归遍历右子树
printf("%d ",T->data);
}
int PostTreeHeight(BitTree T){
//通过后序遍历实现求树的高度
int h = 0, hl = 0, hr = 0;
if (T==NULL){
return 1;
}else{
hl = PostTreeHeight(T->lchild);//递归遍历左子树
hr = PostTreeHeight(T->rchild);//递归遍历右子树
h = (hr > hl)?hr:hl 1;//三目运算符，很简单
//如果hr大于hl，那么就取hr的值，然后hr 1赋值给h
//如果hr不大于h1，那么就取hl得值，然后hl 1赋值给h
return h;
}
}
int main()
{
BitTree S;
printf("请输入第一个节点的数据:n");
S = CreateLink(); // 接受创建二叉树完成的根节点
int a;
printf("1.先序n");
printf("2.中序n");
printf("3.后序n");
printf("4.树高n");
for(;;){
scanf("%d",&a);
if(a==1){
printf("n先遍历结果: n");
ShowXianXu(S); // 先序遍历二叉树
printf("n");
}else if(a==2){
printf("n中序遍历结果: n");
ShowZhongXu(S); // 中序遍历二叉树
printf("n");
}else if(a==3){
printf("n后序遍历结果: n");
ShowHouXu(S); // 后序遍历二叉树
printf("n");
}else if(a==4){
printf("树高：%dn",PostTreeHeight(S));
printf("n");
}
}
return 0;
} （2）运行结果
请输入第一个节点的数据:
1
请输入1的左子树: 2
请输入2的左子树: -1
请输入2的右子树: -1
请输入1的右子树: 3
请输入3的左子树: 2
请输入2的左子树: -1
请输入2的右子树: -1
请输入3的右子树: 3
请输入3的左子树: -1
请输入3的右子树: -1
1.先序
2.中序
3.后序
4.树高
1
先遍历结果:
1 2 3 2 3
2
中序遍历结果:
2 1 2 3 3
3
后序遍历结果:
2 2 3 3 1
4
树高：3
总结
遇到问题：
递归异常，忘记生成树的时候申请空间，和节点异常，定义了数据为%d类型，输入了整个字符串导致
核心代码
代码语言：text复制// 中序遍历
void ShowZhongXu(BitTree T) // 先序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层节点
{
return;
}
ShowZhongXu(T->lchild); // 递归遍历左子树
printf("%d ",T->data);
ShowZhongXu(T->rchild); // 递归遍历右子树
}中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果
