open-graph-logo

156 次

一、实验目的

  1. 掌握二叉树的基本概念;
  2. 掌握二叉树的二叉链表的存储结构;
  3. 掌握利用括号法表示二叉树的的构建方法,以及先、中、后序遍历和层序遍历的实现。

二、实验相关知识

  1. 复习C语言文件读写的相关知识
  2. 复习课本中第6章关于数的相关知识点;

三、实验内容与要求

1.建立一棵用二叉链表方式存储的二叉树,并利用凹凸法进行二叉树的打印;并对其进行遍历(先序、中序、后序和层序),并打印输出遍历结果。

【设计要求】输入为括号法表示的二叉树字符串序列,补充完整以下函数,实现二叉链表的建立,二叉树的遍历、以及二叉树的竖向打印。

void CreateBiTree(BiTree *bt)

/*扩展的先序遍历结果构造二叉链表*/

void  PreOrder(BiTree root) /*先序遍历二叉树*/

void  PostOrder(BiTree root) /* 后序遍历二叉树*/

void  InOrder(BiTree root) /* 中序遍历二叉树的非递归算法 */

int   LayerOrder(BiTree bt) /* 层序遍历二叉树 */

void  PrintTree(BiTree bt,int nLayer)  /* 按竖向树状打印的二叉树 */

【测试用例】设有以下的二叉树:

则添加空孩子进行扩展之后:

  1. 输入:A(B(C,D(E,F(G))))
  2. 输出:

先序遍历:ABCDEFG

中序遍历:CBEDGFA

后序遍历:CEGFDBA

层序遍历:ABCDEFG

打印二叉树:

A
F
G
D

E
B
C

四、程序代码及运行结果

【程序代码】

#include<stdio.h>
#include <malloc.h>
#include <conio.h>
typedef char DataType;
//二叉链表的结点结构定义 
typedef struct Node
{
	DataType data;
	struct Node *LChild;
	struct Node *RChild;
}BiTNode, *BiTree;
typedef BiTree StackElementType;
typedef BiTree QueueElementType;
#include"stack.h" 
#include"queue.h" 
//构造二叉链表 
void CreateBiTree(BiTNode *&bt, char *str1)
{
	BiTNode *St[Stack_Size], *p = NULL;
	int top = -1, k = 0, j = 0;
	char ch;
	bt = NULL;
	ch = str1[j];
	while (ch != '\0')
	{
		switch (ch)
		{
		case '(':top++;
			St[top] = p;
			k = 1;
			break;
		case ')':top--;
			break;
		case ',':k = 2;
			break;
		default:p = (BiTNode *)malloc(sizeof(BiTNode));
			p->data = ch;
			p->LChild = p->RChild = NULL;
			if (bt == NULL)
				bt = p;
			else
			{
				switch (k)
				{
				case 1:St[top]->LChild = p; break;
				case 2:St[top]->RChild = p; break;
				}
			}
		}
		j++;
		ch = str1[j];
	}

}

void Visit(BiTree root)
{
	if (root != NULL)
		printf("%c ", root->data);
}

/*先序遍历二叉树, root为指向二叉树根结点的指针*/
void  PreOrder(BiTree root)
{
	if (root != NULL)
	{
		printf("%c ", root->data);
		PreOrder(root->LChild);
		PreOrder(root->RChild);
	}
}

/* 后序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/
void  PostOrder(BiTree root)
{
	if (root != NULL)
	{
		PostOrder(root->LChild);
		PostOrder(root->RChild);
		printf("%c ", root->data);
	}
}
void  InOrder(BiTree root) /* 中序遍历二叉树的非递归算法 */
{
	if (root != NULL)
	{
		InOrder(root->LChild);
		printf("%c ", root->data);
		InOrder(root->RChild);
	}
}

void PrintTree(BiTree bt, int nLayer)  /* 按竖向树状打印的二叉树 */
{
	if (bt == NULL)
		return;
	PrintTree(bt->RChild, nLayer + 3);
	for (int i = 0; i < nLayer; i++)
		printf(" ");
	printf("%c\n", bt->data);
	PrintTree(bt->LChild, nLayer + 3);
}

void LayerOrder(BiTree bt) /* 层序遍历二叉树 */
{
	BiTree p;
	BiTree qu[Stack_Size];
	int front, rear;
	front = rear = -1;
	rear++;
	qu[rear] = bt;
	while (front != rear)
	{
		front = (front + 1) % Stack_Size;
		p = qu[front];
		printf("%c ", p->data);
		if (p->LChild != NULL)
		{
			rear = (rear + 1) % Stack_Size;
			qu[rear] = p->LChild;
		}
		if (p->RChild != NULL)
		{
			rear = (rear + 1) % Stack_Size;
			qu[rear] = p->RChild;
		}
	}
}/* LayerOrder */

int main()
{
	BiTNode *T;
	//char str1[] = " ";   //请输入括号法表示的二叉树序列
	char str1[Stack_Size];
	printf("请输入括号法表示的二叉树序列:");
	gets_s(str1);
	printf("括号法表示的二叉树序列为%s:\n", str1);
	CreateBiTree(T, str1);
	printf("先序遍历输出序列为:");
	PreOrder(T);
	printf("\n中序遍历输出序列为:");
	InOrder(T);
	printf("\n后序遍历输出序列为:");
	PostOrder(T);
	printf("\n层序遍历输出序列为:");
	LayerOrder(T);
	printf("\n竖向打印二叉树:\n");
	PrintTree(T, 1);
	_getch();
	return 0;
}

【运行结果】

五、实验心得体会

巩固了二叉树的知识。

赞赏

微信赞赏支付宝赞赏

评论

电子邮件地址不会被公开。 必填项已用*标注

CAPTCHAis initialing...

%d 博主赞过: