当前位置:   article > 正文

二叉树的四种基本遍历方式(C语言)_二叉树中序遍历c语言代码

二叉树中序遍历c语言代码

前言

Algorithms Data Structures = Programs
”数据结构 + 算法 = 程序“

by Niklaus Wirth

二叉树

注意:在阅读本文之前需要掌握栈和队列这两种基本的数据结构

二叉树是一种树形结构,其特点是每个节点至多只有两颗子树(即二叉树中不存在度大于2的节点),并且二叉树的子树有左右之分,其次序不能任意颠倒。

基本数据结构

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define dataType char
#define MAX_SIZE 50
#define Element BinaryTree *
#define endl() printf("\n")
typedef struct TreeNode
{
    /* data */
    dataType val;
    struct TreeNode *left;		//左子树
    struct TreeNode *right;		//右子树
} BinaryTree;
typedef struct Stack		//栈
{
    /* data */
    Element data[MAX_SIZE];
    int cursor;
} Stack;

typedef struct Queue		//队列
{
    /* data */
    Element data[MAX_SIZE];
    int rear;
    int front;
} Queue;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

基本数据结构算法

void visited(BinaryTree *tree);
Stack initStack();
Element pop(Stack *st);
void push(Stack *st, Element el);
bool IsEmpty(Stack st);
Element peek(Stack st);
Queue initQueue();
Element get(Queue *q);
void put(Queue *q, Element el);
bool IsEmptyQueue(Queue q);
bool IsOverflowQueue(Queue q);

void visited(BinaryTree *tree)
{
    printf("%c\t", tree->val);
}
Queue initQueue()
{
    Queue q;
    q.front = 0;
    q.rear = 0;
    return q;
}
bool IsEmptyQueue(Queue q)
{
    return q.rear == q.front;
}
bool IsOverflowQueue(Queue q)
{
    return q.front >= MAX_SIZE;
}
Element get(Queue *q)
{
    return (*q).data[(*q).rear++];
}
void put(Queue *q, Element el)
{
    (*q).data[(*q).front++] = el;
}
Stack initStack()
{
    Stack st;
    st.cursor = -1;
    return st;
}
Element pop(Stack *st)
{
    return (*st).data[(*st).cursor--];
}
void push(Stack *st, Element el)
{
    (*st).data[++(*st).cursor] = el;
}
bool IsEmpty(Stack st)
{
    return st.cursor == -1 ? true : false;
}
Element peek(Stack st)
{
    return st.data[st.cursor];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

建立一颗二叉树

递归建立二叉树

BinaryTree *create_binary_tree();
BinaryTree *create_binary_tree()
{
    dataType ch = getchar();
    if (ch != '#')
    {
        BinaryTree *tree = (BinaryTree *)malloc(sizeof(BinaryTree));
        tree->val = ch;
        tree->left = create_binary_tree();
        tree->right = create_binary_tree();
        return tree;
    }
    return NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

二叉树样例

ABD##E#H##CG#I##F##

二叉树样例

二叉树的四种基本遍历

  • 前序遍历

前序遍历(VLR), 是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

实现前序遍历之前,请读者先思考一下一个问题,怎么才算遍历完一个节点?

要进行前序遍历,就得从根节点(样例中的A节点)出发,遍历完其右结点,遍历其左节点,我们发现如果直接分析根节点是很复杂的,于是我们选择自低向上的分析法,先看D节点,由于D节点没有子节点,所以在访问完D节点之后,是不需要保存D节点的。

再看B节点,在访问完B节点之后,如果不将B节点保存,则无法访问到其后继节点,因此首先确定一点如果存在有后继节点的节点是需要先保存下来的,然后进入到其子节点,A节点同理。于是我们发现,越是后面保存的节点反而越先被访问完,因此我们选取一种能够实现后进先出得数据结构 — — , 这种数据结构作为保存节点的工具。

数据结构确定了,那我们应该采取何种算法呢?这就需要找到前序遍历的特点了,前面有底向上分析,得出数据结构,接下来就模拟遍历过程,找出规律或者是共同点。访问A,A是否有子节点,是,那就将A节点存入栈,然后往下走,此时问题又来了,往哪里走?往C走?显然不符合先序遍历,那么就只能往B走,走走走,边走边存,走到D,发现D点没有子节点,访问完之后可以不保存,那么接下来怎么办呢,我们发现B的的右节点E还没访问,那么怎么才能访问到E呢,我们惊喜的发现栈中存了B而且还是最后一个存入的,因此取出B,进入B的右子树E,发现E也有子节点,因此将E也存入栈,如此循环往复,直至栈为空,也就是遍历完成,分析至此,程序也不难写出,代码如下:

void preorder(BinaryTree *tree)
{
    Stack st = initStack();
    BinaryTree *temp = tree;
    while (!IsEmpty(st) || temp != NULL)
    {
        /* code */
        while (temp != NULL)
        {
            /* code */
            push(&st, temp);
            visited(temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
            temp = pop(&st);
            temp = temp->right;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

前序遍历: A B D E H C G I F

  • 中序遍历

中序遍历(LDR)是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。

把所有的节点投影到水平面就是中序遍历的顺序。
中序遍历与前序遍历的思路差不多,区别在于什么时候进行访问节点。

void inorder(BinaryTree *tree)
{
    Stack st = initStack();
    BinaryTree *temp = tree;
    while (!IsEmpty(st) || temp != NULL)
    {
        /* code */
        while (temp != NULL)
        {
            /* code */
            push(&st, temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
            temp = pop(&st);
            visited(temp);
            temp = temp->right;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

中序遍历: D B E H A G I C F

  • 后序遍历

后序遍历(LRD)是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。

后序遍历比较难,主要难点在于如何判断一个节点的左右节点是否都已访问。

void postorder(BinaryTree *tree)
{
    Stack st = initStack();
    BinaryTree *temp = tree;
    BinaryTree *record = NULL;
    while (!IsEmpty(st) || temp != NULL)
    {
        /* code */
        while (temp != NULL)
        {
            /* code */
            push(&st, temp);
            temp = temp->left;
        }
        if (!IsEmpty(st))
        {
            temp = peek(st);

            if (temp->right != NULL && temp->right != record)
            {
                temp = temp->right;
            }
            else
            {
                visited(temp);
                record = pop(&st);
                temp = NULL;
            }
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

后序遍历: D H E B I G F C A

  • 层次遍历

二叉树的层次遍历 ,顾名思义就是指从二叉树的第一层(根节点)开始,从上至下逐层遍历,在同一层中,则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中,按从顶层到底层的次序访问树中元素,在同一层中,从左到右进行访问。

void levelorder(BinaryTree *tree)
{
    Queue q = initQueue();
    BinaryTree *temp = tree;
    put(&q, temp);
    while (!IsEmptyQueue(q))
    {
        /* code */
        temp = get(&q);
        visited(temp);
        if (temp->left != NULL)
            put(&q, temp->left);
        if (temp->right != NULL)
            put(&q, temp->right);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

层次遍历: A B C D E G F H I

总结

在本文中仅给出前序遍历的详细思路,因为四种遍历方式大同小异。写程序之前先思考以何种数据结构存储数据,以何种算法操作数据,把思路理清楚,写起程序来事半功倍。方法是死的,思路是活的,数据结构与算法之路,基础与思考很重要,不要做一个只会ctrl+c、crtl+v 程序员,与君共勉!

"学而不思则罔,思而不学则殆"

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/716035
推荐阅读
相关标签
  

闽ICP备14008679号