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

Question

实验三  二叉树基础算法
实验目的：
   掌握树和二叉树的概念、二叉树的链式存储结构及常用算法；。
实验内容及要求：
设字符型二叉树采用二叉链表作存储结构，编程实现二叉树的如下基本操作：
1. 二叉树的初始化（构造空树）；
以先序序列形式如A(B(C,D),E(F(G,H(,I),)构造该二叉树；
以先序和中序序列如ABCDEFGHI与CBDAGFHIE构造该二叉树；
求二叉树的高度、结点总数、叶结点数目；
交换二叉树各个结点的左右子树。
判断该树是否完全二叉树；
以层序方式遍历该二叉树进行遍历；
编写主函数测试以上各个操作；
2-7操作需给出算法基本思想及时空复杂度分析。2,3操作若觉得难度较大，可以改为以先序全序列AB##C##形式（书上算法6.4）构造二叉树；
备注：操作2,3中序列所代表的二叉树形态如下：
A
B E
C D F
G H
I
拜托了，很急的

Answer 1

#include <stdio.h>
#include <stdlib.h>
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;
}本回答被提问者和网友采纳