二叉树层次建树，前序（递归与非递归）遍历--中序遍历（递归与非递归）-后序遍历-层次遍历-蒲公英云

创建一个二叉树

创建项目为创建C++项目

1.导包

开始前需要写一些导包

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

_CRT_SECURE_NO_WARNINGS这一串写或者不写跟你使用的编译器有关，此处是为了解决scanf（）的正常run——此处我用的是visual Studio 2022

2.类型别名设定

#define MaxSize 50
typedef  int ElemType;
typedef char BiElemType;

3.结构引入

二叉树的结构

typedef struct BiTNode {
      //二叉树的树节点
    BiElemType c;//c就是书籍上的data
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode,*BiTree;

储存树节点的队列节点

typedef struct tag {
     //储存树节点的队列节点
    BiTree p;//树
    struct tag* pnext;
}tag_t,*ptag_t;

递归实现前序遍历（先序遍历）

（先打印当前节点，再打印左孩子，再打印右孩子）

//递归实现 前序遍历（先序遍历）（先打印当前节点，再打印左孩子，再打印右孩子）
void preOrder(BiTree p) {
    if (p != NULL) {
        putchar(p->c);//等价于visit函数
        preOrder(p->lchild);
        preOrder(p->rchild);
    }
}

中序遍历

//中序遍历
void InOrder(BiTree p) {
    if (p!=NULL) {
        InOrder(p->lchild);
        putchar(p->c);
        InOrder(p->rchild);
    }
}

后序遍历

void PostOrder(BiTree p) {
    if (p != NULL) {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->c);
    }
}

中序遍历非递归，

非递归执行效率更高，需要借助栈来进行
因此先创建栈的结构

//typedef BiTree ElemType  
//上行代码 当与写在一个页面的时候感觉会与之前设定的产生不必要的混淆
//因此，将所有的原本的 ElemType 修改为  BiTree 
//如果你单独使用 上行代码时，也可以将BiTree 修改为ElemType 
typedef struct {
       //栈
    BiTree data[MaxSize];
    int top;
}SqStack;
//初始化栈
void InitStack(SqStack& S) {
    S.top = -1;
}
bool StackEmpty(SqStack& S) {
    if (S.top==-1) {
        return true;
    }
    else {
        return false;
    }
}
//入栈
bool Push(SqStack& S, BiTree x) {
    if (S.top==MaxSize-1) {
        return false;
    }
    S.data[++S.top] = x;
    return true;
}
//出栈
bool Pop(SqStack& S, BiTree&x) {
    if (-1==S.top) {
        return false;
    }
    x = S.data[S.top--];
    return true;
}
//获取栈顶元素
bool GetTop(SqStack& S, BiTree& x) {
    if (-1 == S.top) {
        return false;
    }
    x = S.data[S.top];
    return true;
}
//中序遍历非递归，非递归执行效率更高，
//中序遍历非递归
void InOrder2(BiTree T) {
    SqStack S;
    InitStack(S);//初始化栈
    BiTree p = T;
    while (p || !StackEmpty(S)) {
      //逻辑 或者 ||
        if (p) {
            Push(S,p);
            p = p->lchild;
        }
        else {
            Pop(S, p);
            putchar(p->c);
            p = p->rchild;
        }
    }
}

层次遍历（广度优先遍历）

//初始化队列  带头节点的队列
void InitQueue(LinkQueue& Q) {
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}
bool IsEmpty(LinkQueue Q) {
    if (Q.front==Q.rear)
    {
        return true;
    }
    else {
        return false;
    }
}
//入队
void EnQueue(LinkQueue& Q, BiTree x){
    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}
//出队
bool DeQueue(LinkQueue &Q,BiTree &x) {
    if (Q.front == Q.rear) {
        return false;
    }
    LinkNode* p = Q.front->next;//头结点什么都没存，所以头结点的下一个结点才有数据
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    free(p);
    return true;
}
//层次遍历 （广度优先遍历） 运用到辅助队列
void LevelOrder(BiTree T) {
    LinkQueue Q;//辅助队列
    InitQueue (Q);//初始化队列
    BiTree p;
    EnQueue(Q,T);//树根入队
    while (!IsEmpty(Q)) {
        DeQueue(Q,p);
        putchar(p->c);
        if (p->lchild!=NULL)
        {
            EnQueue(Q, p->lchild);
        };
        if (p->rchild!=NULL)
        {
            EnQueue(Q, p->rchild);
        }
    }
}

主函数

int main() {
    // ①树根要置空  队列初始化
    BiTree pnew; //二叉树结构指针
    //int i, j, pos;
    char c;
    BiTree tree = NULL;//树根（主）  
    ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pcur=NULL;
    //phead队列头 ptail队列尾 不带头节点的队列  pcur始终指向要插入的节点的位置
//②数据开始进入  abcdefghij   ||一开始a进来 
    while (scanf("%c",&c) != EOF) {
        //结束循环
        if (c == '\n') {
    //等于回车退出循环
            break;
        }
//③新建一个二叉树的节点空间 用于存储进来的a
        //将数据放入空间   pnew二叉树结构指针内有 c  lchild  rchild 三个参数
        //    ||当a刚进来时，new一个树的节点空间
        pnew = (BiTree)calloc(1, sizeof(BiTNode));//pnew通过calloc申请一个空间并且对空间进行初始化，赋值0
        pnew->c = c;//将数据放入pnew->c中 （放入树中）
//④新建一个队列的节点空间 将整个二叉树节点存入队列
        //listpnew 队列链表  内有 p  pnext 两个参数  
        //p（树节点）中有 c  lchild  rchild      
        //pnext中为p pnext
        listpnew = (ptag_t)calloc(1,sizeof(tag_t));//给队列节点申请一个空间，
        listpnew->p = pnew;  //将树节点作为数据存入队列   
//⑤首次存a时，树还为空 需要走下边的判断     
        if (NULL == tree) {
    //当主树根若为空，构建辅助队列
        //a放入树根
            tree = pnew;//树的根  此时让a作为树根
        //a放入队列
            //此时 由于队列中只有一个a，因此a既做队列头也做队列尾
            phead = listpnew;//队列头 队列头指针  
            ptail = listpnew;//队列尾 队列尾指针   队列中储存的是树节点的地址    
            pcur = listpnew; //pcur始终指向要插入的节点的位置
//⑥ continue 此次循环结束
            continue;
        }
//⑦  ①-④步相同  不过此时进入的是b 放入队列，通过尾插法
        else {
    //b当已经有主树的时候
            ptail->pnext = listpnew;//   新结点B放入队列，通过尾插法
            ptail = listpnew;//ptail队列尾指针 指向队列尾（新插入的b）
        }
//⑧  队列判断结束后，开始判断b进入树
//⑨ a节点树的左孩子若为空  新节点b放在tree的lchild里
        if (NULL == pcur->p->lchild) {
    //pcur为首次存放入a的时候给的定义
            pcur->p->lchild = pnew;   //pcur始终指向要插入的节点的位置
        }
//⑩ 1-8相同 但9不同 a节点树的左孩子存在值  新节点c放在tree的rchild里
        else if(NULL == pcur->p->rchild){
            pcur->p->rchild = pnew;  //pcur始终指向要插入的节点的位置
            pcur = pcur->pnext;//当左右孩子都放了后，就pcur指向下一个
        }
    }
    printf("答案输出\n");
    printf("------------前序遍历------------\n"); //（先打印当前节点，再打印左孩子，再打印右孩子）
        preOrder(tree);//abc    a bde cfg    a b dhi ej c fg
    printf("\n------------中序遍历------------\n");//（先打印打印左孩子，再打印当前节点,再打印右孩子）--------从上到下一脚踩扁
        InOrder(tree);        //bac     dbe a fcg  hdibjeafcg
    printf("\n------------后序遍历------------\n");//先打印打印左孩子，再打印右孩子,再打印当前节点
        PostOrder(tree);//bca   deb fgc a      hid jeb fgc a     hidjebfgca
    //printf("\n------------中序遍历非递归------\n");//难度比较大
    //    InOrder2(tree);
    //printf("\n------------层次遍历------------\n");
}