大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > 算法技巧 > 数据结构与算法基本程序合集

数据结构与算法基本程序合集(4)

关键词:数据结构算法基本程序  阅读(2773) 赞(55)

[摘要]本文是数据结构与算法基本程序合集,与大家分享。
五、树(二叉树)及其操作
//二叉排序树
 
#include<stdio.h>
#include<stdlib.h>
 
typedef struct tnode
{
    int num;
    struct tnode *Lchild,*Rchild;
}Tnode,*Btree;
 
typedef struct snode
{
    int num;
    Btree r;
    struct snode *next;
}Snode,*stack;
 
Btree root;
 
void describe_tree()    //交互式显示哈夫曼树
{
    Btree t;
    stack s,top,temp;
    int choice;
 
    s=(stack)malloc(sizeof(Snode));
    s->num=0;
    s->next=NULL;
    s->r=NULL;
    top=s;
    
    t=root;//t指向哈夫曼树的根结点
 
    temp=(stack)malloc(sizeof(Snode));    //分配新栈结点    
    temp->num=t->num;
    temp->next=top;        //结点入栈
    temp->r=t;    //将当前二叉树结点指针给栈顶结点
    top=temp;        //修改栈顶指针
 
    printf("输入1往左子树,输入2往右子树,输入3返回父结点,其它输入退出程序\n");
    scanf("%d",&choice);
    getchar();
    
    while(choice==1||choice==2||choice==3)
    {
        if(choice==1)        //往左子树
        {
            if(t->Lchild!=NULL)
            {
                t=t->Lchild;
                temp=(stack)malloc(sizeof(Snode));    //分配新栈结点
                //新结点入栈    
                temp->num=t->num;
                temp->next=top;        //结点入栈
                temp->r=t;    //将当前二叉树结点指针给栈顶结点
                top=temp;        //修改栈顶指针
                printf("值为%d\n",t->num);
            }
            else    //左子树不存在,当前结点已经是叶子结点
                printf("无左孩子!\n");    
        }
        else if(choice==2)    //往右子树
        {
            if(t->Rchild!=NULL)
            {
                t=t->Rchild;
                temp=(stack)malloc(sizeof(Snode));    //分配新栈结点
                //新结点入栈
                temp->num=t->num;
                temp->next=top;        //结点入栈
                temp->r=t;    //将当前二叉树结点指针给栈顶结点
                top=temp;        //修改栈顶指针
                printf("值为%d\n",t->num);
            }
            else    //右子树不存在,当前结点已经是叶子结点
                printf("无右孩子!\n");
        }
        else if(choice==3)    //返回父结点
        {
            if(top->next!=s)    //栈非空
            {
                top=top->next;
                t=top->r;
                printf("值为%d\n",t->num);
            }
            else
                printf("已经在根结点了!\n");
        }
 
        scanf("%d",&choice);
        getchar();
    }
}
 
void inorder(Btree r)        //中序递归遍历
{
    if(r!=NULL)
    {
        inorder(r->Lchild);
        printf(" %d <",r->num);
        inorder(r->Rchild);
    }
}
 
main()
{
    int array[100],n=0,i,choice;
    Btree p,q;
 
    for(i=0;i<100;i++)
        array[i]=0;
 
    printf("输入若干个整数,结束用\"0\"表示\n");
    scanf("%d",&array[n++]);
    getchar();
    while(array[n-1]!=0)
        scanf("%d",&array[n++]);
 
    n=0;
    if(array[n]!=0)
    {
        root=(Btree)malloc(sizeof(Tnode));        //建立二叉排序树的根结点
        root->num=array[n];
        root->Lchild=NULL;
        root->Rchild=NULL;
        n++;
    }
    else
        exit(0);
 
    while(array[n]!=0)
    {
        p=(Btree)malloc(sizeof(Tnode));        //依次给每个整数分配结点
        p->num=array[n];
        p->Lchild=NULL;
        p->Rchild=NULL;
 
        //分配完结点后,要插入到二叉树中合适的位置
        q=root;        //q初始化到根结点
        while(q!=NULL)
        {
            if(q->num<p->num)    //若新结点的值大于根结点的值,则往右子树
            {
                if(q->Rchild!=NULL)        //当前结点有右孩子,则指针移向右孩子继续比较
                    q=q->Rchild;
                else        //当前结点没有右孩子,则新结点为当前结点的右孩子
                {
                    q->Rchild=p;
                    break;
                }
            }
            else
            {
                if(q->Lchild!=NULL)        //当前结点有左孩子,则指针移向左孩子继续比较
                    q=q->Lchild;
                else        //当前结点没有左孩子,则新结点为当前结点的左孩子
                {
                    q->Lchild=p;
                    break;
                }
            }
        }
        n++;
    }
    
    
    //建立二叉排序树完毕
    //对其进行中序遍历
    
    printf("\n哈夫曼树构造完成,是否查看哈夫曼树,输入1查看,其它输入跳过");
    scanf("%d",&choice);
    getchar();
    if(choice==1)
        describe_tree();
    
    inorder(root);
    printf("\n");
}


相关评论