c语言实现二叉树的建立与前序、中序、后序、层序遍历

太过爱你忘了你带给我的痛 2022-06-09 09:09 18阅读 0赞

--------------------

## 树的节点与函数的定义 ##

typedef char ElemType;
    
    typedef struct BiTNode{
        ElemType data;
        struct BiTNode * lchild , * rchild;
    }BiTNode, * BiTree;
    
    void CreateBiTree(BiTree T);
    BiTree CreateBiTree1();
    void Visit(BiTree T);
    void PreOrder(BiTree T);
    void InOrder(BiTree T);
    void PostOrder(BiTree T);
    void LevelOrder(BiTree T);

--------------------

## 树的建立 ##

**错误的树的建立函数**

void CreateBiTree(BiTree T){
        char ch;
        scanf("%c", &ch);
        if(ch == '#') T = NULL;
        else{
            T = (BiTree)malloc(sizeof(BiTNode));
            T->data = ch;
            CreateBiTree(T->lchild);
            CreateBiTree(T->rchild);
        }
    }

**正确的树的建立函数**

BiTree CreateBiTree1(){
        char ch;
        BiTree T;
        scanf("%c", &ch);
        if(ch == '#') T = NULL;
        else{
            T = (BiTree)malloc(sizeof(BiTNode));
            T->data = ch;
            T->lchild = CreateBiTree1();
            T->rchild = CreateBiTree1();
        }
        return T;
    }

**注意比较两个函数的区别：**  
如果不自己运行调试一遍根本找不出来错误，只有自己动手运行一遍才会发现第一种和第二种方法看似不同，实则差别很大。  
本人用第一个函数也调试了很久，把指针一个一个的printf出来，找到问题。  
第一个函数建立不了完整的树，因为malloc函数的问题，本来存在的指针经过malloc之后，又重新分配了一个与原来不一样的空间，因此第一个函数进行构造的时候，会有很多指针为空。  
使用第二个函数进行构造的好处是：每有一个节点，就会单独的分配一个存储空间。每个几点的左子树和右子树也能够很好的通过递归链接起来。

--------------------

## 树的遍历 ##

树的前序，中序，后序遍历直接使用递归就行

void Visit(BiTree T){
        printf("%c ", T->data);
    }
    
    void PreOrder(BiTree T){
        if(T != NULL){
            Visit(T);
            PreOrder(T->lchild);
            PreOrder(T->rchild);
        }
    }
    
    void InOrder(BiTree T){
        if(T != NULL){
            InOrder(T->lchild);
            Visit(T);
            InOrder(T->rchild);
        }
    }
    
    void PostOrder(BiTree T){
        if(T != NULL){
            PostOrder(T->lchild);
            PostOrder(T->rchild);
            Visit(T);
        }
    }

## 树的层序遍历 ##

树的层序遍历需要用到队列，这里引入了队列构造的一些函数

typedef BiTree ElemTypeList;
    
    typedef struct{
        ElemTypeList data[MaxSize];
        int front, rear;
    }SqQueue;
    
    
    void InitQueue(SqQueue * Q);
    int QueueEmpty(SqQueue Q);
    int EnQueue(SqQueue * Q, ElemTypeList e);
    int DeQueue(SqQueue * Q, ElemTypeList * e);

这里需要注意的是，队列的数组是一个指针数组，每一个元素是一个指针，指向的是树的节点BitNode，这样，在编写层序遍历的程序的时候，就非常地简洁。  
队列函数的实现：

void InitQueue(SqQueue * Q){
        Q->front = Q->rear = 0;
    }
    
    int QueueEmpty(SqQueue Q){
        if(Q.front == Q.rear) return 1;
        return 0;
    }
    
    
    int EnQueue(SqQueue * Q, ElemTypeList e){
        if((Q->rear + 1) % MaxSize == Q->front){
            printf("queue is full!");
            return 0;}//队列满，牺牲一个存储单元
        Q->data[Q->rear] = e;
        Q->rear = (Q->rear+1) % MaxSize;
        return 1;
    }
    
    int DeQueue(SqQueue * Q, ElemTypeList * e){
        if(QueueEmpty(* Q)) return 0;
        * e = Q->data[Q->front];
        Q->front = (Q->front + 1) % MaxSize;
        return 1;
    }

将队列的代码写好之后，层序遍历的思想也是很精髓的。  
先将二叉树的根节点入队，然后出队，访问该结点。（注意这个算法的这个该结点的重要性）。如果该结点有左子树，则将左子树入队。如果有右子树，则将右子树入队。如果队列不为空，就出队，再对该出队结点进行循环

void LevelOrder(BiTree T){
        SqQueue Q;
        InitQueue(& Q);
        EnQueue(& Q, T);
        BiTree p;
        while(!QueueEmpty(Q)){
            DeQueue(& Q, & p);
            Visit(p);
            if(p->lchild != NULL)
                EnQueue(& Q, p->lchild);
            if(p->rchild != NULL)
                EnQueue(& Q, p->rchild);
        }
    }

--------------------

## 程序的测试 ##

**二叉树的性质：n个节点的二叉树有n+1个空指针域**  
因此在输入的时候，有几个数字就会有n+1个‘\#’  
主函数如下：

#include <stdio.h>
    #include "tree.h"
    
    int main(int argc, const char * argv[]) {
        BiTree T;
        printf("please input the tree node:\n");
        T = CreateBiTree1();
        printf("the PreOrder node:\n");
        PreOrder(T);
        printf("\nthe InOrder node:\n");
        InOrder(T);
        printf("\nthe PostOrder node:\n");
        PostOrder(T);
        printf("\nthe LevelOrder node:\n");
        LevelOrder(T);
        printf("\n");
        return 0;
    }

测试的二叉树如图：  
![这里写图片描述][SouthEast]  
测试输入的时候，应该输入的是：  
12\#46\#\#\#3\#5\#\#  
前序遍历的理论结果：1 2 4 6 3 5  
中序遍历的理论结果：2 6 4 1 3 5  
后序遍历的理论结果：6 4 2 5 3 1  
层序遍历的理论结果：1 2 3 4 5 6  
其实遍历就按照递归算法的思想就行了。  
运行程序得到的结果如下：  
![这里写图片描述][SouthEast 1]  
可以看到运行的结果是与理想的结果是一致的。

[SouthEast]: /images/20220609/823292a3dde843d386f521ac511f98c7.png
[SouthEast 1]: /images/20220609/8415f8e6370341938c8e1d5ff554d78b.png