数据结构【二叉树的遍历实现】

📘考研数据结构基础：二叉树的存储、遍历与队列辅助实现详

在数据结构的学习中，二叉树作为一种结构清晰、应用广泛的树形结构，是考研计算机专业课中重点内容之一。本文将以实际代码为基础，介绍二叉树的存储结构、遍历方式，以及在遍历过程中为何要使用队列结构，并解答一个常见疑问：“为什么不能用 char 类型直接代替队列的元素类型”。

🧩一、二叉树的存储方式：链式存储结构

在实际开发或算法设计中，二叉树常采用链式存储结构。其基本定义如下：

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

• 每个结点由一个字符 data 表示数据域。
• lchild 和 rchild 分别指向该结点的左、右子树。
• BiTree 是指向 BiTNode 的指针，代表一个树的根结点。

🧪二、二叉树的遍历方式

✅ 1. 先序遍历（PreOrder）

void PreOrder(BiTree T) {
    if (T) {
        cout << T->data;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

先访问根结点，再递归遍历左子树和右子树。

✅ 2. 中序遍历（InOrder）

void InOrder(BiTree T) {
    if (T) {
        InOrder(T->lchild);
        cout << T->data;
        InOrder(T->rchild);
    }
}

先访问左子树，再访问根结点，最后遍历右子树。

✅ 3. 后序遍历（PostOrder）

void PostOrder(BiTree T) {
    if (T) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout << T->data;
    }
}

先遍历左右子树，最后访问根结点。

✅ 4. 层序遍历（LevelOrder）

层序遍历不同于上面三种递归遍历，它需要用辅助队列实现。

void LevelOrder(BiTree T) {
    LinkQueue Q;
    InitQ(Q);
    EntQ(Q, T);
    while (!EmptyQ(Q)) {
        BiTree p;
        DelQ(Q, p);
        cout << p->data;
        if (p->lchild)
            EntQ(Q, p->lchild);
        if (p->rchild)
            EntQ(Q, p->rchild);
    }
}

🚩三、辅助队列结构及其核心设计

为了支持层序遍历的广度优先访问，我们需要一个队列，队列中存放的是树结点的指针而非字符：

typedef BiTree ElemType;  // 关键设计：定义队列的元素类型为 BiTree（即指向树结点的指针）

队列的基本操作如下：

bool EntQ(LinkQueue &Q, ElemType x);    // 入队
bool DelQ(LinkQueue &Q, ElemType &x);   // 出队

❓为什么不能直接将 ElemType 改为 char？

这是许多初学者常见的疑惑。解释如下：

• char 仅能存储字符，比如 'A'，却无法提供关于该字符结点的结构信息。

• 层序遍历时，我们需要访问一个结点的左右孩子：

  if (p->lchild) EntQ(Q, p->lchild);
  

  这里 p 是一个指向结构体的指针，如果你仅保存了 char，根本无法访问 p->lchild。

✅ 所以，队列中必须保存的是 BiTree 类型的指针，从而能继续递归或迭代处理其子树。

🧵四、二叉树的构建

构建过程通常采用先序递归建树法，使用 '#' 表示空结点：

void CreateTree(BiTree &T) {
    char ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else {
        T = new BiTNode;
        T->data = ch;
        CreateTree(T->lchild);
        CreateTree(T->rchild);
    }
}

输入示例（先序）：

AB#D##C##

表示结构如下的树：

    A
   / \
  B   C
   \
    D

🔚五、总结与考研建议

完整代码《仅供参考》

function.h

 //层次建树   借助一个辅助队列
    //          a
    //        b   c
    //    d   e   f   g

    #ifndef LEVELIRDER3_FUNCTION_H
    #define LEVELIRDER3_FUNCTION_H
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <ostream>
    
    using namespace std;
    
    
    //树的结构体定义
    typedef struct BiTNode{
        char data;
        struct BiTNode *lchild,*rchild;
    }BiTNode , * BiTree;
    
    
    //队列的结构体的声明
    typedef BiTree ElemType;
    typedef struct LinkNode{
        ElemType datac;
    //在进行入队的时候 这里使用的是 int 类型的的数据 然而树存储的是一个char  类型的
    这时候就体现出的了 typedef 的作用了 不用频繁的修改数据
        struct LinkNode * next;
    }LinkNode;
    
    typedef struct {  //声明一个结构体类型的指针
        LinkNode * front, * rear;
    }LinkQueue;
    
    void InitQ(LinkQueue &Q);
    bool EmptyQ(LinkQueue Q);
    //这里出入队列 实际上是对 树 的结点进行 的一个操作 所以应该使用 树的 结构体类型
    bool EntQ(LinkQueue &Q,ElemType x);
    bool DelQ(LinkQueue &Q, ElemType &x);
    
    // 建立一个辅助队列 tag  进行层序建树
    typedef struct tag{
        //    BiTree p;  //树的某一结点的地址值
        BiTNode *p;
        struct tag *pnext;
    
    }tag_t , *ptag_t;
    
    #endif //LEVELIRDER3_FUNCTION_H
    
    

queue.cpp

   //
    // Created by Yhame on 2025/5/11.
    //
    
    #include "function.h"
    
    //初始化
    void InitQ(LinkQueue &Q){
        //这里的结构体类型  LinkNode
        Q.front = Q.rear =(LinkNode*) malloc(sizeof(LinkNode));
        Q.front->next =NULL; //队头指向NULL
    
    }
    //判空 这里可以不用判断队列是否会满
    
    bool EmptyQ(LinkQueue Q){
        if(Q.front == Q.rear)return true;
    //    Q.front->next =NULL;
    //    return true;
    }
    
    //入队
    bool EntQ(LinkQueue &Q,ElemType x){
        //插入
        LinkNode *s =(LinkNode*)malloc(sizeof(LinkNode)); //申请新的结点 插入队尾
        if(!s)return false;
    
        s->datac =x;   //尾巴插入
        Q.rear->next =s;   //尾部入队  尾指针的指向s
        s->next =NULL;  //s的指向NULL
        Q.rear =s;  //更新尾指针
        return true;
    }
    //出队
    bool DelQ(LinkQueue &Q,ElemType &x){ //判空 从头开始删除
        if(Q.front ==Q.rear){
            return false;
        }
        LinkNode *q ;
    
        x = Q.front->next->datac; //返回要删除的数据
        q = Q.front->next;  //q指向第一个数据结点  队头出
        Q.front->next =q ->next;  //断开q 使front 指向后一个元素
    
        if(Q.rear==q){
            Q.rear = Q.front; // rear也回到front（空队列状态）
        }
        free(q);//如果q 为最后一个结点  使front 和rear 相等
    
        return true;
    
    }

main.cpp

     #include <iostream>
    #include "function.h"
    
    //前序遍历
    void PreOrder(BiTree p){
    
        if(p!=NULL){
    
            printf("%c",p->data);
            PreOrder(p->lchild);
            PreOrder(p->rchild);
        }
    
    
    }
    
    //中序遍历
    void InOrder(BiTree p){
    
        if(p!=NULL){
    
            InOrder(p->lchild);
            printf("%c",p->data);
            InOrder(p->rchild);
        }
    
    }
    
    //后序遍历
    void PostOrder(BiTree p){
    
        if(p!=NULL){
    
            PostOrder(p->lchild);
    
            PostOrder(p->rchild);
    
            printf("%c",p->data);
        }
    }
    
    //层次遍历
    void LevelOrder(BiTree T){
        LinkQueue Q; //声明一个 辅助队列
        InitQ(Q);
        BiTree p;  //记录树的当前结点
    //    BiTNode * p;
    
        EmptyQ(Q);
        EntQ(Q,T);  //树根入队
        当队列不为空进行 队头出队打印   之后判断 该点的 左右孩子是否为空  进行出入队操作
        puts("层序");
        while(!EmptyQ(Q)){
            DelQ(Q,p); //出队当前结点 并打印
            putchar(p->data);  //printf("%c,c);
            if(p->lchild!=NULL){
                EntQ(Q,p->lchild);
            }
            if(p->rchild!=NULL){
                EntQ(Q,p->rchild);
            }
        }
    
    }
    
    int main() {
        BiTree pnew; //用来指向新申请的数结点
        BiTree tree =NULL; //tree 是指向树根的，代表树
    
        ptag_t phead= NULL,ptail =NULL, listpnew =NULL, pre =NULL; //初始化队列 定义一个pre 指向执行的当前元素
    
        char c;
    
    
        这里使用的是 tag 的方法去建立一棵树，通过辅助队列来实现的 层序遍历
        //abcdef
        while(scanf("%c",&c)){
    
            if(c=='\n'){
                break;
            }
            //calloc申请空间  大小是两个参数相乘，并对空间进行初始化  赋值为0;
            //malloc 申请以后还需要对其进行赋值 malloc 返回的是 void * 类型的 也需要进行强制转换
    
            树申请结点
            pnew =(BiTree) calloc(1,sizeof(BiTNode));
            pnew->data = c;
    
    
            //队列结点申请空间
           listpnew = (ptag_t) calloc(1,sizeof(tag_t));  //申请一个结构体类型的结点 返回一个指针类型的
    
           listpnew->p =pnew;
    
            //如果是数的第一个结点
            if(tree==NULL){
                tree = pnew;  //tree 指向根的头结点
                //第一个结点 即是队列头也是 队列尾
                phead = ptail = listpnew;
                pre = listpnew; //  用来判断当前结点 的左右孩子是否满了
    
            }else {
                //元素直接入队
                ptail ->pnext = listpnew;
                ptail =listpnew;
                //接下来把元素放入树中
                if(pre->p->lchild ==NULL){
                    pre ->p ->lchild =pnew;  // pre -> p 左孩子为空 就放入左孩子
    
                }else if(pre->p->rchild==NULL){
                    pre->p->rchild =pnew;
                    pre = pre->pnext;  // !!! 左右孩子都满了，指向下一个节点
                }
    
    
            }
    
        }
        puts("前序");
        PreOrder(tree);
        printf("\n");
    
        puts("中序");
        InOrder(tree);
        printf("\n");
    
        puts("后序");
        PostOrder(tree);
        printf("\n");
    
        LevelOrder(tree);
        return 0;
        //这没有对树进行相应的输出  ，使用调试发现建树完成
    }
    
    //abcdefg
    //        前序
    //abdecfg
    //        中序
    //dbeafcg
    //        后序
    //debfgca
    //        层序
    //abcdefg
    

这个代码实现了通过层次输入字符数据来构建一棵二叉树，并对这棵二叉树进行前序、中序、后序、层序遍历，完整地展示了树的构建与遍历过程。

✅ 具体功能如下：

1. 层次建树（用辅助队列实现）

• 利用自定义的tag_t 辅助队列结构体进行层次建树。
• 每次输入一个字符就创建一个二叉树结点。
• 如果当前树为空（即首次输入），设置为根节点；
• 后续的结点依次作为上一结点的左孩子、右孩子插入；
• 每插入完一个结点，就将其作为队列中的一个元素排队，继续等待为它的孩子分配子节点。

📘写在最后

学习数据结构尤其是二叉树，最重要的是掌握“结构 + 操作”的关系。每一次遍历、每一次入队出队，背后都是指针、结构体、递归这些基础能力的体现。希望本文结合实际代码的讲解能为你的学习提供实用帮助。