小言_互联网的博客

二叉树的层序遍历+非递归算法（C语言）

2021-04-26 21:30 395人阅读  评论(0)

学校数据结构的题也完成差不多，最近也在考虑博客应该写那些方面。毕竟大学里学习还是以考试为中心，我也就把平时看什么就写出来吧。

层序遍历

队列用数组实现

层序遍历就是按二叉树一层一层遍历，我认为已经很直观了其实。写这篇博客就是加强我二叉树与栈和队列的联合应用的能力，毕竟学到道理与敲代码出来差距是很大的。

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

#define MAXSIZE 100
typedef struct Node{
   
char data;
struct Node *Lchild;
struct Node *Rchild;
}BiTNode,*Bitree;

typedef struct queue{
   
    BiTNode *numQ[MAXSIZE];//注意此处为关键。我们用的队列要与我们的ADT类型相同！！
    int front;
    int rear;
}Queue;//在这里我选择用数组来操作



void CreateBinTree(BiTNode **T)
{
   
    char ch;
    ch=getchar();
   if(ch=='#'){
    *T=NULL;return;}

            *T=(BiTNode*)malloc(sizeof(BiTNode));
            (*T)->data=ch;
        CreateBinTree(&((*T)->Lchild));
        CreateBinTree(&((*T)->Rchild));
}
void PreTree(Bitree T)
{
      if(T==NULL) return;
    printf("%c ",T->data);
     PreTree(T->Lchild);
     PreTree(T->Rchild);

}


//以下为建立队列的基本操作，注意与二叉树对应
void initilize(Queue *Q) {
    //初始化队列
    Q->front = 0;
    Q->rear = 0;
}

void Push(Queue *Q,BiTNode *T)//入队
//我还是比较喜欢用带*的来表示指针，比较直观
{
   
    Q->rear++;
    Q->numQ[Q->rear]=T;
}

BiTNode *Pop(Queue *Q)//出队
{
   
    Q->front++;
    return Q->numQ[Q->front];
}

int Isempty(Queue *Q)//判断是否为空
{
   
    return Q->front==Q->rear;
}

void LayerOrder(BiTNode *T)//二叉树的层次遍历
{
   
    Queue Q;
    initilize(&Q);
    BiTNode *p;
    Push(&Q,T);
    while(!Isempty(&Q))
    {
   
        p=Pop(&Q);
        printf("%c ",p->data);//输出队首结点
        if(p->Lchild) Push(&Q,p->Lchild);//把Pop掉的结点的左子结点加入队列
        if(p->Rchild) Push(&Q,p->Rchild);//把Pop掉的结点的右子结点加入队列
    }


}
int main()
{
   
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    //PreTree(T);
    LayerOrder(T);
    return 0;
}

这就完事了，如图：



（灵魂画师）
这里最后可以不在 LayerOrder中建立队列，可以在主函数中建立，调用时就不用加&了，如下代码：
（变化仅仅在最后两个函数，读者有兴趣可以粘贴试一试）

void LayerOrder(Queue *Q,BiTNode *T)//二叉树的层次遍历
{
   

    BiTNode *p;
    Push(Q,T);
    while(!Isempty(Q))
    {
   
        p=Pop(Q);
        printf("%c ",p->data);//输出队首结点
        if(p->Lchild) Push(Q,p->Lchild);//把Pop掉的结点的左子结点加入队列
        if(p->Rchild) Push(Q,p->Rchild);//把Pop掉的结点的右子结点加入队列
    }


}
int main()
{
   
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    Queue Q;
    initilize(&Q);
    //PreTree(T);
    LayerOrder(&Q,T);
    return 0;
}

或者，完全可以定义全局变量，这样就根本不用在函数调用Q，用的时候直接用" . “来访问，不用“->”，不失为一种好方法。

这里最关键为建立队列时建立的数组为BitTreeNode * 类型的，要相对应。

用链队列实现

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

#define MAXSIZE 100

typedef struct TreeNode{
   
char data;
struct TreeNode *Lchild;
struct TreeNode *Rchild;
}BiTNode,*Bitree;

typedef BiTNode* QueueElemType;//终于懂了啥叫用户自定义类型了

typedef struct Node
{
   
    QueueElemType data;
    struct Node *next;
}LQNode;

typedef struct {
   
LQNode *front;
LQNode *near;
}LinkQueue;

void CreateBinTree(BiTNode **T)
{
   
    char ch;
    ch=getchar();
   if(ch=='#'){
    *T=NULL;return;}

            *T=(BiTNode*)malloc(sizeof(BiTNode));
            (*T)->data=ch;
        CreateBinTree(&((*T)->Lchild));
        CreateBinTree(&((*T)->Rchild));
}
void PreTree(Bitree T)
{
      if(T==NULL) return;
    printf("%c ",T->data);
     PreTree(T->Lchild);
     PreTree(T->Rchild);
}

//以下为建立链队列的基本操作，注意与二叉树对应

void initilize(LinkQueue *Q) {
    //初始化队列
     Q->front=(LQNode*)malloc(sizeof(LQNode));
     Q->near=Q->front;
    Q->front->next=NULL;
}


void EnterQueue(LinkQueue *Q,BiTNode *x)//入队
{
   
    LQNode *NewNode;
    NewNode=(LQNode*)malloc(sizeof(LQNode));

    if(NewNode!=NULL)
    {
   
        NewNode->data=x;
        NewNode->next=NULL;
        Q->near->next=NewNode;
        Q->near=NewNode;
    }
}

BiTNode *DeleteQueue(LinkQueue *Q)//出队
{
   
    LQNode *p;
    p=Q->front->next;
    Q->front->next=p->next;
    if(Q->near==p)  //若只有一个元素
    {
   
        Q->front=Q->near;
    }

    return p->data;
}

int Isempty(LinkQueue *Q)
{
   
    return Q->front==Q->near;
}

void LayerOrder(LinkQueue *Q,BiTNode *T)//二叉树的层次遍历
{
   

    BiTNode *p;
    EnterQueue(Q,T);
    while(!Isempty(Q))
    {
   
        p=DeleteQueue(Q);
        printf("%c ",p->data);//输出队首结点
        if(p->Lchild) EnterQueue(Q,p->Lchild);//把Pop掉的结点的左子结点加入队列
        if(p->Rchild) EnterQueue(Q,p->Rchild);//把Pop掉的结点的右子结点加入队列
    }
}

int main()
{
   
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    //PreTree(T);

    LinkQueue *Q=(LinkQueue*)malloc(sizeof(LinkQueue));
    initilize(Q);

    LayerOrder(Q,T);
    return 0;

}


有一点要注意，就是我在主函数中定义 *Q，需要分配空间才能调用初始化函数进行初始化，若是初始化直接在主函数中进行，则不必须分配Q的空间。
像我在前面用数组队列的时候就是直接定义Q，但这里用指针操作则必须定义 *Q。
我认为这里难懂的是什么时候用&，这里还是平时经验和编译的时候报不报错来判断的。谨记指针即是地址，在函数中调用过地址的变量所代表即是地址。
话说还是数组来的方便，用链队列太麻烦。

非递归算法

中序遍历的非递归算法

模拟栈

这里就是模拟压栈操作进行模拟递归，比较递归本质就是压栈。

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

#define MAXSIZE 100

typedef struct TreeNode{
   
char data;
struct TreeNode *Lchild;
struct TreeNode *Rchild;
}BiTNode,*Bitree;

void CreateBinTree(BiTNode **T)
{
   
    char ch;
    ch=getchar();
   if(ch=='#'){
    *T=NULL;return;}

            *T=(BiTNode*)malloc(sizeof(BiTNode));
            (*T)->data=ch;
        CreateBinTree(&((*T)->Lchild));
        CreateBinTree(&((*T)->Rchild));
}

void PreTree(Bitree T)//中序输出
{
      if(T==NULL) return;

     PreTree(T->Lchild);
      printf("%c ",T->data);
     PreTree(T->Rchild);

}
void inorder(BiTNode *T)//中序输出非递归
{
   
    BiTNode *s[MAXSIZE];//模拟栈
    int top=0;
    BiTNode *p;
    p=T;
    do{
   
        while(p!=NULL)
        {
   
            if(top>MAXSIZE) return ;
            top++;
            s[top]=p;
            p=p->Lchild;
        }//遍历左子树
        if(top!=0)
        {
   
            p=s[top];
            top--;
            printf("%c ",p->data);//访问根结点
            p=p->Rchild;//遍历右子树
        }
    }while(p!=NULL||top!=0);
}
int main()
{
   
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    PreTree(T);
    printf("\n");
    inorder(T);

    return 0;
}

如图可验证正确性：

调用栈操作

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

#define MAXSIZE 100

typedef struct TreeNode{
   
char data;
struct TreeNode *Lchild;
struct TreeNode *Rchild;
}BiTNode,*Bitree;

typedef struct stack
{
   
    BiTNode *s[MAXSIZE];
    int top;
}Stack;

void CreateBinTree(BiTNode **T)
{
   
    char ch;
    ch=getchar();
   if(ch=='#'){
    *T=NULL;return;}

            *T=(BiTNode*)malloc(sizeof(BiTNode));
            (*T)->data=ch;
        CreateBinTree(&((*T)->Lchild));
        CreateBinTree(&((*T)->Rchild));
}

void PreTree(Bitree T)//中序输出
{
      if(T==NULL) return;

     PreTree(T->Lchild);
      printf("%c ",T->data);
     PreTree(T->Rchild);

}
void inorder(BiTNode *T)//中序输出非递归
{
   
    BiTNode *s[MAXSIZE];//模拟栈
    int top=0;
    BiTNode *p;
    p=T;
    do{
   
        while(p!=NULL)
        {
   
            if(top>MAXSIZE) return ;
            top++;
            s[top]=p;
            p=p->Lchild;
        }//遍历左子树
        if(top!=0)
        {
   
            p=s[top];
            top--;
            printf("%c ",p->data);//访问根结点
            p=p->Rchild;//遍历右子树
        }
    }while(p!=NULL||top!=0);
}
//以下为建立栈的基本操作，注意与二叉树对应
void InitStack(Stack *S)//初始化
{
   
    S->top=0;
}

void Push(Stack *S,BiTNode *T)//压栈
{
   
    S->top++;
    S->s[S->top]=T;
}

BiTNode *Pop(Stack *S)//出栈
{
   
    BiTNode *p;
    p=S->s[S->top];
    S->top--;
    return p;
}

int Isempty(Stack *S)
{
   
    if(S->top==0) return 1;
    else return 0;
}
void inordermoder2(BiTNode *T)
{
   
    Stack S;
    InitStack(&S);
    BiTNode *p;
    p=T;
    while(p!=NULL||!Isempty(&S))
    {
   
        if(p!=NULL)//遍历左子树
        {
   
            Push(&S,p);
            p=p->Lchild;
            printf("0");
        }
        else{
   
                 printf("1");
            p=Pop(&S);
            printf("%c ",p->data);
            p-p->Rchild;
        }
    }

}

int main()
{
   
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    PreTree(T);
    printf("\n");
    inordermoder2(T);

    return 0;
}

建完队列再建栈发现真简单。

后序遍历非递归

//以下为建立栈的基本操作，注意与二叉树对应
void InitStack(Stack *S)//初始化
{
   
    S->top=0;
}

void Push(Stack *S,BiTNode *T)//压栈
{
   
    S->top++;
    S->s[S->top]=T;
}

BiTNode *Pop(Stack *S)//出栈
{
   
    BiTNode *p;
    p=S->s[S->top];
    S->top--;
    return p;
}
void gettop(Stack *S,BiTNode **T)//取栈头
//注意修改树一律用二级指针
{
   
    (*T)=S->s[S->top];
}

int Isempty(Stack *S)
{
   
    if(S->top==0) return 1;
    else return 0;
}
void inordermoder2(BiTNode *T)
{
   
    Stack S;
    InitStack(&S);
    BiTNode *p;
    p=T;
   while(p!=NULL||!Isempty(&S))
    {
   
        if(p!=NULL)//遍历左子树
        {
   
            Push(&S,p);
            p=p->Lchild;
            printf("0");
        }
        else{
   
                 printf("1");
            p=Pop(&S);
            printf("%c ",p->data);
            p-p->Rchild;
        }
    }

}
void PreTree2(Bitree T)//后序输出
{
      if(T==NULL) return;

     PreTree(T->Lchild);

     PreTree(T->Rchild);

     printf("%c ",T->data);

}
void PostOrder(BiTNode *T)//后序输出非递归
{
   
    Stack S;
    BiTNode *q,*p;
    q=NULL;
    p=T;
    InitStack(&S);
    while(p!=NULL||!Isempty(&S))
    {
   
        if(p!=NULL)
        {
   
            Push(&S,p);
            p=p->Lchild;
        }//遍历左子树
        else{
   
                gettop(&S,&p);
                if(p->Rchild==NULL||(p->Rchild==q))
                {
   
                    printf("%c ",p->data);
                    q=p;
                    p=Pop(&S);
                    p=NULL;
                }
                else{
   
                    p=p->Rchild;
                }
        }
    }
}


完事，手打一遍感觉还是有很大收获的。


转载：https://blog.csdn.net/qq_52290436/article/details/116126419
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场