#include"Bintree.h"
/****************************************************/
/* 树的结点个数 */
/****************************************************/
int num_of_node(Bintree t)
{
if(t==NULL)return 0 ;
else return num_of_node(t->lchild)+num_of_node(t->rchild)+1;
} int main()
{
Bintree root,p;
Creat_Bintree(&root);
printf("%d\n",num_of_node(root));
return 0;
} #include"Bintree.h"
/*******************************************************/
/* 已知一课棵二叉树的中序和前序序列，建立这棵树 */
/*******************************************************/
void Pre_In_order(Bintree
*t,char *s,char *r)
{
char La[30],Lb[30],Ra[30],Rb[30];
int i,len;
if(s[0]!='\0')
{
*t=(Binnode *)malloc(sizeof(Binnode));
(*t)->data=s[0];
for(i=0;r[i]!=s[0];i++)
{
Ra[i]=r[i];
}
len=i;
Ra[len]='\0'; //左中
for(i=0;i<len;i++)
{
La[i]=s[i+1];
}
La[len]='\0'; //左前
for(i=len+1;i<strlen(r);i++)
{
Rb[i-len-1]=r[i];
}
Rb[i-len-1]='\0';
for(i=len+1;i<strlen(s);i++)
{
Lb[i-len-1]=s[i];
}
Lb[i-len-1]='\0';
Pre_In_order(&(*t)->lchild,La,Ra);
Pre_In_order(&(*t)->rchild,Lb,Rb);
}
else
{
*t=NULL;
}
} int main()
{
Bintree t;
char pre[30]="ABCDEF",in[30]="CBAEDF";//测试数据
printf("输入前序遍历序列:");
scanf("%s",pre);
printf("输入中序遍历序列:");
scanf("%s",in);
Pre_In_order(&t,pre,in);
Posorder1(t);
} #include<stdio.h>
#include<malloc.h>
typedef struct node{
int data;
struct node *lchild,*rchild,*next;
}hufnode; typedef hufnode
*linkhuf;
/****************************************************/
/* huffman树 */
/****************************************************/
linkhuf Creat_Node(int n) //创建一单链表
{
linkhuf head,pre,p;
int x;
head=NULL;
while(n--)
{
scanf("%d",&x);
p=(linkhuf)malloc(sizeof(hufnode));
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(NULL==head)
{
head=p;
pre=head;
}
else
{
p->next=pre->next;
pre->next=p;
pre=pre->next;
}
}
return head;
}
linkhuf insert(linkhuf root , linkhuf s)//将结点S插入到有序Huffman root中。
{
linkhuf p1,p2;
if(NULL == root ) root=s;
else
{
p1=NULL;
p2=root;
while(p2&&p2->data<s->data)
{
p1=p2;
p2=p2->next;
}
s->next=p2;
if(NULL==p1)
{
root=s;
}
else
{
p1->next=s;
}
}
return root;
} void Preorder1(linkhuf t)
{
if(t!=NULL)
{
printf("%-6d",t->data);
Preorder1(t->lchild);
Preorder1(t->rchild);
}
}
void creathuffman(linkhuf *root)//构造Huffman树。
{
linkhuf s, rl,rr;
while(*root && (*root)->next)
{
rl=*root;
rr=(*root)->next;
*root=rr->next;
s=(linkhuf)malloc(sizeof(hufnode));
s->next=NULL;
s->data=rl->data+rr->data;
s->lchild=rl;
s->rchild=rr;
rl->next=rr->next=NULL;
*root=insert(*root,s);
}
} int main()
{
linkhuf root;
int n;
scanf("%d",&n);
root=Creat_Node(n);
creathuffman(&root);
Preorder1(root);
printf("\n");
return 0;
} /************************************************************/
/* 按层次顺序建立一棵二叉树 */
/************************************************************/
#include"Bintree.h"
Bintree Level_Creat()
{
Bintree root,p,s;
queue node;
node.front=node.rear=0;
char ch;
ch=getchar();
if(ch==' ')
{
return NULL;
}
root=(Binnode*)malloc(sizeof(Binnode)); //生成根结点
root->data=ch;
node.data[node.rear++]=root; //用队列实现层次遍历
while(node.front<node.rear)
{
p=node.data[node.front++];
ch=getchar(); //为了简化操作，分别对左右子结点进行赋值。
if(ch!=' ')//子树不空则进队列进行扩充。下同
{
s=(Binnode*)malloc(sizeof(Binnode));
s->data=ch;
p->lchild=s;
node.data[node.rear++]=s;
}
else
{
p->lchild=NULL;
}
ch=getchar();
if(ch!=' ')
{
s=(Binnode*)malloc(sizeof(Binnode));
s->data=ch;
p->rchild=s;
node.data[node.rear++]=s;
}
else
{
p->rchild=NULL;
}
}
return root;
}
int main()
{
Bintree root;
root=Level_Creat();
Inorder1(root);//测试，中序遍历
return 0;
}
