博客

本次课程设计主要含三部分内容，并且每一部分内容独立为一个小的课程设计

1.二叉树的建立及其非递归的先序、中序、后序遍历；



2.二叉树的层序遍历



3.排序二叉树的创建及中序遍历输出

• 首先我们来实现第一小部分的内容，先序递归构建二叉树并按非递归的方法对其进行先序、中序和后序遍历。

接下来我们用下面这颗二叉树作为我们示例进行演示，我们示例二叉树长这样：

在前序遍历生成二叉树中，我们用‘#’表示结点为NULL，因此前序遍历生成二叉树时的输入序列应该为：”abd#h##k##cef##g##m##”。通过CreateTree()函数我们就建立起了一颗如上图所示的二叉树，然后就可以愉快的开始各种遍历测试了，具体代码如下：

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

typedef struct treeNode{
    char data;
    struct treeNode*rchild, *lchild;
}TreeNode;

char str[] = "abd#h##k##cef##g##m##";
int pos = 0;

void CreateTree(TreeNode** T)
{//前序递归创建二叉树
    char ch;
    //scanf("%c", &ch);//读入字符
    ch = str[pos++];
    if (ch == '#')//.代表空子树
        *T = NULL;
    else
    {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        if (!(*T))
        {
            printf("开辟内存失败\n");
            exit(1);
        }
        (*T)->data = ch;//给T赋值
        CreateTree(&(*T)->lchild);//给左子树赋值
        CreateTree(&(*T)->rchild);//给右子树赋值
    }
}

void preorderTraversal(TreeNode* root)
{
    if (!root)
        return;

    TreeNode* stack[10]; int top = -1;
    stack[++top] = root;

    while (top > -1)
    {
        TreeNode* temp = stack[top--];
        printf("%c ", temp->data);
        
        if (temp->rchild)
            stack[++top] = temp->rchild;
        if (temp->lchild)
            stack[++top] = temp->lchild;
    }

}
void midorderTraversal(TreeNode* root)
{//中序非递归遍历二叉树

    TreeNode *stack[10]; int top = -1;
    TreeNode *p = root;
    while (p != NULL || top > -1)
    {
        while (p != NULL)
        {
            stack[++top] = p;
            p = p->lchild;
        }
        if (top > -1)
        {
            p = stack[top];
            printf("%c ", p->data);
            --top;
            p = p->rchild;
        }
    }

}

typedef struct tempNode{
    TreeNode* btnode;
    bool isFirst;
}TempNode;
void postorderTraversal(TreeNode* root)
{//后续非递归遍历二叉树
    TempNode *stack[10]; int top = -1;
    TreeNode *p = root;
    TempNode *temp;
    while (p != NULL || top > -1)
    {
        while (p != NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
        {
            TempNode *tempNode = new TempNode;
            tempNode->btnode = p;
            tempNode->isFirst = true;
            stack[++top] = tempNode;
            p = p->lchild;
        }
        if (top > -1)
        {
            temp = stack[top--];
            if (temp->isFirst == true)   //表示是第一次出现在栈顶
            {
                temp->isFirst = false;
                stack[++top] = temp;
                p = temp->btnode->rchild;
            }
            else  //第二次出现在栈顶
            {
                printf("%c ", temp->btnode->data);
                p = NULL;
            }
        }
    }
}

int choice()
{
    printf("*********欢迎来到二叉树非递归遍历演示界面************\n");
    printf("0-退出\n");
    printf("1-显示前序非递归遍历结果\n");
    printf("2-显示中序非递归遍历结果\n");
    printf("3-显示后序非递归遍历结果\n");

    int n;
    printf("请选择:"); scanf("%d", &n);
    return n;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    TreeNode* root;
    CreateTree(&root);
    int n;
    while (1)
    {
        n = choice();
        if (!(n >= 0 && n <= 3))
        {
            printf("菜单选择错误");
            continue;
        }
        if (n == 0)break;
        switch (n)
        {
        case 1:printf("前序遍历结果:");
            preorderTraversal(root); break;
        case 2: printf("中序遍历结果:");
            midorderTraversal(root);
            break;
        case 3:
            printf("\n后序遍历结果:");
            postorderTraversal(root);
            break;
        }
        putchar('\n');
        system("pause"); system("cls");
    }
}//运行结果ok 2019年5月26日15:36:55

以上代码的运行结果为：

• 通过比较我在图1中手动遍历的结果与程序运行之后的结果，可以看到我们的代码给出了正确的结果。

• 接下来我们再继续第二个小设计——二叉树的层序遍历，这部分内容比较简单，没什么好讲述的直接贴代码好了，代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;

typedef struct treeNode{
    char data;
    struct treeNode*rchild, *lchild;
}TreeNode;

void CreateTree(TreeNode** T)
{//前序递归创建二叉树
    char ch;
    scanf("%c", &ch);//读入字符
    if (ch == '#')//.代表空子树
        *T = NULL;
    else
    {
        *T = (TreeNode *)malloc(sizeof(TreeNode));
        if (!(*T))
        {
            printf("开辟内存失败\n");
            exit(1);
        }
        (*T)->data = ch;//给T赋值
        CreateTree(&(*T)->lchild);//给左子树赋值
        CreateTree(&(*T)->rchild);//给右子树赋值
    }
}

void levelorderTraversal(TreeNode*root)
{//二叉树从左至右，从上至下层次遍历
    int front, rear;
    TreeNode*que[10];
    front = rear = 0;
    TreeNode*q;
    if (root)
    {
        rear = (rear + 1) % 10;
        que[rear] = root;
        while (front != rear)
        {
            front = (front + 1) % 10;
            q = que[front];
            printf("%c ", q->data);
            if (q->lchild)
            {
                rear = (rear + 1) % 10;
                que[rear] = q->lchild;
            }
            if (q->rchild)
            {
                rear = (rear + 1) % 10;
                que[rear] = q->rchild;
            }
        }
    }
}


int main()
{
    freopen("data.txt", "r", stdin);
    TreeNode* root;
    CreateTree(&root);

    printf("层序遍历结果:");
    levelorderTraversal(root);

    putchar('\n');
}//运行结果ok2019年5月26日14:37:20

• 这是一个完整可以执行出结果的代码，不过我们重定义了标准输入为“data.txt”，因此运行这段代码之前你需要在程序所在的文件夹内创建名为“data.txt”的文件，并将”abd#h##k##cef##g##m##”写入该文件保存(字符串不含引号)，然后程序就可以直接从“data.txt”文本中读入二叉树的数据，并将按层序遍历的结果输出。演示结果为：

• 完成了第二个关于层序遍历的小任务，再让我们来看最后一个与排序二叉树有关的小任务。该任务比较简单，要求我们首先生成一颗二叉排序树，然后对其进行中序遍历，输出递增序列。由于中序遍历我们在任务一中已经完成了，因此只需要构建一个能生成二叉排序树的函数就可以了，这里我们采用递归的方式来实现，具体代码如下：

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

typedef struct treeNode{
    int data;
    struct treeNode*rchild, *lchild;
}TreeNode;

bool CreateTree(TreeNode** root, int data)
{//二叉排序树创建
    if ((*root) == NULL)    //如果为空，则创建一个节点
    {
        *root = (TreeNode *)malloc(sizeof(TreeNode));
        (*root)->data = data; ( *root)->lchild = (*root)->rchild = NULL;    //该节点为根节点，左孩子和右孩子指针均置空
        return true;
    }
    else if (data == (*root)->data) //如果存在，则返回false
        return false;
    else if (data < (*root)->data)  //如果被插入数据较小，则插入到左子树
        return CreateTree(&((*root)->lchild), data);
    else    //如果被插入数据较大，则插入到右子数
        return CreateTree(&((*root)->rchild), data);
}

void midorderTraversal(TreeNode* root)
{//中序非递归遍历二叉树
    
    TreeNode *stack[10]; int top = -1;
    TreeNode *p = root;
    while (p != NULL ||  top > -1)
    {
        while (p != NULL)
        {
            stack[++top] = p;
            p = p->lchild;
        }
        if (top > -1)
        {
            p = stack[top];
            printf("%d ", p->data);
            --top;
            p = p->rchild;
        }
    }

}



int main()
{
    
    TreeNode* root = NULL;
    int data;
    srand((unsigned)time(NULL));
    printf("依次保存在排序树中的值：");
    for (int i = 0; i < 10;)
    {//通过随机生成数字建立二叉排序树
        data = rand() % 20;
        
        if (CreateTree(&root, data))
        {
            printf("%d ", data);
            ++i;
        }
    }
    
    printf("\n中序遍历结果:");
    midorderTraversal(root);

    putchar('\n');
}//运行结果ok 2019年5月26日14:57:05

• 我们采用在main（）函数中随机生成0-19之间的数字的方式来构建二叉排序树，树中的结点一共有10个，并且要求结点之间没有重复的值。随机函数生成的值及排序结果输出如下图：

• 感想：本次课程设计比较简单，但是它一次性的总结了二叉树的创建、非递归先序、中序、后序及层序遍历，对掌握二叉树的遍历方法比较全面系统，因此有必要进行总结，方便下次使用的时候直接参考或者拷贝代码。最后该课程设计也涉及了少量的二叉排序树的知识，但是还不够全面，对二叉排序树的查找和结点删除等相对复杂的点没有过多涉及，以后还需要补充这方面的知识。