二叉树深度优先遍历的非递归与递归实现,以及广度优先遍历的实现

0 人赞了该文章

实现截图:

代码为:

// 层次遍历二叉树.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>
#include "malloc.h"
#define MaxSize 100
typedef struct BTNode
{
    char data;
    struct BTNode *lchild;
    struct BTNode *Rchild;
}BTNode,*BtNode;

BtNode t;
//先序创建二叉树
void InitBTree(BtNode &T)
{
    printf("请输入字符:");
    char ch = getchar();
    if (ch != '#')
    {
        T = (BtNode)malloc(sizeof(BTNode));
        T->data = ch;
        //ch = getchar();
        InitBTree(T->lchild);
        InitBTree(T->Rchild);
    }
    else
    {
        //ch = getchar();
        T = NULL;
    }
}
/***********************递归遍历*****************************/
//先序
void preTravel(BtNode T)
{
    if (T!=NULL)
    {
        printf("a:%c",T->data);
        preTravel(T->lchild);
        printf("b:%c", T->data);
        preTravel(T->Rchild);
        printf("c:%c", T->data);
    }
    else
    {
        printf("[虚]");
    }
}
//层次遍历
void LevelTravel(BtNode T)
{
    BtNode  Queue[MaxSize];
    int front, rear;
    front = rear = 0;
    BtNode t;
    if (T != NULL)
    {
        rear = (rear + 1) % MaxSize;
        Queue[rear] = T;
        while (front != rear)
        {
            front = (front + 1) % MaxSize;
            t = Queue[front];
            printf("%c",t->data);
            if (t->lchild)
            {
                rear = (rear + 1) % MaxSize;
                Queue[rear] = t->lchild;
            }
            if (t->Rchild)
            {
                rear = (rear + 1) % MaxSize;
                Queue[rear] = t->Rchild;
            }
        }

    }
}
/**********************************************************/
/****************非递归二叉树遍历*****************/
//先序栈遍历
void preNoRecursion(BtNode T)
{
    BtNode   Stack[MaxSize];
    int top = -1;
    BtNode t;
    if (T != NULL)
    {
        Stack[++top] = T;
        while (top != -1)
        {
            t = Stack[top];
            //当栈不为空栈时
            printf("%c",t->data);
            top--;
            if (t->Rchild)
            {
                Stack[++top] = t->Rchild;
            }
            if (t->lchild)
            {
                Stack[++top] = t->lchild;
            }
        }
    }
}
//中序非递归
void inNonRecursion(BtNode T)
{
    BtNode Stack[MaxSize];
    int top = -1;
    BtNode t;
    if (T != NULL)
    {
        t = T;
        while (top!=-1||t!=NULL)
        {

            while (t)
            {
                Stack[++top] = t;
                t = t->lchild;
            }
            if (top!=-1)
            {
                t = Stack[top--];
                printf("%c",t->data);
                t = t->Rchild;
            }
        }
    }

}
//后序栈遍历
void  postNonRecursion(BtNode T)
{
    BtNode Stack1[MaxSize], Stack2[MaxSize];
    int top1 = -1, top2 = -1;
    BtNode t;
    if (T)
    {
        Stack1[++top1] = T;
        while (top1!=-1)
        {
            t = Stack1[top1--];
            Stack2[++top2] = t;
            if (t->lchild)
            {
                Stack1[++top1] = t->lchild;
            }
            if (t->Rchild)
            {
                Stack1[++top1] = t->Rchild;
            }

        }

        while (top2!=-1)
        {
            printf("%c",Stack2[top2--]->data);
        }
    }
}
/***********************************************/

int main()
{
    BtNode T;
    printf("******开始*******\r\n");
    InitBTree(T);
    printf("********存储完成*********\r\n");
    printf("先序\r\n");
    preTravel(T);
    printf("\r\n");
    printf("层次\r\n");
    LevelTravel(T);
    printf("\r\n");
    printf("先序栈\r\n");
    preNoRecursion(T);
    printf("\r\n");
    printf("中序栈\r\n");
    inNonRecursion(T);
    printf("\r\n");
    printf("后序栈\r\n");
    postNonRecursion(T);
}

评论

暂无评论