欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【数据结构】-------二叉树的四种遍历方法(递归实现)

程序员文章站 2022-06-07 07:54:21
...

二叉树的数据结构主要是了解二叉树的链表结构,也就是一个数据域,两个指针域(指向左右孩子的指针) 对于二叉树来说,我们最常用的就是使用孩子表示法来表示一个树。使用根节点指针来表示一棵树,利用空指针来表示空树。

今天我们就来看看二叉树的四种遍历的方法:

先序遍历,中序遍历,后序遍历,层序遍历四种方法,我们知道的是,层序是其中最难的一种方法,今天我就在这里着重的说下。

层序遍历的方法

我们的思路是先让根结点进行入队列,然后将根节点进行入队列,然后打印根结点,出队列根结点,然后入队列根结点的左右子树,取队首元素,打印队首元素,出队列b,入队列b的左右子树,再取队首元素c,打印队首元素c,然后入队列c的左右子树,依次进行循环,当我们取到最后一个元素g的时候,我们发现我们队列为空,取队首元素为0的时候,就说明我们已经执行完毕了,这时候我们就进行层序完毕,得到最终的结果。
【数据结构】-------二叉树的四种遍历方法(递归实现)
二叉树涉及到的四种遍历方式的代码就如下:


//树的数据结构
typedef char TreeNodeType;
typedef struct TreeNode{
    struct TreeNode* lchild;
    struct TreeNode* rchild;
    TreeNodeType data;
}TreeNode;

#define MAXSIZE  100
typedef TreeNode* SeqQType;
typedef struct SeqQ{
    SeqQType data[MAXSIZE];//定义了一个长度为100的队列
    size_t size;//记录当前顺序表的大小
    size_t head;
    size_t tail;
}SeqQ;

//树的初始化
void TreeInit(TreeNode** root)
{
    if (root == NULL)
    {
        return;
    }
    *root = NULL;
}
//前序的遍历方法
void PreOrder(TreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    //先访问根节点
    printf("%c ", root->data);
    //再访问左子树
    PreOrder(root->lchild);
    //访问右子树
    PreOrder(root->rchild);
}

//中序的遍历方法
void InOrder(TreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    //访问左子树
    InOrder(root->lchild);
    //访问根节点
    printf("%c ", root->data);
    //访问右子树
    InOrder(root->rchild);
}
//后序的遍历方法
void PostOrder(TreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    //先访问左子树
    PostOrder(root->lchild);
    //访问右子树
    PostOrder(root->rchild);
    //访问根结点
    printf("%c ", root->data);
}


void SeqQInit(SeqQ* sq){
    if (sq == NULL){
        return;
    }
    sq->size = 0;
    sq->head = 0;
    sq->tail = 0;
}

void SeqQResize(SeqQ* sq){
    if (sq == NULL){
        return;
    }
    if (sq->size <= MAXSIZE){
        return;
    }
    int size = MAXSIZE * 2 + 1;
    SeqQType* new = (SeqQType*)malloc(sizeof(SeqQType));
    int i = 0;
    for (; i<sq->size; i++){
        new[i] = sq->data[i];
    }
    free(sq->data);
}


void SeqQPush(SeqQ* sq, SeqQType  value){
    if (sq == NULL)

    {
        return;
    }
    if (sq->size >= MAXSIZE){
        SeqQResize(sq);
        return;
    }

    sq->data[sq->tail++] = value;
    if (
        sq->tail == MAXSIZE){
        sq->tail = 0;
    }
    ++sq->size;
}

void SeqQPop(SeqQ* sq){
    if (sq == NULL){
        return;
    }
    if (sq->size == 0){
        return;
    }
    ++sq->head;
    if (sq->head >= MAXSIZE){
        sq->head = 0;
    }
    --sq->size;
}
TreeNodeType SeqQFront(SeqQ* sq, SeqQType* value){
    if (sq == NULL || value == NULL){
        return 0;
    }
    if (sq->size == 0){
        return 0;
    }
    *value = sq->data[(sq->head)];//注意在这里考虑优先级的问题
    return *value;
}
//层序的遍历方法
void LevelOrder(TreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    SeqQ sq;
    SeqQInit(&sq);
    SeqQType front = root;
    SeqQPush(&sq, root);
    //将队首元素进行入队列
    while (1)
    {
        int ret ;
        ret = SeqQFront(&sq, &front);
        //返回值为空时,说明树已经访问完了,循环结束
        if (ret == -1)
        {
            break;
        }
        //访问队首元素
        printf("%c ", front->data);
        SeqQPop(&sq);
        //入队列左右子树
        if (front->lchild != NULL)
        {
            SeqQPush(&sq, front->lchild);
        }
        if (front->rchild != NULL)
        {
            SeqQPush(&sq, front->rchild);
        }
    }
    printf("\n");
}

TreeNode*  TreeNodeCreate(TreeNodeType value)//创建树结点
{
    TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
    newnode->data = value;
    newnode->lchild = NULL;
    newnode->rchild = NULL;
    return newnode;
}



TreeNode* TreeCreate(TreeNodeType array[], size_t size, int *index, TreeNodeType null_node)
//根据先序遍历的结构,带有空结点的进行标记,构造成一棵树,array[] 先序遍历的结果 
//size 数组中元素个数,null_node 数组中空节点的特殊标记
{
    if (index == NULL)
    {
        return NULL;
    }
    //index表示当前取数组中的哪一个元素

    //index不在有效的范围内
    if (*index >= size){
        return NULL;
    }
    //如果该节点为空节点
    if (array[*index] == null_node)
    {
        return NULL;
    }
    //创建根结点
    TreeNode* newnode = TreeNodeCreate(array[*index]);
    //创建左子树
    ++(*index);
    newnode->lchild = TreeCreate(array, size, index, null_node);
    //创建右子树
    ++(*index);
    newnode->rchild = TreeCreate(array, size, index, null_node);
    return newnode;
}