实验题目:树的应用

实验环境: CLion

实验目的:

1.熟悉树的存储结构;

2.熟悉二叉链表的创建;

3.熟悉二叉树的遍历操作。

实验内容:

  1. 依据顺序二叉树的存储结构:实现基于先序遍历思想实现二叉链表的创建,并输出其先序、中序和后序遍历的结果
    typedef struct BiNode{
    TElemType data;
    struct BiNode *lchild,*rchild; //左右孩子指针
    }BiNode,*BiTree;
  2. 统计上题创建的二叉树的叶结点个数
  3. 实现二叉树的层次遍历,转换成程序并上机实现(可以借用队列实现);
  4. (选做)实现二叉树遍历的非递归算法,转换成程序并上机实现(可以借助栈实现)

实现代码

BiTree.h

//二叉树结点定义
// Created by 17235 on 2020/4/18.
//

#ifndef CLION_WORKSPACE_BITREE_H
#define CLION_WORKSPACE_BITREE_H

#include <stdlib.h>
#include <stdio.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef struct BiNode{
TElemType data;
struct BiNode *lchild, *rchild;
}BiNode, *BiTree;

/*
* 按前序输入二叉树中结点的值(一次一个字符)
* # 表示空树,构造二叉链表表示二叉树T
*/
extern BiTree CreatBiTree(BiTree T);

/*
* 二叉树前序遍历递归算法
*/
extern void PerOrderTraverse(BiTree T);

/*
* 二叉树中序遍历递归算法
*/
extern void InOrderTraverse(BiTree T);

/*
* 二叉树后序遍历递归算法
*/
extern void PostOrderTraverse(BiTree T);

/*
* 统计二叉树中叶子结点的个数统计
*/
extern void BiTreeLeavesCount(BiTree T,int *count);

/*
* 调用计数函数,初始化count计数器
*/
extern int Count(BiTree T);

#endif //CLION_WORKSPACE_BITREE_H

BiTree.cpp

//二叉树基本操作函数
// Created by 17235 on 2020/4/18.
//
#include "BiTree.h"
#include <stdlib.h>
#include <stdio.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -2

/*
* 按前序输入二叉树中结点的值(一次一个字符)
* # 表示空树,构造二叉链表表示二叉树T
*/
BiTree CreatBiTree(BiTree T){
TElemType ch;
ch=getchar();
if(ch == '#'){
T = NULL;
return T;
}
T = (BiTree)malloc(sizeof(BiNode));
if(T == NULL){
exit(OVERFLOW);
}
//生成根结点
T->data = ch;
//构造左子树
T->lchild = CreatBiTree(T->lchild);
//构造右子树
T->rchild = CreatBiTree(T->rchild);
return T;

}

/*
* 二叉树前序遍历递归算法
*/
void PerOrderTraverse(BiTree T){
if (T == NULL){
return;
}
//这里输出结点数据
printf("%c",T->data);
//然后遍历左子树
PerOrderTraverse(T->lchild);
//最后遍历右子树
PerOrderTraverse(T->rchild);
}

/*
* 二叉树中序遍历递归算法
*/
void InOrderTraverse(BiTree T){
if (T == NULL){
return;
}
//然后遍历左子树
InOrderTraverse(T->lchild);
//这里输出结点数据
printf("%c",T->data);
//最后遍历右子树
InOrderTraverse(T->rchild);
}

/*
* 二叉树后序遍历递归算法
*/
void PostOrderTraverse(BiTree T){
if (T == NULL){
return;
}
//然后遍历左子树
PostOrderTraverse(T->lchild);
//最后遍历右子树
PostOrderTraverse(T->rchild);
//这里输出结点数据
printf("%c",T->data);
}

/*
* 统计二叉树中叶子结点的个数统计
*/
void BiTreeLeavesCount(BiTree T,int *count){
if(T!=NULL && T->lchild==NULL && T->rchild==NULL){
*count = *count + 1;
}
if(T){
BiTreeLeavesCount (T->lchild,count);/*先序遍历T的左子树*/
BiTreeLeavesCount (T->rchild,count);/*先序遍历T的右子数*/
}
return;
}

/*
* 调用计数函数,初始化count计数器
*/
int Count(BiTree T){
int count = 0;
BiTreeLeavesCount(T,&count);
return count;
}

Queue.h

// 队列定义
// Created by 17235 on 2020/4/18.
//

#ifndef CLION_WORKSPACE_QUEUE_H
#define CLION_WORKSPACE_QUEUE_H

#include "BiTree.h"

typedef int Status ;
typedef struct QNode{
BiTree data;
struct QNode *next;
}QNode,*QueuePtr;

typedef struct LinkQ{
QueuePtr front,rear;
}LinkQueue;

/*
* 队列初始化
*/
extern void InitQueue(LinkQueue *Q);

/*
* 队列入队操作
*/
extern Status EnQueue(LinkQueue *Q,BiTree e);

/*
* 队列出队操作
*/
extern Status DeQueue(LinkQueue *Q,BiTree *e);

#endif //CLION_WORKSPACE_QUEUE_H

Queue.cpp

//队列基本操作函数
// Created by 17235 on 2020/4/18.
//
#include <iostream>
#include "queue.h"
#include <stdlib.h>
#include "BiTree.h"

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status ;

/*
* 队列初始化
*/
void InitQueue(LinkQueue *Q){
Q->front=Q->rear=new QNode;
Q->front->next=NULL;
// QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
// //存储分配失败
// if (!s){
// exit(OVERFLOW);
// }
// Q->front=Q->rear=s;
// Q->front->next=NULL;
// return;
}

/*
* 队列入队操作
*/
Status EnQueue(LinkQueue *Q,BiTree e){
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
//存储分配失败
if (!s){
exit(OVERFLOW);
}
s->data = e;
s->next = NULL;
//把刚放进去e的结点s放到原来队尾,使之成为原队尾的后继
Q->rear->next = s;
//将队尾指针指rear向s
Q->rear = s;
free(s);
// delete s;
return OK;
}

/*
* 队列出队操作
*/
Status DeQueue(LinkQueue *Q,BiTree *e){
//若队列不为空,则删除队列的对头元素,并将其返回给e
QueuePtr p;
if ((Q->front == Q->rear)){
return ERROR;
}
p = Q->front->next;
Q->front->next = p->next;
//如果队头是队尾,则删除后将rear指向头结点
if (Q->rear == p){
Q->rear = Q->front;
}
*e = p->data;
free(p);
// delete p;
return OK;
}

Stack.h

//栈的定义
// Created by 17235 on 2020/4/24.
//

#ifndef CLION_WORKSPACE_STACK_H
#define CLION_WORKSPACE_STACK_H
#include "BiTree.h"
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
using namespace std;

/*
* 栈的结构体
*/
typedef struct
{
BiNode *base;
BiNode *top;
int stacksize;
}SqStack;

extern Status InitStack(SqStack &S);
extern StackEmpty(SqStack S);
extern StackLength(SqStack S);
extern int StackLength(SqStack S);
extern Status Push(SqStack &S,BiNode e);
extern Status Pop(SqStack &S,BiNode &e);
extern BiNode GetTop(SqStack S);

#endif //CLION_WORKSPACE_STACK_H

Stack.cpp

//
// Created by 17235 on 2020/4/24.
//
#include "Stack.h"
#include <stdlib.h>

//初始化栈
Status InitStack(SqStack &S){
S.base = new BiNode [MAXSIZE];
if (!S.base)
exit(OVERFLOW);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}

//判断栈满栈空
Status StackEmpty(SqStack S){
if(S.top == S.base)
return OK;
else return ERROR;
}

//求栈长
int StackLength(SqStack S){
return (S.top - S.base);
}

//入栈函数
Status Push(SqStack &S,BiNode e){
if(S.top - S.base == S.stacksize){
return ERROR;

}
else
*S.top++ = e;
return OK;
}

//出栈函数
Status Pop(SqStack &S,BiNode &e){
if(S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}

//取栈顶元素
BiNode GetTop(SqStack S){
if(S.top != S.base){
return *(S.top-1);
}
}

main.cpp

#include <iostream>
#include "BiTree.h"
#include "Queue.h"
#include "Stack.h"
extern void LevelOrder(BiTree T);
extern void InOrderTraverseNo(BiTree T);

int main() {
BiTree T = NULL;
printf("请以先序输入二叉树,以#结束:\n");
T = CreatBiTree(T);
printf("前序遍历:");
PerOrderTraverse(T);
printf("\n");
printf("中序遍历:");
InOrderTraverse(T);
printf("\n");
printf("后序遍历:");
PostOrderTraverse(T);
printf("\n");
printf("叶子结点个数:%d",Count(T));
printf("\n");
printf("层序遍历:");
LevelOrder(T);
printf("\n");
printf("(选做)二叉树中序遍历的非递归算法:");
InOrderTraverseNo(T);
return 0;
}

/*
* 二叉树借助队列进行层序遍历
*/
void LevelOrder(BiTree T){
LinkQueue *Q;
Q=(LinkQueue *)malloc(sizeof(LinkQueue));
InitQueue(Q);
EnQueue(Q,T);
while ( Q->rear != Q->front){
DeQueue(Q,&T);
printf("%c",T->data);
if (T->lchild != NULL){
EnQueue(Q,T->lchild);
}
if ( T->rchild != NULL ){
EnQueue(Q,T->rchild);
}
}
}

void InOrderTraverseNo(BiTree T) {
//中序遍历二叉树T的非递归算法
SqStack S;
InitStack(S);
BiTree p = T;
BiTree q = new BiNode;
while (p || !StackEmpty(S)) {
if(p) {//p非空
Push(S,*p); //根指针进栈
p=p->lchild; //根指针进栈, 遍历左子树
}else { //p为空
Pop(S,*q); //退栈
printf("%c",q->data); //访问根结点
p = q->rchild; //遍历右子树
}
} // while
}

测试用二叉树示意图

运行结果