2023年6月22日发(作者：)

C语⾔实现⼆叉树的遍历（数据结构）⼆叉树（binary tree）是指树中节点的度不⼤于2的有序树，它是⼀种最简单且最重要的树。⼆叉树的递归定义为：⼆叉树是⼀棵空树，或者是⼀棵由⼀个根节点和两棵互不相交的，分别称作根的左⼦树和右⼦树组成的⾮空树；左⼦树和右⼦树⼜同样都是⼆叉树⼆叉树的性质⼆叉树遍历⼆叉树有三种遍历⽅式，分别为先序遍历、中序遍历、后序遍历先序遍历：12345 （1）先访问根节点。 （2）再访问左⼦树。 （3）最后访问右⼦树。中序遍历：12345 （1）先访问左⼦树。 （2）再访问根节点。 （3）最后访问右⼦树。后序遍历：12345 （1）先访问左⼦树。 （2）再访问右⼦树。 （3）最后访问根节点。⽐如如下的⼆叉树先序遍历结果为 ABCDEFG中序遍历结果为 CBEDAFG后序遍历结果为 CEDBGFA⼆叉树结构123456typedef struct binarytreenode{ int data; struct binarytreenode *Lnode; struct binarytreenode *Rnode;} BiTNode,*BiTree;创建⼆叉树17void CreateBiTree(BiTree *T){ char ch; scanf("%c",&ch); if(ch == '#') { *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); if(!*T){return;} (*T)->data = ch; CreateBiTree(&(*T)->Lnode); CreateBiTree(&(*T)->Rnode); }}三种遍历829363738394041//⼆叉树的先序遍历void PreOrderTraverse(BiTree T){ if(T == NULL) return; printf("%c ",T->data); PreOrderTraverse(T->Lnode); PreOrderTraverse(T->Rnode);}//⼆叉树的中序遍历void InOrderTraverse(BiTree T){ if(T == NULL) return; InOrderTraverse(T->Lnode); printf("%c ",T->data); InOrderTraverse(T->Rnode);}//⼆叉树的后序遍历void PostOrderTraverse(BiTree T){ if(T == NULL) return; PostOrderTraverse(T->Lnode); PostOrderTraverse(T->Rnode); printf("%c ",T->data);}//⼆叉树的层次遍历void LevelOrderTraverse(BiTree T){ if(T == NULL) return; Q_Push(T); //取树的第⼀个节点加⼊队列 while(!Q_empty()){ //树不为空时 BiTree tmp = Q_Pop(T); //删除队列的第⼀个元素 printf("%c ",tmp->data); if(tmp->Lnode) Q_Push(tmp->Lnode); //取队列的左⼦树 if(tmp->Rnode) Q_Push(tmp->Rnode);//取队列的右⼦树 }}层次遍历82936373839464748495657585960616263/*

完整代码 */#include #include #include

#define MaxSize 100

struct tree { int data; struct tree* left; struct tree* right;};

typedef struct queue{ struct tree* numQ[MaxSize]; int front; int rear;}Queue;

Queue Q;

void initilize() { //初始化队列 = 0; = 0;}

void Push(struct tree* root) { //⼊队 [++] = root;}

struct tree* Pop() { //出队 return [++];}

int empty() { //判断对列是否为空 return == ;}

struct tree* creatTree (struct tree* root) { int value; scanf("%d", &value); if (value == -1) return NULL; root = (struct tree*)malloc(sizeof(struct tree)); root->data = value; printf("请输⼊%d的左⼦树：", root->data); root->left = creatTree(root->left); printf("请输⼊%d的右⼦树：", root->data); root->right = creatTree(root->right); return root;}

void LevelOrderTraversal (struct tree* root) { //⼆叉树的层次遍历 struct tree* temp; Push(root); while (!empty()) { temp = Pop(); printf("%d ", temp->data); //输出队⾸结点 if (temp->left) //把Pop掉的结点的左⼦结点加⼊队列 Push(temp->left); if (temp->right) 把Pop掉的结点的右⼦结点加⼊队列 Push(temp->right); }6364656667686976 }}

int main() { printf("请输⼊头节点："); struct tree* root = creatTree(root);

initilize(); //初始化队列

LevelOrderTraversal(root); putchar('n');

return 0;}完整代码8293637383946//#include #include #include #include #include #define MaxSize 100using namespace std;typedef struct binarytreenode{ int data; struct binarytreenode *Lnode; struct binarytreenode *Rnode;} BiTNode,*BiTree;typedef struct queue{ BiTree numQ[MaxSize]; int front; int rear;}Queue;Queue Q;void Q_initilize(){ = 0; = 0;}void Q_Push(BiTree root){ [++] = root;}BiTree Q_Pop(BiTree root){ return [++] ;}int Q_empty() { //判断对列是否为空 return == ;}void CreateBiTree(BiTree *T)4647484956575859666768697677787986878889969798991void CreateBiTree(BiTree *T){ char ch; scanf("%c",&ch); if(ch == '#') { *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); if(!*T){return;} (*T)->data = ch; CreateBiTree(&(*T)->Lnode); CreateBiTree(&(*T)->Rnode); }}//⼆叉树的先序遍历void PreOrderTraverse(BiTree T){ if(T == NULL) return; printf("%c ",T->data); PreOrderTraverse(T->Lnode); PreOrderTraverse(T->Rnode);}//⼆叉树的中序遍历void InOrderTraverse(BiTree T){ if(T == NULL) return; InOrderTraverse(T->Lnode); printf("%c ",T->data); InOrderTraverse(T->Rnode);}//⼆叉树的后序遍历void PostOrderTraverse(BiTree T){ if(T == NULL) return; PostOrderTraverse(T->Lnode); PostOrderTraverse(T->Rnode); printf("%c ",T->data);}//⼆叉树的层次遍历void LevelOrderTraverse(BiTree T){ if(T == NULL) return; Q_Push(T); while(!Q_empty()){ BiTree tmp = Q_Pop(T); printf("%c ",tmp->data); if(tmp->Lnode) Q_Push(tmp->Lnode); if(tmp->Rnode) Q_Push(tmp->Rnode); }}int main(){ BiTree T; CreateBiTree(&T); printf("前序遍历结果为 :n"); PreOrderTraverse(T); printf("nn中序遍历结果为 :n"); InOrderTraverse(T);48119120 InOrderTraverse(T); printf("nn后序遍历结果为 :n"); PostOrderTraverse(T); printf("nn层次遍历结果为 :nn"); LevelOrderTraverse(T); return 0;}补充：（1）建⽴⼆叉树时，这⾥是以前序遍历的⽅式，输⼊的是扩展⼆叉树，也就是要告诉计算机什么是叶结点，否则将⼀直递归，当输⼊“#”时，指针指向NULL，说明是叶结点。（2）输⼊的时候⼀定要注意因为有缓冲区的原因，⽤scanf输⼊的话，⼀定要把所有要输⼊的数据⼀次性输⼊，再回车（3）不要输⼊⼀个数据回车⼀次，这样就永远也⾛不出递归函数了，界⾯⼀直停留在输⼊界⾯，或者想⼀个⼀个输⼊⽤cin如图为扩展⼆叉树：（前序遍历为：ABC##DE###F#G##）