一、实验目的

1、掌握用指针类型描述、访问和处理二叉树的操作。

2、理解二叉树的结构特性，以及各种存储结构的特点及适用范围。

3、设计并编程实现树型结构基本运算的实验程序。

4、熟练掌握二叉搜索树的建立及元素遍历方法。

5、熟悉哈夫曼树的构造及哈夫曼编码的实现方法。

二、程序源码

#include"pch.h"
#include <stdio.h>
#include "stdlib.h"
#include <conio.h>
#include <string.h>
#define NULL       0
#define MAXSIZE    100         //最大存储元素个数，可调

typedef int DataType;           //自定义数据类型，可调
typedef struct trnode {
    DataType data;
    struct trnode *lchild, *rchild;
}BITREE;

typedef struct stacktag {
    BITREE* data[MAXSIZE];
    int top;
} STACK;

STACK *s;                   /*s--是顺序栈类型的指针*/
BITREE *creat();                /*建立二叉树*/
void PreOrder(BITREE *tr);     /*先序遍历二叉树*/
void PostOrder(BITREE *tr);    /*后续遍历二叉树*/
void InOrder(BITREE *tr);       /*中序遍历二叉树*/
void exchange(BITREE *tr);      /*借助堆栈实现的交换函数*/
void exchange2(BITREE *tr); /*递归方式实现的交换函数*/
void PostOrder(BITREE *tr); /*后序遍历释放结点*/

int main() {
    STACK mystk;
    BITREE *root;
    s = &mystk;
    printf("输入二叉树结点的值（每个分支均以0结束输入）:\n");
    root = creat();
    printf("先序遍历结果:\n");
    PreOrder(root);
    printf("\n");
    printf("中序遍历结果为：\n");
    InOrder(root);
    printf("\n");
    printf("后续遍历结果为:\n");
    PostOrder(root);
    printf("\n");
    exchange(root);
    printf("交换后中序遍历结果为：\n");
    InOrder(root);
    printf("\n");
    printf("交换后先序遍历结果:\n");
    PreOrder(root);
    printf("\n");
    printf("交换后后续遍历结果为:\n");
    PostOrder(root);
    printf("\n");
    exchange2(root);
    printf("再交换后先序遍历结果:\n");
    PreOrder(root);
    printf("\n");
    printf("再交换后中序遍历结果为：\n");
    InOrder(root);
    printf("\n");
    printf("再交换后后续遍历结果为:\n");
    PostOrder(root);
    printf("\n");
    PostOrder(root);
    return 1;
} /* main */

BITREE *creat() {               /*建立二叉树*/
    BITREE *tr;
    DataType x;
    scanf_s("%d", &x);
    if (x == 0) tr = NULL;
    else {
        tr = (BITREE *)malloc(sizeof(BITREE));
        tr->data = x;
        tr->lchild = creat();
        tr->rchild = creat();
    }
    return tr;
}

void PreOrder(BITREE *tr)      /*先序遍历二叉树*/
{
    if (tr != NULL)
    {
        printf("% 4d",tr->data);
        PreOrder(tr->lchild);
        PreOrder(tr->rchild);
    }
}
void InOrder(BITREE *tr) {      /*中序遍历二叉树*/
    if (tr != NULL) {
        InOrder(tr->lchild);
        printf("%4d", tr->data);
        InOrder(tr->rchild);
    }
}/* end of InOrder */

void PostOrder(BITREE *tr)    /*后续遍历二叉树*/
{
    if (tr != NULL)
    {
        PostOrder(tr->lchild);
        PostOrder(tr->rchild);
        printf("% 4d" ,tr->data);
    }
}
void exchange(BITREE *tr) {     /*借助堆栈实现的交换函数*/
    BITREE *p, *t;
    if (tr != NULL) {
        s->top = 1;
        s->data[s->top] = tr;       /*根指针进栈*/
        do {
            t = s->data[s->top];
            s->top--;
            if ((t->lchild != NULL) || (t->rchild != NULL)) {
                p = t->lchild;
                t->lchild = t->rchild;
                t->rchild = p;
            }
            if (t->lchild != NULL) {    /*交换后的左孩子指针入栈*/
                s->top++;
                s->data[s->top] = t->lchild;
            }
            if (t->rchild != NULL) {    /*交换后的右孩子指针入栈*/
                s->top++;
                s->data[s->top] = t->rchild;
            }
        } while (s->top != 0);      /*栈空结束*/
    }
}/* end of exchange */

void exchange2(BITREE *tr) {        /*递归方式实现的交换函数*/
    BITREE *p;
    if (tr != NULL) {
        p = tr->lchild;
        tr->lchild = tr->rchild;
        tr->rchild = p;
        exchange2(tr->lchild);
        exchange2(tr->rchild);
    }
}

三、运行截图

四、思考题

在“二叉树结点交换程序”的main函数中，s=&mystk;语句的作用是什么？如果不定义mystk变量，程序应该怎样修改？

答：作用是为顺序桟类型的指针s建立一个地址，便于后面在桟堆中实现二叉树节点的交换。

在“二叉搜索树程序”中，如果每个结点的数据是字符串，如何修改程序？

在输入扫描的时候用

scanf(“%c”,&x);

并且在输出的时候将%d改成%c，在判断是否为空时用Null判断。

五、心得体会

通过本次实验了解了树和二叉树的各种功能及应用。增长了这种算法相关程序的编写。