大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > 算法技巧 > 二叉树基本操作的程序实现

二叉树基本操作的程序实现(5)

关键词:二叉树C语言  阅读(3131) 赞(31)

[摘要]本文是二叉树基本操作的程序实现,与大家分享。

#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;
}



相关评论