美文网首页
课程设计——非递归实现二叉树的三种遍历算法及创建排序二叉树

课程设计——非递归实现二叉树的三种遍历算法及创建排序二叉树

作者: LetUsGoOn | 来源:发表于2019-05-26 19:24 被阅读0次

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

1.二叉树的建立及其非递归的先序、中序、后序遍历;
2.二叉树的层序遍历
3.排序二叉树的创建及中序遍历输出

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

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

图1 示例二叉树

在前序遍历生成二叉树中,我们用‘#’表示结点为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

以上代码的运行结果为:


图2 前序遍历 图3 中序遍历 图4 后续遍历

通过比较我在图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”文本中读入二叉树的数据,并将按层序遍历的结果输出。演示结果为:


图5 层序遍历结果
  • 完成了第二个关于层序遍历的小任务,再让我们来看最后一个与排序二叉树有关的小任务。
    该任务比较简单,要求我们首先生成一颗二叉排序树,然后对其进行中序遍历,输出递增序列。由于中序遍历我们在任务一中已经完成了,因此只需要构建一个能生成二叉排序树的函数就可以了,这里我们采用递归的方式来实现,具体代码如下:
#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个,并且要求结点之间没有重复的值。随机函数生成的值及排序结果输出如下图: 图6 二叉排序树演示结果
  • 感想:本次课程设计比较简单,但是它一次性的总结了二叉树的创建、非递归先序、中序、后序及层序遍历,对掌握二叉树的遍历方法比较全面系统,因此有必要进行总结,方便下次使用的时候直接参考或者拷贝代码。最后该课程设计也涉及了少量的二叉排序树的知识,但是还不够全面,对二叉排序树的查找和结点删除等相对复杂的点没有过多涉及,以后还需要补充这方面的知识。

相关文章

  • 面试题

    面试题 二叉树 非递归实现二叉树遍历 节点: 前序遍历 中序遍历 后序遍历 排序 快速排序 其他问题 算法题 给一...

  • 算法之二叉树

    二叉树之C++实现 创建二叉树 复制二叉树 先序遍历 递归实现 非递归实现 中序遍历 递归实现 非递归实现 后序遍...

  • 二叉树的三种深度优先遍历算法与思路

    看了一些关于二叉树遍历算法的文章,例如:二叉树三种遍历方式的递归和循环实现二叉树的递归与非递归遍历(前序、中序、后...

  • 二叉树遍历-JAVA实现

    基础二叉树 二叉树遍历分为前序、中序、后序递归和非递归遍历、还有层序遍历。 前序递归遍历算法:访问根结点-->递归...

  • 二叉树的遍历实现递归与非递归

    本文实现了二叉树的深度遍历算法,分为递归与非递归 递归的实现非常简单,基本上没啥难度 非递归的实现需要根据遍历的顺...

  • 二叉树

    来源 二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现 二叉树的实现及先序、...

  • 二叉树

    二叉树实现 本程序实现二叉树的构造以及三种遍历的递归与非递归算法、求叶子数和节点数,以及判断一个节点是否是叶子等操...

  • 总结

    1、二叉树广度遍历(非递归) 广度遍历非递归实现需要依靠一个队列。 2、二叉树深度遍历(递归与非递归,前序,中序和...

  • Java二叉树的遍历

    Java二叉树的遍历 利用递归和非递归实现二叉树的先序,中序,后序遍历以及使用队列实现二叉树的层次遍历

  • 二叉树的遍历 递归 非递归 Java

    二叉树的常用遍历算法实现 前序遍历 递归实现 非递归实现(1)这个是常规思路,先遍历到根节点,并打印、压栈,然后遍...

网友评论

      本文标题:课程设计——非递归实现二叉树的三种遍历算法及创建排序二叉树

      本文链接:https://www.haomeiwen.com/subject/upeftctx.html