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

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

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

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

//Bintree.h
#include<stdio.h>
#include<malloc.h>
typedef struct Binnode{//二叉树结点结构体
    char data;
    struct Binnode *lchild;
    struct Binnode *rchild;
  };
typedef Binnode *Bintree ;
 
typedef struct stack{ //二叉树结点栈
     Bintree data[100];
    int flag[100];
    int top;
  };
 
typedef struct queue{ //二叉树结点队列
    Bintree data[30];
    int front;
    int rear;
  };
 

  
/*******************************************/
/*          按照前序遍历建立二叉树         */
/*******************************************/
 
void Creat_Bintree(Bintree *root)
{
    char ch;
    if((ch=getchar())==' ')
    {
        *root=NULL;
 
    }
    else
    {
        *root=(Binnode*)malloc(sizeof(Binnode));
        (*root)->data=ch;
        Creat_Bintree(&(*root)->lchild);
        Creat_Bintree(&(*root)->rchild);
    }
}
 
/*******************************************/
/*          按照前序递归遍历二叉树         */
/*******************************************/
 
void Preorder1(Bintree t)
{
    if(t!=NULL)
    {
        printf("%c",t->data);
        Preorder1(t->lchild);
        Preorder1(t->rchild);
    }
}
 

/*******************************************/
/*          按照中序递归遍历二叉树         */
/*******************************************/
 
void Inorder1(Bintree t)
{
    if(t!=NULL)
    {
        Inorder1(t->lchild);
        printf("%c",t->data);
        Inorder1(t->rchild);
    }
}
 
/*******************************************/
/*          按照后序递归遍历二叉树         */
/*******************************************/
 
void Posorder1(Bintree t)
{
    if(t!=NULL)
    {
        Posorder1(t->lchild);
        Posorder1(t->rchild);
        printf("%c",t->data);
    }
}
/*******************************************/
/*          按照前序非递归遍历二叉树         */
/*******************************************/
 
void Preorder2(Bintree t)
{
    Bintree pre=t;
    stack s;
    s.top=0;
    printf("输出前序遍历序列:");
    while(pre||s.top>0)
    {
        if(pre)
        {
            printf("%c",pre->data);
            s.data[s.top++]=pre;
            pre=pre->lchild;
        }
        else
        {
            pre=s.data[--s.top]->rchild;
        }
    }
    printf("\n\n");
}
 
/*******************************************/
/*          按照中序非递归遍历二叉树         */
/*******************************************/
 
void Inorder2(Bintree t)
{
    Bintree pre=t;
    stack s;
    s.top=0;
     printf("输出中序遍历序列:");
    while(pre||s.top>0)
    {
        if(pre)
        {
            s.data[s.top++]=pre;
            pre=pre->lchild;
        }
        else
        {
            pre=s.data[--s.top];
            printf("%c",pre->data);
            pre=pre->rchild;
        }
    }
    printf("\n\n");
}
 
/*******************************************/
/*        按照后序非递归遍历二叉树         */
/*******************************************/
 
void Posorder2(Bintree t)
{
    stack s;
    s.top=-1;
    printf("输出后序遍历序列:");
    while(t!=NULL||s.top!=-1)
    {
        while(t)
        {
            s.top++;
            s.flag[s.top]=0;
            s.data[s.top]=t;
            t=t->lchild;
           
        }
        while(s.top>=0&&s.flag[s.top]==1)
        {
            t=s.data[s.top];
            printf("%c",t->data);
            s.top--;
        }
        if(s.top>=0)
        {
            t=s.data[s.top];
            s.flag[s.top]=1;
            t=t->rchild;
        }
        else
        {
            t=NULL;
        }
    }
    printf("\n\n");
}
 

/*******************************************/
/*           按照层次遍历二叉树            */
/*******************************************/
void Levelorder(Bintree t)
{
    queue q;
    q.data[0]=t;
    q.front=0;q.rear=1;
    printf("层次遍历二叉树结果:");
    while(q.front<q.rear)
    {
        if(q.data[q.front])
        {
            printf("%c",q.data[q.front]->data);
            q.data[q.rear++]=q.data[q.front]->lchild;
            q.data[q.rear++]=q.data[q.front]->rchild;
            q.front++;
        }
        else
        {
            q.front++;
        }
    }
    printf("\n\n");
}
«上一页1234...6下一页»


相关评论