C语言二叉树前序、中序、后序、层序遍历

一时失言乱红尘 2023-10-11 17:40 40阅读 0赞

**知识点整理：**

1、前序遍历：根-左-右

2、中序遍历：左-根-右

3、后序遍历：左-右-根

4、层序遍历：从树根出发一层一层从左往右遍历

**代码展示：**

#include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    typedef struct node{
        char data;
        struct node *left,*right;
    }Node;
     Node *insert_node(Node *root,char c){
         if(root==NULL){
             Node *p=(Node *)malloc(sizeof(Node));
             p->data=c;
             p->left=p->right=NULL;
             return p;
         }
         int x=rand()%2;
         if(x==0){//往左子树插入
             root->left=insert_node(root->left,c);
         }
         else root->right=insert_node(root->right,c);
         return root;
     }
     void perorder(Node *root){//前序遍历
         if(root==NULL)//当前结点为空
           return ;
         printf("%c",root->data);//自身
         perorder(root->left);//左子树
         perorder(root->right);//右子树
     }
     void inorder(Node *root){//中序遍历
         if(root==NULL)//当前结点为空
           return ;
         inorder(root->left);//左子树
         printf("%c",root->data);//自身
         inorder(root->right);//右子树
     }
     void postorder(Node *root){//后序遍历
         if(root==NULL)//当前结点为空
           return ;    
         postorder(root->left);//左子树
         postorder(root->right);//右子树
         printf("%c",root->data);//自身
     }
     void levelorder(Node *root){//层序遍历
         Node *num[30];//队列
         int front=0,rear=1;//num[front]、num[rear]首、尾指针
         num[0]=root;
         while(front!=rear){
             Node *p=num[front];
             front++;
             printf("%c",p->data);
             if(p->left!=NULL) num[rear++]=p->left;
             if(p->right!=NULL) num[rear++]=p->right;
         }
        printf("\n");
     }
     int main(){
         srand(time(0));
         int n,mark[26];//标记数组，避免产生重复字母
         scanf("%d",&n);//二叉树的结点数
         Node *root=NULL;
         for(int i=0;i<n;i++){
             int x=rand()%26;//使'A'+x在26个字母范围内
             while(mark[x]==1)
               x=rand()%26;//避免重复
            mark[x]=1;//标记已出现的字母
            root=insert_node(root,'A'+x);//随机生成字母二叉树
         }
         printf("先序遍历： ");
         perorder(root);
         printf("\n中序遍历： ");
         inorder(root);
         printf("\n后序遍历： ");
         postorder(root);
         printf("\n层序遍历： ");
         levelorder(root);
     }

**运行结果示例：**

先序遍历： HBZUDA
    中序遍历： BHDUZA
    后序遍历： BDUAZH
    层序遍历： HBZUAD

该示例二叉树如下图所示：

![3cd56674f45549919e6829cc95e451c9.jpeg][]

[3cd56674f45549919e6829cc95e451c9.jpeg]: https://img-blog.csdnimg.cn/3cd56674f45549919e6829cc95e451c9.jpeg