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

#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 = 0ll->next != NULL &&i <indexi++)

{

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

}

刚刚回答了一个类似的问题，以下代码供参考：

#include "stdio.h"

#include "stdlib.h"

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef char TElemType

typedef int Status

typedef struct BiTNode { // 结点结构

TElemType data

struct BiTNode *lchild, *rchild

// 左右孩子指针

} BiTNode, *BiTree

//以下是建立二叉树存储结构，空节点输入作为#结束标识

Status CreateBiTree(BiTree &T) {

//请将该算法补充完整，参见第6章课件算法或课本

char ch

scanf("%c",&ch)

if(ch=='#') T=NULL

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW)

T->data=ch

CreateBiTree(T->lchild)

CreateBiTree(T->rchild)

}

return OK

} // CreateBiTree

void Preorder(BiTree T)

{

if(T)

{

printf("%c",T->data)

Preorder(T->lchild)

Preorder(T->rchild)

}

}

void Inorder(BiTree T)

{ // 中序遍历二叉树

//请将该算法补充完整，参见第6章课件算法

if(T)

{

Inorder(T->lchild)

printf("%c",T->data)

Inorder(T->rchild)

}

}

void Postorder(BiTree T)

{ // 后序遍历二叉树

//请将该算法补充完整，参见第6章课件算法

if(T)

{

Postorder(T->lchild)

Postorder(T->rchild)

printf("%c",T->data)

}

}

//以下是求叶子结点数

void CountLeaf(BiTree T,int&count){

//请将该算法补充完整，参见第6章课件算法

if(T){

if((!T->lchild)&&(!T->rchild))

count++

CountLeaf(T->lchild,count)

CountLeaf(T->rchild,count)

}

}

//以下是求二叉树的深度

int Depth(BiTree T ){

//请将该算法补充完整，参见第6章课件算法

int depthval,depthLeft,depthRight

if(!T) depthval=0

else{

depthLeft = Depth(T->lchild)

depthRight = Depth(T->rchild)

if(depthLeft>depthRight)depthval = 1+depthLeft

else depthval = 1+depthRight

}

return depthval

}

void main(){

BiTree T

int s=0,d

printf("\n creat of the bitree:\n")

CreateBiTree(T)

printf("\n output result of Preorder:\n")

Preorder(T)

CountLeaf(T,s)

d=Depth(T)

printf("\n leaves=%d\n",s)

printf("\n depth=%d\n",d)

}

void PreOrder(BiTree T)//先序

{

if(T!=NULL)

{

printf("%c",T->data)

PreOrder(T->lchild)

PreOrder(T->rchild)

}

}

void InOrder(BiTree T)//中序

{

if(T!=NULL)

{

InOrder(T->lchild)

printf("%c",T->data)

InOrder(T->rchild)

}

}

void PostOrder(BiTree T)//后序

{

if(T!=NULL)

{

PostOrder(T->lchild)

PostOrder(T->rchild)

printf("%c",T->data)

}

}

全部程序

void PreOrder(BiTree T)//先序

{

if(T!=NULL)

{

printf("%c",T->data)

PreOrder(T->lchild)

PreOrder(T->rchild)

}

}

void InOrder(BiTree T)//中序

{

if(T!=NULL)

{

InOrder(T->lchild)

printf("%c",T->data)

InOrder(T->rchild)

}

}

void PostOrder(BiTree T)//后序

{

if(T!=NULL)

{

PostOrder(T->lchild)

PostOrder(T->rchild)

printf("%c",T->data)

}

}

---