用c语言实现前序创建二叉树（递归），分别用前序，中序，后序遍历，以及分别输出节点个数和叶子节点个数

本人c语言小白一枚，近期在学习数据结构（c语言版），特写此随笔，做一些总结和分享，如有不当之处，请各位技术大牛斧正

首先我们用一个结构体来抽象树的结点，代码如下（这里我们存放的数据为char型，大家可以根据自己不同的数据来自己定义，也可以在一开始用typedf特别定义一个类型，接下来就是两个指针，

用来指向左儿子和右儿子）

struct tnode{
    char data;
    struct tnode *lchild,*rchild;
};

一，如何前序创建一颗二叉树

首先简述一下前序创建二叉树的算法：其实前序创建一颗二叉树的算法非常简单，这里我们要用到递归的思想，先给根节点赋值，然后再依次给左子树的根节点和右子树的根节点赋值，用递归的思想将整颗树赋值。（在这里我们用‘#’来表示某个结点为空），代码如下：

struct tnode * creatTree(struct tnode *head){
    char e;
    scanf("%c",&e);
    fflush(stdin);
    if(e != '#'){
         head = (struct tnode *)malloc(sizeof(struct tnode));//先开辟空间
         head ->data = e;//判断不是'#'后,给根节点赋值
         head ->lchild = NULL;
         head ->rchild = NULL;　　　　　　//依次把左儿子和右儿子调用该方法进行赋值
         head ->lchild = creatTree(head->lchild);
         head ->rchild = creatTree(head->rchild);
    }
    return head;
}

这样我们就可以成功创建一颗二叉树

二，前序遍历二叉树

简述一下前序遍历二叉树的算法：（这里同样也要用到递归的思想），首先拜访头结点，然后拜访左子树，再拜访右子树，代码如下：

void preorderTree(struct tnode *head){
    //先拜访头结点
    printf("%c",head->data);
    //再走左子树
    if(head->lchild != NULL){//判断左子树是不是为空
         preorderTree(head->lchild);
    }
    if(head ->rchild !=NULL){//判断右子树是不是为空
        //再走右子树
        preorderTree(head->rchild);

    }
    return;
}

三，后序遍历二叉树：和前序遍历二叉树类似，只是我们要最后拜访根节点，同样用到了递归的思想，代码如下：

void postorderTree(struct tnode *head){
    //先左子树
    if(head->lchild != NULL){
        postorderTree(head->lchild);
    }

    //再右子树

    if(head->rchild != NULL){
        postorderTree(head->rchild);
    }
    //最后根节点
    printf("%c",head->data);
    return;
}

四，中序遍历二叉树：和前两种类似，我们先拜访左子树，再拜访根节点，最后拜访右子树，（同样用到了递归的思想）代码如下：

void inorderTree(struct tnode *head){
    //先走头结点
    printf("%c",head->data);

    //再走左子树
    if(head->lchild !=NULL){
        inorderTree(head->lchild);
    }
     //再走右子树
    if(head->rchild != NULL){
        inorderTree(head->rchild);
    }

    return;
}

五，输出节点的个数

思路：我们先在main函数里面定义一个计数器，在遍历的过程中，只要节点不是null，我们就让这个计数器++，这样就可以实现记录节点个数的功能啦，(在这里我们同样又用到了递归的思想，递归真的好重要的，到处都是递归),代码如下：(这里特别要注意的地方就是我们在main函数里面定义的计数器,一定要把地址给我们的函数,所以我们函数里面的形参是个int型的指针)

int sumNode(struct tnode *head,int *count){
    if(head == NULL){//判断根节点是否为空
        ;
    }else{
        //在这里我们用的是前序遍历二叉树的思想,先走根节点,在走左右子树
        *count += ;
        sumNode(head->lchild,count);
        sumNode(head->rchild,count);
    }
    return *count;
}

六，输出叶子节点的个数

简单思路：其实这个和上面输出节点的思路差不多，只不过我们要加一个判断条件，就是判断该结点是否为叶子节点，判断条件也很简单，只要看它的左右子树是否为空就好了，(同样也是用到了递归的思路)代码如下：

int numberLeafNode(struct tnode *head,int *countln){
    if(head->lchild == NULL&&head->rchild == NULL){//判断是否为叶子节点
        ;
    }else{//如果不是叶子节点的话,就去看它的左右子树是不是叶子节点
        if(head->lchild != NULL){
            numberLeafNode(head->lchild,countln);
        }
        if(head->rchild != NULL){
            numberLeafNode(head->rchild,countln);
        }
    }
}

以上就是全部内容,如有疑问和您的宝贵建议,尽情可以在评论中留言

巴特西

用c语言实现前序创建二叉树（递归），分别用前序，中序，后序遍历，以及分别输出节点个数和叶子节点个数

最新文章

热门文章