二叉树,是一种链式数据结构。二叉树遍历是用于查找树节点的算法。

二叉树遍历结构.jpg

遍历命名描述
NLR前序遍历
LNR中序遍历
LRN后序遍历

前序:访问根结点的操作发生在遍历其左右子树之前。
中序:访问根结点的操作发生在遍历其左右子树之间
后序:访问根结点的操作发生在遍历其左右子树之后。

代码实例

设节点数据 n1 = 1666 n2 = 9222 n3 = 7333 n4 = 4888 在C语言中简单的二叉树实现前序、中序、后续遍历。

二叉树.jpg

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

typedef struct node
{
    //数据
    int data;
    //左节点
    struct node *left;
    //右节点
    struct node *right;
} Node;

//先序遍历
void preorder(Node *node)
{
    if (node != NULL)
    {
        printf("%d \n", node->data);
        preorder(node->left);
        preorder(node->right);
    }
}

//中序遍历
void inorder(Node *node)
{
    if (node != NULL)
    {
        inorder(node->left);
        printf("%d \n", node->data);
        inorder(node->right);
    }
}
//后序遍历
void postorder(Node *node)
{
    if (node != NULL)
    {
        postorder(node->left);
        postorder(node->right);
        printf("%d \n", node->data);
    }
}
int main()
{
    Node n1, n2, n3, n4;

    n1.data = 1666;
    n2.data = 9222;
    n3.data = 7333;
    n4.data = 4888;

    n1.left = &n2;
    n1.right = &n3;

    n2.left = &n4;
    n2.right = NULL;

    n3.left = NULL;
    n3.right = NULL;

    n4.left = NULL;
    n4.right = NULL;

    printf("先序遍历:\n");
    preorder(&n1);

    printf("中序遍历:\n");
    inorder(&n1);

    printf("后序遍历:\n");
    postorder(&n1);
    return 0;
}

运行结果

先序遍历:
1666     
9222     
4888     
7333     
中序遍历:
4888     
9222     
1666     
7333     
后序遍历:
4888
9222
7333 
1666