| 网站首页 | 技术文章 | 下载频道 | 博客 | 编程论坛 |
 
| 技术教程首页 | 开发语言 | WEB开发 | .NET技术 | 数据库 | 操作系统 | 网页制作 |
 
 
您现在的位置: 编程中国 >> 技术教程 >> 开发语言 >> 数据结构 >> 正文
  ►  二叉树基本操作的程序实现
二叉树基本操作的程序实现
作者:nuciewth    阅读人次:……    文章来源:本站原创    发布时间:2007/6/13    网友评论()条
 

原帖及讨论:http://bbs.bccn.net/thread-137061-1-1.html

//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");
}

[1] [2] [3] [4] [5] [6] 下一页

 

 
文章录入:静夜思    责任编辑:静夜思 
  • 上一篇文章:

  • 下一篇文章:

  •  
    相关文章
    原创地带
    24小时热门帖子