数据结构与算法 实验二 二叉树的建立与遍历算法（C语言版）

实验目的：

1、掌握二叉树的定义。

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

实验内容：

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

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

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

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

基本要求：

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

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

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

实验方法:

1.二叉树采用链式存储结构，以链表实现，每个节点里面有一个数据和两个左右子树节点的指针。

2.前序和中序遍历还有统计二叉树中叶子节点个数采用非递归算法完成，使用栈来实现。

3.后续遍历则采用递归，递归实质上也是使用栈实现的。

4.左右树的交换利用一个辅助指针，将根节点的左右子树节点交换。

5.我在本次实验基础上还增加了一个输出二叉树的功能，首先根据二叉树的高度和宽度创建一个动态的二维数组，在通过前序遍历的方法将每个节点的数据存入数组中，同时向数组中填入连线和空格，最终通过输出数组打印二叉树。

代码图：

 代码部分：

#include
#include 
#include
#define MaxSize 20
//链二叉树类型
typedef struct Node
{
	int data;		
	struct Node* lchild;//左孩子节点
	struct Node* rchild;//右孩子节点
}*BinaryTree;
int width = 0, height = 0;
//创建二叉树
BinaryTree CreatTree()
{
	int data;
	BinaryTree tree;
	scanf_s("%d",&data);
	int temp = getchar();  //吸收空格
	if (data==-1)
	{
		return NULL;       //数据域为-1代表此节点不存数据，左右子节点指针置为NULL，不继续指向子节点
	}
	else
	{
		tree = (BinaryTree)malloc(sizeof(Node));
		if (tree != NULL)
		{
			tree->data = data;
			printf("请输入%d树的左叶子节点的值!n",data);
			tree->lchild = CreatTree();
			printf("请输入%d树的右叶子节点的值!n",data);
			tree->rchild = CreatTree();
			return tree;
		}
	}
}
//求树的高度
int TreeHeight(BinaryTree tree)
{
	int lchildh, rchildh;
	if (tree == NULL)
	{
		return 0;
	}
	else
	{
		lchildh = TreeHeight(tree->lchild);
		rchildh = TreeHeight(tree->rchild);
		return (lchildh > rchildh ? lchildh+1 : rchildh+1);
	}
}
//非递归前序遍历
void FrontPrint(BinaryTree tree)
{
	    BinaryTree Stack[MaxSize], node = NULL;	//创建栈,创建节点
		int top = -1;		  //栈顶指针  
		if (tree != NULL)     //如果树不为空
		{
			Stack[0] = tree;  //根节点入栈
			top++;
			while (top!=-1)   //如果栈不为空
			{
				node = Stack[top];
				printf("%dt",node->data);//出栈
				top--;
				if (node->rchild != NULL)
				{
					Stack[++top] = node->rchild;//右孩子不为空先进栈
				}
				if (node->lchild != NULL)
				{
					Stack[++top] = node->lchild;//左孩子不为空先进栈
				}
			}
	}
}
//非递归中序遍历
void MiddlePrint(BinaryTree tree)
{ 
	BinaryTree stack[MaxSize], node = NULL;//创建栈
	int top = -1;	                       //栈顶指针
	while (top!=-1 || tree!=NULL)          //栈或树非空
	{
		while (tree!=NULL)
		{
			stack[++top] = tree;
			tree = tree->lchild;
		}
		if (top!=-1)
		{
			node = stack[top--];
			printf("%dt", node->data);
		    tree = node->rchild;
		}
	}
}
//后序遍历
void LastPrint(BinaryTree tree)
{
	if (tree == NULL)
	{
		return;//遍历到的当前节点如果为空则返回
	}
	LastPrint(tree->lchild);
	LastPrint(tree->rchild);
	printf("%dt", tree->data);
	
}
//左右树的交换
void ChangeTree(BinaryTree tree)
{
	if (tree == NULL)
	{
		printf("树为空，左右树交换失败！n");
	}
	else 
	{
		BinaryTree temp; //辅助交换的指针
		temp = tree->rchild;
		tree->rchild = tree->lchild;
		tree->lchild = temp;
		printf("n左右子树交换成功!nn");
	}
}
//统计叶子节点个数
int CalTreeLeaf(BinaryTree tree)
{
	int top = -1; // 栈为空
	int count = 0;
	BinaryTree s[MaxSize]; //创建栈

	while (tree != NULL || top != -1) // 当前节点不为空或栈不为空
	{
		while (tree != NULL) // 当前节点不为空
		{
			if (tree->lchild == NULL && tree->rchild == NULL) // 若当前根节点的左右子树都为空，则是叶子节点
				count++;
			s[++top] = tree; // 先 ++top，然后将当前的根节点入栈

			tree = tree->lchild; // 然后访问当前根节点的左子树

		}
		if (top != -1) // 栈不为空
		{
			tree = s[top--]; 
			tree = tree->rchild; 
		}
	}

	return count;
}//打印二叉树
//打印二叉树
void Print(BinaryTree tree, char* a, int i, int j)//a是数组 i,j是当前节点在数组中的位置
{
	int ti, tj;
	if (tree!=NULL) //如果该位置有节点
	{
		*(a + (i * width) + j) = tree->data+48; //向数组该点填入字符
		if (tree->lchild!=NULL) //有左右孩子给对应的连接线,左右孩子的值在下一层递归赋值
		{
			for (ti = i + 1, tj = j - 1; tj > j - (height - i + 1) / 2; tj--)//将该点与其左孩子之间的连线全部填上'/'
			{
				*(a + ((ti)*width) + tj) = '/';
				ti++;
			}
		}
		if (tree->rchild!=NULL)
		{
			for (ti = i + 1, tj = j + 1; tj < j + (height - i + 1) / 2; tj++)
			{
				*(a + ((ti)*width) + tj) = '\';
				ti++;
			}
		}
		if (tree->lchild == NULL && tree->rchild == NULL)
			return;
		Print(tree->lchild, a, ti, j - (height - i + 1) / 2);//经过循环,ti恰好指到其孩子所在的层
		Print(tree->rchild, a, ti, j + (height - i + 1) / 2);
	}
}
void printTree(BinaryTree tree)
{
	int i, j;
	int n = TreeHeight(tree); //计算高度
	width = (2 << n) - 3;  // 2^(n+1)-3   一个数据左移1位就相当于乘以2的1次方
	height = (2 << (n - 1)) - 1; // 2^n-1
	char* a = (char*)malloc(sizeof(char) * (width * height));
	memset(a, 0, sizeof(char) * (width * height));//数组初始化
	Print(tree, a, 0, (width - 1) / 2);	//调用Print函数,填充打印数组
	for (i = 0; i < height; i++)
	{
		for (j = 0; j < width; j++)
		{
			if (*(a + (i * width) + j) == '/')
			{
				printf("/");
			}
			else if (*(a + (i * width) + j) == '\')
			{
				printf("\");
			}
			else if (*(a + (i * width) + j) == 0)
			{
				printf(" ");
			}
			else
			{
				printf("%c", *(a + (i * width) + j));
			}
		}
		printf("n");
	}
}
int main()
{
	BinaryTree tree=NULL;
	int choice = 0,h=0,num=0;
	while (choice != 8)
	{
		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("*******************************n");
		scanf_s("%d", &choice);
		switch (choice)
		{
		case 1:
			printf("n请输入树的节点的值!(节点类型为整型，空节点用-1表示)n");
			tree = CreatTree();//创建二叉树
			system("cls");
			printf("n创建成功!n");
			printTree(tree);//打印二叉树
			break;
		case 2:
			system("cls");
			printTree(tree);
			printf("n前序遍历结果为:n");
			FrontPrint(tree);//非递归前序遍历
			printf("nn");
			break;
		case 3:
			system("cls");
			printTree(tree);
			printf("n中序遍历结果为:n");//非递归中序遍历
			MiddlePrint(tree);
			printf("nn");
			break;
		case 4:
			system("cls");
			printTree(tree);
			printf("n后续遍历结果为:n");
			LastPrint(tree);  //递归后序遍历
			printf("nn");
			break;
		case 5:
			system("cls");
			printTree(tree);
			h = TreeHeight(tree);
			printf("n树的高度为:%dnn", h);
			break;
		case 6:
			system("cls"); 
			printTree(tree);
			ChangeTree(tree);
			printTree(tree);
			break;
		case 7:
			system("cls");
			printTree(tree);
			num = CalTreeLeaf(tree);
			printf("n叶子结点个数为:%dn",num);
			break;
		case 8:
			break;
		default:
			system("cls");
			printf("n没有此选项，请重新选择!nn");
			break;
		}
	}
}

实验数据

创建二叉树 

前序遍历

中序遍历

后续遍历

求树的高度

左右子树交换

统计叶子节点个数

实验总结略