数据结构——二叉树的建立与遍历算法（实验报告）

 

 

实验名称：二叉树的建立与遍历算法          指导教师：       

实验日期：2022年  月  日 实验地点：            成绩：     

实验目的：

1、掌握二叉树的定义。

2、二叉树的链式存储结构及在链式存储结构中三种遍历（前序，中序，后序） *** 作的实现及应用。

实验内容：

编写程序，实现以下功能：

(1)建立一棵二叉树（以链表存储），对该二叉树进行遍历并输出该二叉树的前序，中序，后序遍历序列。要求前序、中序遍历用非递归方法，后序遍历用递归方法完成。

(2)实现二叉树左右子树的交换。

(3)统计二叉树中叶子结点个数。(要求用非递归算法完成)

基本要求：

1、写出完成实验内容的实验方法和源代码。

2、写出实验数据及运行结果。

3、写出在实验过程中所遇到的问题及解决办法。

实验源码

#include 
#include
#include
#define Maxsize 20
typedef 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;
		 }
	 }
 }