数据结构：非完全二叉树（递归实现）

非完全二叉树是指在二叉树中，除了叶子节点（无子节点）外，其他节点的子节点个数可以不同，即不一定是每个节点都有两个子节点，有右孩子时也不一定有左孩子。

tree.h

/*===============================================
*   文件名称：tree.h
*   创 建 者：cxy     
*   创建日期：2024年01月21日
*   描    述：
================================================*/
#ifndef _TREE_H
#define _TREE_H

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

typedef struct node{
    char data;
    struct node *lchild; //左孩子
    struct node *rchild; //右孩子
}Tree,*Ptree;

Ptree init();   //创建树
int preorder(Ptree root);  //先序遍历
int inorder(Ptree root);   //中序遍历
int postorder(Ptree root); //后序遍历

#endif

tree.c

/*===============================================
*   文件名称：tree.c
*   创 建 者：cxy     
*   创建日期：2024年01月21日
*   描    述：
================================================*/
#include "tree.h"

Ptree init()  //递归与回归 先根
{
    char ch;
    scanf("%c",&ch);
    Ptree root = NULL;
    if('#' == ch)
        return NULL;
    else
    {
        root = malloc(sizeof(Tree));
        root->data = ch;
        root->lchild = init();
        root->rchild = init();
    }

    return root;
}

int preorder(Ptree root)
{
    if(NULL == root)
        return 0;
    printf("%c",root->data);
    preorder(root->lchild);
    preorder(root->rchild);
   
    return 0;
}

int inorder(Ptree root)
{
    if(NULL == root)
        return 0;
    inorder(root->lchild);
    printf("%c",root->data);
    inorder(root->rchild);

    return 0;
}

int postorder(Ptree root)
{
    if(NULL == root)
        return 0;
    postorder(root->lchild);
    postorder(root->rchild);
    printf("%c",root->data);

    return 0;
}

main.c

/*===============================================
*   文件名称：mian.c
*   创 建 者：cxy     
*   创建日期：2024年01月21日
*   描    述：
================================================*/
#include "tree.h"

int main(int argc, char *argv[])
{ 
    Ptree root = NULL;
    root = init();

    printf("-----先序遍历-----\n");
    preorder(root);
    puts("");
    printf("-----中序遍历-----\n");
    inorder(root);
    puts("");
    printf("-----后序遍历-----\n");
    postorder(root);
    puts("");

    return 0;
}

结果