一、二叉树层次建树及遍历（先序中序后序及层序遍历）
/
// Created by 斋心 on 2023/5/22.
//
#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H
#include<stdio.h>
#include<stdlib.h>
typedef char BiElemType;
//二叉树结构体类型申明
typedef struct BiTNode{
BiElemType c;//结点数据
struct BiTNode *lchild;//结点左孩子指针
struct BiTNode *rchild;//结点右孩子指针
}BiTNode,*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; //先进先出，从队尾入队，队头出队
//申明要在main.cpp中使用的queue函数
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q,ElemType x);
bool DeQueue(LinkQueue &Q,ElemType &m);
bool IsEmpty(LinkQueue Q);
#endif //TREE_FUNCTION_H
//
// Created by 斋心 on 2023/5/25.
//
#include "function.h"
//初始化队列,带头结点的链表
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
Q.front->next=NULL;//初始为空
}
//入队
void EnQueue(LinkQueue &Q,ElemType x){
LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;//本句不可省略
Q.rear->next=s;
Q.rear=s;
}
//出队
bool DeQueue(LinkQueue &Q,ElemType &m){ //Q.rear可能发生改变
if(Q.rear==Q.front){ //判断队列是否为空 //因为是带头结点的单链表，所以判断是rear=front
return false;
}
LinkNode *q=Q.front->next;//待删除结点
m=q->data;
Q.front->next=q->next;
if(Q.rear==q){ //判断待删除结点是否为最后一个结点
Q.rear=Q.front;
}
free(q);
return true;
}
//判断队列为空
bool IsEmpty(LinkQueue Q){
if(Q.rear==Q.front){
return true;
}
return false;
}
#include "function.h" //头文件的引用，注意引号
//前序遍历，也叫先序遍历，也是深度优先遍历
void PreOrder(BiTree p){
if(p!=NULL){
printf("%c",p->c);//等同于课本中的visit函数
PreOrder(p->lchild);
PreOrder(p->rchild);
}
}
//中序遍历
void InOrder(BiTree p){
if(p!=NULL){
InOrder(p->lchild);
printf("%c",p->c);
InOrder(p->rchild);
}
}
//后序遍历
void PostOrder(BiTree p){
if(p!=NULL){
PostOrder(p->lchild);
PostOrder(p->rchild);
printf("%c",p->c);
}
}
//层序遍历
void LevelOrder(BiTree T){
LinkQueue Q;//申请辅助队列
InitQueue(Q);
EnQueue(Q,T);//将树的根结点入队
BiTree p;//存储出队的结点
while(!IsEmpty(Q)){ //辅助队列非空，则将队头结点出队打印，并将其左孩子和右孩子依次入队
DeQueue(Q,p);
putchar(p->c);
if(p->lchild){
EnQueue(Q,p->lchild);
}
if(p->rchild){
EnQueue(Q,p->rchild);
}
}
}
int main() {
//层次建树
BiTree tree=NULL;//建立根结点并初始化
BiTree pnew;//新的树结点
BiElemType c;//用于赋值树结点数据的变量
ptag_t phead=NULL,ptail=NULL,list_new=NULL,pcur;//phead和ptail是队头和队尾指针;list_new为队列结点指针；pcur指向待插入孩子的结点地址
while(scanf("%c",&c)){
if(c=='\n'){
break;//跳出while循环
}
//calloc申请的空间大小是1×sizeof()，并对申请变量进行初始化
pnew=(BiTree)calloc(1,sizeof(BiTNode));//申请新的树结点
pnew->c=c;
list_new=(ptag_t)calloc(1,sizeof(tag_t));//申请新的辅助队列结点
//等价于list_new=(ptag_t)malloc(sizeof(tag_t));list_new->p=NULL;list_new->pnext=NULL;
list_new->p=pnew;
if(NULL==tree){ //如是树的根结点，则将根结点加入树，队头和队尾结点指向第一个队列节点
phead=ptail=list_new;
pcur=list_new;
tree=pnew;
}else{
ptail->pnext=list_new;
ptail=list_new;
if(NULL==pcur->p->lchild){
pcur->p->lchild=pnew;
}else if(NULL==pcur->p->rchild){
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;
}
输出结果：
abcdefg
-----------PreOrder-----------
abdecfg
-----------InOrder------------
dbeafcg
-----------PostOrder----------
debfgca
-----------LevelOrder----------
abcdefg
进程已结束，退出代码为 0
二、中序前序后序线索二叉树及其遍历
//
// Created by 斋心 on 2023/6/27.
//
#ifndef INC_13_4_FUNCTION_H
#define INC_13_4_FUNCTION_H
#include<stdio.h>
#include<stdlib.h>
//线索二叉树结点结构体类型申明
typedef char BiElemType;
typedef struct ThreadNode{
BiElemType c;//结点数据
struct ThreadNode *lchild,*rchild; //左孩子，右孩子
int ltag,rtag;//左前驱，右后继
}ThreadNode,*ThreadTree;
//创建二叉树的辅助队列结构体类型申明
typedef struct tag{
ThreadTree p;
struct tag *pnext;
}tag_t,*ptag_t;
#endif //INC_13_4_FUNCTION_H
#include "function.h"
//-----------------------------------------层次建树---------------------------------------------------------
//层次建树
//算法思想：设置链式辅助队列，用来存储树结点的地址，并用pcur记录当前待插入孩子结点的结点地址。
#include "function.h "
BiTree CreateBiTree(BiTree &T){
T=NULL;
BiElemType c;
BiTree pnew;
ptag_t phead=NULL,ptail=NULL,listnew,pcur;
int tag=0;//标志孩子结点是否已经插入，防止连续插入空结点的情形
while(scanf("%c",&c)){
if(c=='\n'){
break;
}
if(c=='0'){
pnew=NULL;
listnew=NULL;
}else{
pnew=(BiTree)calloc(1,sizeof(BiNode));
pnew->c=c;
listnew=(ptag_t)calloc(1,sizeof(tag_t));
listnew->p=pnew;
}
if(NULL==T){
phead=ptail=listnew;
pcur=listnew;
T=pnew;
}else{
if(listnew){
ptail->pnext=listnew;
ptail=listnew;
}
if(NULL==pcur->p->lchild&&tag!=1){
pcur->p->lchild=pnew;
tag=1;
}else{
pcur->p->rchild=pnew;
pcur=pcur->pnext;
tag=0;
}
}
}
return T;
}
//-----------------------------------------前序中序后序遍历-----------------------------------------------------------
//前序遍历
void PreOrder(ThreadTree T){
if(T){
printf("%c",T->c);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(ThreadTree T){
if(T){
InOrder(T->lchild);
printf("%c",T->c);
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(ThreadTree T){
if(T){
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->c);
}
}
//------------------------------------------二叉树线中序索化及其遍历------------------------------------------------------
//中序线索化二叉树
//算法思想：设置遍历结点的前驱指针pre，中序遍历二叉树，遍历至待visit结点时，如该结点左孩子为空，则建立前驱线索，指向前驱结点；
//如该结点右孩子为空，则建立pre的后继线索，指向后继结点；建立线索后pre指针后移，继续中序遍历。
//中序遍历二叉树并线索化，一边中序遍历一边线索化
void InThread(ThreadTree T,ThreadTree &pre){
if(T){
InThread(T->lchild,pre);
if(T->lchild==NULL){
T->lchild=pre;
T->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=T;
pre->rtag=1;
}
pre=T;
InThread(T->rchild,pre);
}
}
//建立中序线索二叉树
void CreateInThread(ThreadTree T){
ThreadTree pre=NULL; //前驱指针，初始化为NULL
if(T){ //非空二叉树才能线索化
InThread(T,pre);
if(pre->rchild==NULL){ //处理最后一个结点
pre->rtag=1;
}
}
}
//遍历中序线索二叉树：找到二叉树树第一个被遍历的结点（最左下结点），然后依次遍历其后继结点
//找到以T为根的子树中，第一个被中序遍历的结点，即该子树的最左下孩子结点
ThreadTree FirstInNode(ThreadTree T){
while(T->ltag==0){
T=T->lchild;
}
return T;
}
//在中序线索二叉树中找到结点p的后继结点：如p->rtag=1,则p的后继结点即为其中序后继；如p->tag=0，则其后继结点为其右子树的最左下结点
ThreadTree NextInNode(ThreadTree p){
if(p->rtag==0){
return FirstInNode(p->rchild);//p结点的后继结点为其右子树的最左下结点
}else{
return p->rchild; //线索后继
}
}
//遍历中序线索二叉树
void InOrderThread(ThreadTree T){
for(ThreadTree p=FirstInNode(T);p!=NULL;p=NextInNode(p)){
printf("%c",p->c);
}
}
//逆向遍历中序线索二叉树:找到树最后一个被遍历的结点，然后依次遍历其前驱结点
//找到以T为根的子树中，最后一个被中序遍历的结点:子树最右下结点
ThreadTree LastInNode(ThreadTree T){
while(T->rtag==0){
T=T->rchild;
}
return T;
}
//在中序线索二叉树中找到结点p的前驱结点：如p->ltag=1,则其前驱为p->lchild;如p->ltag=0，则其前驱结点为左子树最右下结点
ThreadTree PreInNode(ThreadTree p){
if(p->ltag==0){ //如果结点p有左子树，则其前驱结点为左子树最右下结点
return LastInNode(p->lchild);
}else{
return p->lchild;
}
}
//逆序遍历中序线索二叉树
void RevInOrder(ThreadTree T){
for(ThreadTree p=LastInNode(T);p!=NULL;p= PreInNode(p)){
printf("%c",p->c);
}
}
//----------------------------------二叉树先序线索化及其遍历-----------------------------------------------------
//一边先序遍历一边线索化
void PreThread(ThreadTree T,ThreadTree &pre){
if(T){
if(T->lchild==NULL){
T->lchild=pre;
T->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=T;
pre->rtag=1;
}
pre=T;
if(T->ltag==0){ //先序线索化后会产生原地转圈问题，所以要有条件
PreThread(T->lchild,pre);
}
if(T->rtag==0){ //先序线索化后会产生原地转圈问题，所以要有条件
PreThread(T->rchild,pre);
}
}
}
//建立先序线索二叉树
void CreatePreThread(ThreadTree T){
ThreadTree pre=NULL;//前驱指针
if(T){
PreThread(T,pre);
if(pre->rchild==NULL){ //处理最后一个结点
pre->rtag=1;
}
}
}
//遍历先序线索二叉树：从根结点开始，依次遍历其先序后继结点
//在先序线索二叉树中找到p的后继结点：如p->rtag=1,则其后继结点为其先序后继；
// 如p->rtag=0，则分情况：如p有左子树，则其后继结点为其左孩子，如p无左子树，则其后继结点为其右孩子
ThreadTree NextNode(ThreadTree p){
if(p->rtag==0){
if(p->ltag==0){
return p->lchild;
}else{
return p->rchild;
}
}else{
return p->rchild;//p结点的先序后继
}
}
//遍历先序线索二叉树
void PreOrderThread(ThreadTree T){
for(ThreadTree p=T;p!=NULL;p= NextNode(p)){
printf("%c",p->c);
}
}
//---------------------后序线索二叉树及其遍历--------------------------------------------------
//建立后序线索二叉树
//一边遍历一边线索化
void PostThread(ThreadTree T,ThreadTree &pre){
if(T){
PostThread(T->lchild,pre);
PostThread(T->rchild,pre);
if(T->lchild==NULL){
T->lchild=pre;
T->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=T;
pre->rtag=1;
}
pre=T;
}
}
//建立后序线索二叉树
void CreatePostThread(ThreadTree T){
ThreadTree pre=NULL;
if(T){
PostThread(T,pre);
if(pre->rchild==NULL){
pre->rtag=1;
}
}
}
//逆序遍历后序线索二叉树：从二叉树根结点开始，依次遍历其后序前驱结点
//在后序线索二叉树中找到p结点的前驱结点：如p->ltag=1,则前驱结点为p->lchild；
// 如p->ltag=0，则分情况：
//如p有右孩子，则p的前驱结点为其右孩子；如p无右孩子，则p的前驱结点为其左孩子
ThreadTree PreNode(ThreadTree p){
if(p->ltag==0){
if(p->rtag==0){
return p->rchild;
}else{
return p->lchild;
}
}else{
return p->lchild;
}
}
//逆序遍历后序二叉树
void RevPostOrder(ThreadTree T){
for(ThreadTree p=T;p!=NULL;p=PreNode(p)){
printf("%c",p->c);
}
}
int main() {
ThreadTree tree=NULL;//建立根结点
CreateTree(tree);
printf("------PreOrder--------\n");
PreOrder(tree);
printf("\n------InOrder--------\n");
InOrder(tree);
printf("\n------PostOrder-------\n");
PostOrder(tree);
// CreateInThread(tree);
// printf("\n------InOrderThread------\n");
// InOrderThread(tree);
// printf("\n-------RevInOrder--------\n");
// RevInOrder(tree);
// CreatePreThread(tree);
// printf("\n-------PreOrderThread----\n");
// PreOrderThread(tree);
CreatePostThread(tree);
printf("\n-------RevPostOrder------\n");
RevPostOrder(tree);
return 0;
}
输出结果：
abcdef0g
------PreOrder--------
abdgecf
------InOrder--------
gdbeafc
------PostOrder-------
gdebfca
-------RevPostOrder------
acfbedg
进程已结束，退出代码为 0
三、二叉树前序中序后序非递归遍历
//
// Created by 斋心 on 2023/6/30.
//
#ifndef INC_5_3_3_3_FUNCTION_H
#define INC_5_3_3_3_FUNCTION_H
#include<stdio.h>
#include<stdlib.h>
//二叉树结点结构体类型申明
typedef char BiElemType;
typedef struct BiNode{
BiElemType c;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
typedef BiTree ElemType;
//创建辅助队列结构体类型申明
typedef struct tag{
ElemType p;
struct tag *pnext;
}tag_t,*ptag_t;
//辅助链栈的结构体结构体类型申明
typedef struct stack{
ElemType data;
struct stack *next;
} stack, *Lstack;
//栈函数申明
void InitStack(Lstack &S);
void Push(Lstack &S,ElemType x);
void Pop(Lstack &S,ElemType &m);
void GetTop(Lstack S,ElemType &s);
bool IsEmpty(Lstack S);
#endif //INC_5_3_3_3_FUNCTION_H
//
// Created by 斋心 on 2023/6/30.
//
#include"function.h"
//带头结点的链栈初始化
void InitStack(Lstack &S){
S=(Lstack)calloc(1,sizeof(stack));
}
//进栈(头插法)
void Push(Lstack &S,ElemType x){
Lstack snew=(Lstack)calloc(1,sizeof(stack));
snew->data=x;
snew->next=S->next;
S->next=snew;
}
//出栈(从头出栈)
void Pop(Lstack &S,ElemType &m){
Lstack q=S->next;
m=q->data;
if(S->next!=NULL){ //栈不空，则出栈
S->next=q->next;
}
free(q);
}
//判断栈空
bool IsEmpty(Lstack S){
if(S->next==NULL){
return 1;
}
return 0;
}
//读取栈顶元素
void GetTop(Lstack S,ElemType &s){
if(S->next!=NULL){
s=S->next->data;
}
}
#include "function.h"
//层次建树
#include "function.h "
BiTree CreateBiTree(BiTree &T){
T=NULL;
BiElemType c;
BiTree pnew;
ptag_t phead=NULL,ptail=NULL,listnew,pcur;
int tag=0;//标志孩子结点是否已经插入，防止连续插入空结点的情形
while(scanf("%c",&c)){
if(c=='\n'){
break;
}
if(c=='0'){
pnew=NULL;
listnew=NULL;
}else{
pnew=(BiTree)calloc(1,sizeof(BiNode));
pnew->c=c;
listnew=(ptag_t)calloc(1,sizeof(tag_t));
listnew->p=pnew;
}
if(NULL==T){
phead=ptail=listnew;
pcur=listnew;
T=pnew;
}else{
if(listnew){
ptail->pnext=listnew;
ptail=listnew;
}
if(NULL==pcur->p->lchild&&tag!=1){
pcur->p->lchild=pnew;
tag=1;
}else{
pcur->p->rchild=pnew;
pcur=pcur->pnext;
tag=0;
}
}
}
return T;
}
//前序遍历--递归算法
void PreOrder(BiTree T){
if(T){
printf("%c",T->c);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//前序遍历--非递归算法
//算法思想：借助辅助栈。① 沿着根的左孩子，依次打印结点并入栈，直到左孩子为空；
//②栈顶元素依次出栈，判断其是否有右孩子，如有，则转向右孩子，按①继续；如无，继续出栈。
void PreOrderStack(BiTree T){
Lstack S=NULL;
InitStack(S);
BiTree p=T;
while(p||!IsEmpty(S)){
if(p){ //如结点有左孩子，则将左孩子依次打印并入栈
printf("%c",p->c);
Push(S,p);
p=p->lchild;
}else{
Pop(S,p);
if(p->rchild){
p=p->rchild;
}else{
p=NULL; //如无右孩子，则重置p指针，继续出栈
}
}
}
}
//中序遍历--递归算法
void InOrder(BiTree T){
if(T){
InOrder(T->lchild);
printf("%c",T->c);
InOrder(T->rchild);
}
}
//中序遍历--非递归算法
//算法思想：借助辅助栈。①沿着根的左孩子，依次入栈，直到左孩子为空；
// ②栈顶元素出栈并打印，判断其是否有右孩子：如有，则转向右孩子，继续①；如无，继续出栈。
void InOrderStack(BiTree T){
Lstack S=NULL;
InitStack(S);
BiTree p=T;//遍历指针
while(p||!IsEmpty(S)){
if(p){
Push(S,p);
p=p->lchild;
}else{
Pop(S,p);
printf("%c",p->c);
if(p->rchild){
p=p->rchild;
}else{
p=NULL;//如无右孩子，则重置p指针，继续出栈
}
}
}
}
//后序遍历--递归算法
void PostOrder(BiTree T){
if(T){
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->c);
}
}
//后序遍历--非递归算法
//算法思想：借助辅助栈。①沿着根的左孩子，依次入栈，直到左孩子为空； ②读取栈顶元素，如栈顶元素有右孩子且未被访问过，则转向右孩子，
// 按照①再将结点依次入栈；否则，将栈顶元素出栈，并访问。
void PostOrderStack(BiTree T){
Lstack S=NULL;
InitStack(S);
BiTree p=T,r=NULL;//p为遍历指针；r为临时指针，用于判断右孩子是否被访问过
while(p||!IsEmpty(S)){
if(p){ //如结点有左孩子，则将左孩子依次入栈
Push(S,p);
p=p->lchild;
}else{
GetTop(S,p); //读取栈顶元素
if(p->rchild&&p->rchild!=r){ //如栈顶元素有右孩子且未访问过，则转向其右子树继续进行①
p=p->rchild;
}else{
Pop(S,p);
printf("%c",p->c);
r=p; //标志访问过的结点
p=NULL;//结点访问完后，重置p指针
}
}
}
}
int main() {
BiTree tree=NULL;
CreateBiTree(tree);
printf("------PreOrder--------\n");
PreOrder(tree);
printf("\n------PreOrderStack----\n");
PreOrderStack(tree);
printf("\n------InOrder--------\n");
InOrder(tree);
printf("\n-------InOrderStack----\n");
InOrderStack(tree);
printf("\n------PostOrder-------\n");
PostOrder(tree);
printf("\n-----PostOrderStack-----\n");
PostOrderStack(tree);
return 0;
}
输出结果：
abcde000f00g
------PreOrder--------
abdgecf
------PreOrderStack----
abdgecf
------InOrder--------
gdbeafc
-------InOrderStack----
gdbeafc
------PostOrder-------
gdebfca
-----PostOrderStack-----
gdebfca
进程已结束，退出代码为 0