本文共 2868 字，大约阅读时间需要 9 分钟。

一个简单的二叉树构建与遍历实例

本节将介绍一个用于二叉树构建与遍历操作的C语言程序。程序主要包括以下几个部分：二叉树的前序遍历、级序遍历和后序遍历的实现。通过代码分析，我们可以了解如何利用队列这一数据结构来实现级序遍历，并学习如何通过递归和非递归方式遍历二叉树。

二叉树的前序遍历

前序遍历（Pre-order Traversal）是遍历二叉树的常见方式之一。其特点是先访问根节点，然后依次访问左子节点和右子节点。以下是实现前序遍历的代码片段：

void pre(node *root) {    if (root == NULL) {        return;    }    printf("%d ", root->data);    pre(root->lchild);    pre(root->rchild);}

通过这个函数，我们可以看到：

二叉树的级序遍历

级序遍历（Level Order Traversal）又被称为广度优先搜索（Breadth-First Search，BFS），其特点是按层依次访问所有节点。实现级序遍历的代码如下：

node *level_in() {    int index = 0;    queue
   
     q;    node *root = new node;    root->data = level[index];    root->lchild = NULL;    root->rchild = NULL;    index++;    q.push(root);        node *temp;    int i;    while (!q.empty()) {        temp = q.front();        q.pop();                for (i = 0; i < N; i++) {            if (temp->data == in[i]) {                flag[i] = true;                break;            }        }                if (flag[i - 1] == false && i > 0) {            node *t = new node;            t->data = level[index];            t->lchild = NULL;            t->rchild = NULL;            temp->lchild = t;            index++;            q.push(t);        }                if (flag[i + 1] == false && i < N - 1) {            node *t = new node;            t->data = level[index];            t->lchild = NULL;            t->rchild = NULL;            temp->rchild = t;            index++;            q.push(t);        }    }    return root;}
   

通过这个函数，我们可以看到：

二叉树的后序遍历

后序遍历（Post-order Traversal）是指先访问左子节点和右子节点后再访问根节点。其实现方式通常需要使用栈，而不是队列。以下是实现后序遍历的代码片段：

node *post_in(int postL, int postR, int inL, int inR) {    if (postL > postR) {        return NULL;    }    node *root = new node;    root->data = post[postR];    int k;    for (k = 0; in[k] != post[postR]; k++) {    }    int num_of_right = inR - k;    root->lchild = post_in(postL, postR - 1 - num_of_right, inL, k - 1);    root->rchild = post_in(postR - num_of_right, postR - 1, k + 1, inR);    return root;}

通过这个函数，我们可以看到：

主函数的运行流程

主函数main的实现流程如下：

int main() {    node *root;    scanf("%d", &N);    for (int i = 0; i < N; i++) {        scanf("%d", &level[i]);    }    for (int i = 0; i < N; i++) {        scanf("%d", &post[i]);    }    for (int i = 0; i < N; i++) {        scanf("%d", &in[i]);    }        // 根据需要选择构建二叉树的方式    // root = level_in();    // root = pre_in(0, N - 1, 0, N - 1);    // root = post_in(0, N - 1, 0, N - 1);        pre(root);    return 0;}

功能总结

通过上述代码，我们可以实现二叉树的构建与遍历。程序支持三种遍历方式：

程序的核心逻辑包括：

• 二叉树的构建
• 递归算法的应用
• 队列和栈的使用
• 输入数据的处理

如果需要，可以根据具体需求选择构建二叉树的方式：level_in、pre_in或post_in。程序的输出可以根据需求进行扩展或修改。