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

? ? ? ?如果完全二叉树的深度为h，那么除了第h层外，其他层的节点个数都是满的，第h层的节点都靠左排列。

? ? ? ?完全二叉树的编号方法是从上到下，从左到右，根节点为1号节点，设完全二叉树的节点数为sum，某节点编号为i，

? ? ? ?当2*i <= sum时，有左孩子，其编号为2*i，否则没有左孩子，本身为叶节点。

? ? ? ?当2*i+1 <= sum时，有右孩子，其编号为2*i+1，否则没有右孩子。

tree.h

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

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

typedef struct node{
    int data;
    struct node *lchild;
    struct node *rchild;
}Tree,*Ptree;

Ptree init(int i,int sum); //i为节点编号，sum为总数
int preorder(Ptree root);  //先序遍历
int inorder(Ptree root);   //中序遍历
int postorder(Ptree root); //后序遍历

#endif

tree.c

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

Ptree init(int i,int sum)
{
    Ptree root = malloc(sizeof(Tree));
    root->data = i;
    if(2*i <= sum)
    {
        root->lchild = init(2*i,sum);
    }
    else
    {
        root->lchild = NULL;
    }
    if(2*i+1 <= sum)
    {
        root->rchild = init(2*i+1,sum);
    }
    else
    {
        root->rchild = NULL;
    }
    return root;
}

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

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

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

main.c

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

int main(int argc, char *argv[])
{ 
    Ptree root;
    root = init(1,9);
    printf("-----先序遍历-----\n");
    preorder(root);
    puts("");
    printf("-----中序遍历-----\n");
    inorder(root);
    puts("");
    printf("-----后序遍历-----\n");
    postorder(root);
    puts("");


    return 0;
} 

结果