用C++写一个二叉树的程序

2025-02-13 10:13:54

推荐回答（1个）

回答1：

#include
#include
typedef struct {
char data;
int weight;
} bitree_data_t;

typedef struct bitree
{
bitree_data_t data;
struct bitree *lchild, *rchild;
}bitree_t;

typedef bitree_t * data_t;
typedef struct linknode {
data_t data;
struct linknode *next;
}linknode_t, linkstack_t, linklist_t;

//创建一个链表
//1. 在内存总开辟头结点的空间malloc
//2. 将头结点的next域置空NULL
//3. 返回创建并设置好的链表的首地址
linklist_t *create_linklist()
{
linknode_t *node = (linknode_t *)malloc(sizeof(linknode_t));
node->next = NULL;

return node;
}

//判断当前链表是否为空
int empty_linklist(linklist_t *ll)
{
return ll->next == NULL;
}
//求链表中当前有效元素的个数
int length_linklist(linklist_t *ll)
{
int length = 0;
while(ll->next != NULL)
{
ll = ll->next;
length++;
}

return length;
}
//获得下标为index位置的元素，成功返回0，失败返回-1
//1. 判断index是否合法(部分判断)
//2. 在保证ll->next 不为空的清空下，将ll的首地址向后移动index次
//3. 判断ll->next 是否等于空，如果等于空，则返回-1，如果不为空，执行4.
//4. 当移动了index次之后，当前ll->next 的位置的节点就保存了我要获得的
//数据
//5. *data = ll->next->data;
//6. 返回0
int get_linklist(linklist_t *ll, int index, data_t *data)
{
int i;
if(index < 0)
return -1;

for(i = 0; ll->next != NULL && i < index; i++)
{
ll = ll->next;
}

if(ll->next == NULL)
return -1;

*data = ll->next->data;
return 0;
}
//使用头插法插入一个元素
//1. 创建一个节点node
//2. 将要插入的数据保存到node
//3. 执行插入操作
//4. 返回0
int insert_linklist(linklist_t *ll, data_t *data)
{
linknode_t *node = (linknode_t *)malloc(sizeof(linknode_t));
node->data = *data;

node->next = ll->next;
ll->next = node;
return 0;
}
//删除链表中的一个节点:删除头结点的后一个位置(头删法)
//首先可以判断当前链表是否为空，如果为空返回-1
//如果不为空则删除头结点的下一个位置的节点
//最后返回0
int delete_linklist(linklist_t *ll)
{
linknode_t *node;
if(empty_linklist(ll))
return -1;
node = ll->next;
ll->next = node->next;
free(node);

return 0;
}
//清空链表
//循环删除链表的一个节点，然后判断删除函数的返回值是否为0
//如果为0，继续删除，如果为-1则停止循环
int clear_linklist(linklist_t *ll)
{
while(delete_linklist(ll) == 0);
return 0;
}
//销毁链表
//1. 调用清空操作清空链表
//2. 删除头结点
//3. 返回0
int detory_linklist(linklist_t *ll)
{
clear_linklist(ll);
free(ll);
return 0;
}

void preorder(bitree_t *root)
{
if(root == NULL)
return ;
printf("[%c,%d]", root->data.data, root->data.weight);
preorder(root->lchild);
preorder(root->rchild);

return;
}

int insert_order_linklist(linklist_t *ll, data_t *data)
{
linknode_t *node = (linknode_t *)malloc(sizeof(linknode_t));
node->data = *data;
while(ll->next != NULL && ll->next->data->data.weight < node->data->data.weight)
{
ll = ll->next;
}

node->next = ll->next;
ll->next = node;

return 0;
}

bitree_t *huffman_bitree(linklist_t *ll)
{
bitree_t *node1, *node2, *root;
while(ll->next != NULL && ll->next->next != NULL)
{
get_linklist(ll, 0, &node1);
delete_linklist(ll);
get_linklist(ll, 0, &node2);
delete_linklist(ll);

root = (bitree_t *)malloc(sizeof(bitree_t));
root->data.data = '#';
root->data.weight = node1->data.weight + node2->data.weight;
root->lchild = node1;
root->rchild = node2;
insert_order_linklist(ll, &root);
}
get_linklist(ll, 0, &root);
delete_linklist(ll);

return root;
}

int main(void)
{
bitree_data_t data;
bitree_t *leaf;
linklist_t *ll;
ll = create_linklist();

while(scanf("[%c,%d]", &data.data, &data.weight) == 2)
{
getchar();

leaf = (bitree_t *)malloc(sizeof(bitree_t));
leaf->lchild = leaf->rchild = NULL;
leaf->data = data;
insert_order_linklist(ll, &leaf);
}
leaf = huffman_bitree(ll);
preorder(leaf);
putchar(10);
return 0;
}

最新问答

成都恩喜整形医院全切双眼皮哪个医生做的效果比较好啊，费用大概多少钱呢？

关于变压器油的介绍，主要是生产厂家，非代理商，国内外知名企业有哪些？谢谢

1861~1908大清国慈禧皇太后纪念币!看看真伪?价格?

1986年火虎和男1976年火龙八字相合吗?

苹果6S屏幕图标不显示未接来电,点进去才知道有未接电话,是怎么回事?

狗狗吃了骨头后又吐又拉血，怎么办？