实验名称：二叉树的建立与遍历算法 指导教师：
实验日期：月日 实验地点：成绩：
实验目的：
1、掌握二叉树的定义。
2、二叉树的链式存储结构及在链式存储结构中三种遍历（前序，中序，后序）操作的实现及应用。
实验内容：
编写程序，实现以下功能：
(1)建立一棵二叉树（以链表存储），对该二叉树进行遍历并输出该二叉树的前序，中序，后序遍历序列。要求前序、中序遍历用非递归方法，后序遍历用递归方法完成。
(2)实现二叉树左右子树的交换。
(3)统计二叉树中叶子结点个数。(要求用非递归算法完成)
基本要求：
1、写出完成实验内容的实验方法和源代码。
2、写出实验数据及运行结果。
3、写出在实验过程中所遇到的问题及解决办法。
实验源码
#include <stdio.h>#include<stdlib.h>#include<string.h>#define Maxsize 20typedef struct Node{int date;struct Node* lchild;//左孩子节点struct Node* rchild;//右孩子节点}*binraytree;//创建二叉树binraytree CreatTree(){binraytree tree;int temp = getchar(); int data = getchar();if (data == 48)//空节点以0表示{return NULL; }else{tree = (binraytree)malloc(sizeof(Node));if (tree != NULL){tree->date = data;printf("请输入%c树的左叶子节点的值!\n", data);tree->lchild = CreatTree();printf("请输入%c树的右叶子节点的值!\n", data);tree->rchild = CreatTree();return tree;}}}int treehight(binraytree tree)//获取树的高度{int lchildh, rchildh;if (tree == NULL){return 0;}else{lchildh = treehight(tree->lchild);rchildh = treehight(tree->rchild);return (lchildh > rchildh ? lchildh + 1 : rchildh + 1);}}void FrontPrint(binraytree tree)//前序非递归遍历{binraytree st[Maxsize], node = NULL;int top = -1;if (tree != NULL){st[0] = tree;top++;while (top != -1) //如果栈不为空{node = st[top];printf("%c\t", node->date);//出栈top--;if (node->rchild != NULL){st[++top] = node->rchild;//右孩子不为空先进栈}if (node->lchild != NULL){st[++top] = node->lchild;//左孩子不为空先进栈}}}}void Midlideprint(binraytree tree)//非递归中序遍历{binraytree st[Maxsize], node = NULL;int top = -1;while (top != -1 || tree != NULL)//栈或树非空{while (tree != NULL){st[++top] = tree;tree = tree->lchild;}if (top != -1){node = st[top--];printf("%c\t", node->date);tree = node->rchild;}}}void LastPrint(binraytree tree)//后序递归调用{if (tree == NULL){return;//遍历到的当前节点如果为空则返回}LastPrint(tree->lchild);LastPrint(tree->rchild);printf("%c\t", tree->date);}void Changetree(binraytree tree)//左右子树交换{if (tree != NULL){binraytree temp;temp = tree->lchild;tree->lchild = tree->rchild;tree->rchild = temp;printf("左右子树交换成功\n");}else{printf("左右子树交换失败\n");}}int Growtree(binraytree tree)//非递归计算树的叶子数{int top = -1;binraytree st[Maxsize];int count = 0;while (tree != NULL || top != -1){while (tree != NULL) // 当前节点不为空{if (tree->lchild == NULL && tree->rchild == NULL) // 若当前根节点的左右子树都为空，则是叶子节点count++;st[++top] = tree; // 先 ++top，然后将当前的根节点入栈tree = tree->lchild; // 然后访问当前根节点的左子树}if (top != -1) // 栈不为空{tree = st[top--];tree = tree->rchild;}}return count;}void GetTree(binraytree tree, int type, int level){int i;if (NULL == tree)return;GetTree(tree->rchild, 2, level + 1);switch (type){case 0:printf("%2c\n", tree->date);break;case 1:for (i = 0; i < level; i++)printf("\t");printf("\\\n");for (i = 0; i < level; i++)printf("\t");printf(" %2c\n", tree->date);break;case 2:for (i = 0; i < level; i++)printf("\t");printf(" %2c\n", tree->date);for (i = 0; i < level; i++)printf("\t");printf("/\n");break;}GetTree(tree->lchild, 1, level + 1);}void travlevel(binraytree tree){binraytree qu[Maxsize];int front, rear;front = rear = 0;if (tree != NULL)printf("%c",tree->date);rear++;qu[rear] = tree;while (rear != front){front = (front + 1) % Maxsize;tree = qu[front];if (tree->lchild != NULL){printf("%2c", tree->lchild->date);rear = (rear + 1) % Maxsize;qu[rear] = tree->lchild;}if (tree->rchild != NULL){printf("%2c", tree->rchild->date);rear = (rear + 1) % Maxsize;qu[rear] = tree->rchild;}}}int main(){binraytree tree = NULL;int choice = 0, h = 0, num = 0;while (choice != 9){printf("*******************************\n");printf("***1.创建二叉树 ***\n");printf("***2.前序遍历 ***\n");printf("***3.中序遍历 ***\n");printf("***4.后序遍历 ***\n");printf("***5.求树的高度 ***\n");printf("***6.左右子树交换***\n");printf("***7.统计叶子结点个数 ***\n");printf("***8.层次遍历序列***\n");printf("***9.退出 ***\n");printf("*******************************\n");scanf_s("%d", &choice);switch (choice){case 1:printf("\n请输入树的节点的值!\n");tree = CreatTree();//创建二叉树system("cls");printf("\n创建成功!\n");GetTree(tree,num,h);break;case 2:system("cls");GetTree(tree, num, h);printf("\n前序遍历结果为:\n");FrontPrint(tree);//非递归前序遍历printf("\n\n");break;case 3:system("cls");GetTree(tree, num, h);printf("\n中序遍历结果为:\n");//非递归中序遍历Midlideprint(tree);printf("\n\n");break;case 4:system("cls");GetTree(tree, num, h);printf("\n后序遍历结果为:\n");LastPrint(tree); //递归后序遍历printf("\n\n");break;case 5:system("cls");GetTree(tree, num, h);h = treehight(tree);printf("\n树的高度为:%d\n\n", h);break;case 6:system("cls"); GetTree(tree, num, h);Changetree(tree);GetTree(tree, num, h);break;case 7:system("cls");GetTree(tree, num, h);num = Growtree(tree);printf("\n叶子结点个数为:%d\n", num);break;case 8:system("cls");GetTree(tree, num, h);printf("\n层次遍历为:\n");travlevel(tree);printf("\n\n");break;case 9:break;default:system("cls");printf("\n没有此选项，请重新选择!\n\n");break;}}}
