当前位置：首页 > news >正文

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

news 2025/5/12 13:39:49

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

在这里插入图片描述

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

🔚五、总结与考研建议

知识点	内容
存储结构	常用链式存储，结构清晰，动态性强
遍历方法	先序、中序、后序、层序，掌握递归与非递归实现
辅助结构	层序遍历需要队列，存储的是结点指针 `BiTree`
设计技巧	使用 `typedef ElemType` 抽象数据类型，增强复用性

完整代码《仅供参考》

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){//这里的结构体类型  LinkNodeQ.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;   //尾部入队  尾指针的指向ss->next =NULL;  //s的指向NULLQ.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 的方法去建立一棵树，通过辅助队列来实现的 层序遍历//abcdefwhile(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