自动创建满二叉树

本文记录如何使用程序自动创建一个满二叉树(主要记录如何创建满二叉树的过程）

运行截图：(结果为先序排列） 

程序如下：

#define _CRT_SECURE_NO_WARNINGS 1
//假定输入的数据为完全二叉树的格式
#include 
#include 
#include 
#define MAXLEN 15//二叉树中元素的个数
typedef char DATA;//定义元素类型
int flag;//标识为，记录编码后结点的数值
typedef struct CBTTYPE
{
    DATA data;
    struct CBTTYPE *left;
    struct CBTTYPE *right;
}CBTTYPE;//二叉树结构体
static int num;
CBTTYPE *InitTree()//初始化二叉树，输入首结点
{
    CBTTYPE *node;
    if (node = (CBTTYPE *)malloc(sizeof(CBTTYPE)))
    {
        printf("请输入根结点数据:n");
        scanf("%s", &node->data);
        node->left = NULL;
        node->right = NULL;
        if (node != NULL)
        {
            return node;
        }
        else
        {
            return NULL;
        }
    }
    return NULL;
}
int power(int x, int y)//平方减1
{
    int i = 0;
    int result = 1;
    if (y == 0)return 0;
    for (; i < y; i++)
    {
        result = x *result;
    }
    return result - 1;
}
int log_x(int data)//求二的几次方，弄复杂了,可以直接除2算上一层的节点数
{
    for (int i = 1; i < 10; i++)
    {
        if (data < power(2, i) + 1)
        {
            return i;
        }
    }
    return 0;
}
void addNode(CBTTYPE* treenode,DATA* data)//满二叉树自动增加结点，每层从右向左
{
    //尝试使用编码方式
    //power(2,log_x(sizeof(data)))
    int ok = power(2, log_x(MAXLEN) -1 ) + 1;
    if (flag  < ok)
    {
        treenode->left = (CBTTYPE *)malloc(sizeof(CBTTYPE));
        flag = 2 * flag + 1;
        treenode->left->data = data[flag - 1];
        addNode(treenode->left, data);
        
        treenode->right = (CBTTYPE *)malloc(sizeof(CBTTYPE));
        flag = 2*flag;
        treenode->right->data = data[flag - 1];
        addNode(treenode->right, data);
    }
    else
    {
        treenode->left = NULL;
        treenode->right = NULL;
    }
    flag = flag /2;
}
void PreambleSort(CBTTYPE *treenode)//先序排序
{
    if (treenode->left != NULL && treenode->left->data != '#')
    {
        PreambleSort(treenode->left);
    }
    printf("%c", treenode->data);
    if (treenode->right != NULL && treenode->left->data  != '#')
    {
        PreambleSort(treenode->right);
    }
    
}
int main()
{
    flag = 1;//初始化为1
    CBTTYPE *root = NULL;
    root = InitTree();
    DATA* data = (DATA *)malloc(sizeof(DATA) * MAXLEN);//假设数据为ABCD#F#F####G
    scanf("%s", data);
    addNode(root, data);
    //printf("root的大小%d", power(2,4));
    PreambleSort(root);
}

记录一下关键点：

如上图所示，输入二叉树格式为ABCDEFG

我借助哈夫曼编码向右为0，像左为1，这样叶子层的大小就会超过上一层的大小，从而作为无下一层的依据。