王道c语言-二叉树前序、中序、后序、层次遍历

main.cpp

#include "function.h"//abdhiejcfg 前序遍历=深度优先遍历 abdhiejcfg
void PreOrder(BiTree p) {if (p != NULL) {printf("%c ", p->c);//等价于putchar(p->c);等价于visit函数伪代码PreOrder(p->lchild);PreOrder(p->rchild);}
}//中序遍历 hdibjeafcg
void InOrder(BiTree p) {if (p != NULL) {InOrder(p->lchild);printf("%c ", p->c);//等价于putchar(p->c);等价于visit函数伪代码InOrder(p->rchild);}
}//后序遍历 hidjebfgca
void PostOrder(BiTree p) {if (p != NULL) {PostOrder(p->lchild);PostOrder(p->rchild);printf("%c ", p->c);//等价于putchar(p->c);等价于visit函数伪代码}
}// 层次遍历=层序遍历=广度优先遍历,遍历结果 abcdefghij
void LevelOrder(BiTree T){LinkQueue Q; //辅助队列InitQueue(Q);BiTree p;EnQueue(Q,T);while (!IsEmpty(Q)){DeQueue(Q,p);putchar(p->c);//等价于 printf("%c ",p->c)if(p->lchild){EnQueue(Q,p->lchild);}if(p->rchild){EnQueue(Q,p->rchild);}}
}int main() {BiTree pnew; //指向新申请的树结点BiTree tree = NULL; //要记得初始化为NULLptag_t phead = NULL, ptail = NULL, listpnew = NULL, pcur = NULL;char c;//BiElemType c;int i = 0;while (scanf("%c", &c)) { //循环输入 abcdefgif (c == '\n') {break; //读到换行结束}//calloc申请的空间大小为 两参数的积，并将内存初始化为0pnew = (BiTree) calloc(1, sizeof(BiNode));pnew->c = c;listpnew = (ptag_t) calloc(1, sizeof(tag_t));listpnew->p = pnew;//如果是树的第一个结点if (tree == NULL) {tree = pnew; //tree指向根结点phead = listpnew; // 初始化队列，队头ptail = listpnew; //队尾pcur = listpnew; //要插入的结点的父结点} else {ptail->pnext = listpnew;ptail = ptail->pnext; //ptail = listpnew;if (pcur->p->lchild == NULL) {pcur->p->lchild = pnew;} else if (pcur->p->rchild == NULL) {pcur->p->rchild = pnew;pcur = pcur->pnext;}}}printf("------------PreOrder------------------\n");PreOrder(tree);printf("\n------------InOrder------------------\n");InOrder(tree);printf("\n------------PostOrder------------------\n");PostOrder(tree);printf("\n------------LevelOrder------------------\n");LevelOrder(tree);return 0;
}

queue.cpp

#include "function.h"void InitQueue(LinkQueue &Q) {Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));Q.front->next = NULL;
}bool IsEmpty(LinkQueue Q) {return Q.front==Q.rear;
}void EnQueue(LinkQueue &Q, ElemType x) {LinkNode *pnew = (LinkNode *) malloc(sizeof(LinkNode));pnew->data = x;pnew->next = NULL;Q.rear->next = pnew;Q.rear = Q.rear->next;
//    Q.rear = pnew;
}
bool DeQueue(LinkQueue &Q, ElemType &x) {if (Q.rear == Q.front) return false;LinkNode *q = Q.front->next;Q.front->next = q->next;x = q->data;if (Q.rear == q) {Q.rear = Q.front;}free(q);return true;
}

function.h

//
// Created by ccc on 2024/3/22.
//#ifndef UNTITLED_FUNCTION_H
#define UNTITLED_FUNCTION_H#endif //UNTITLED_FUNCTION_H#include <stdio.h>
#include <stdlib.h>typedef char BiElemType;
typedef struct BiNode {BiElemType c;struct BiNode *lchild;struct BiNode *rchild;
} BiNode, *BiTree;//辅助队列
typedef struct tag {BiTree p;//注意是指针struct tag *pnext;
} tag_t, *ptag_t;//队列相关的数据结构
typedef BiTree ElemType;  //注意
typedef struct LinkNode {ElemType data;struct LinkNode *next;
} LinkNode;typedef struct {LinkNode *front, *rear;
} LinkQueue;void InitQueue(LinkQueue &Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkQueue &Q, ElemType x);
bool DeQueue(LinkQueue &Q, ElemType &x);