Chinaunix首页 | 论坛 | 博客
  • 博客访问: 6362441
  • 博文数量: 579
  • 博客积分: 1548
  • 博客等级: 上尉
  • 技术积分: 16634
  • 用 户 组: 普通用户
  • 注册时间: 2012-12-12 15:29
个人简介

http://www.csdn.net/ http://www.arm.com/zh/ https://www.kernel.org/ http://www.linuxpk.com/ http://www.51develop.net/ http://linux.chinaitlab.com/ http://www.embeddedlinux.org.cn http://bbs.pediy.com/

文章分类

全部博文(579)

文章存档

2018年(18)

2015年(91)

2014年(159)

2013年(231)

2012年(80)

分类: C/C++

2012-12-14 16:38:47

/*creat a bittree*/
#include "stdlib.h"
#include "stdio.h"
typedef struct BiTNode
{
  int data;
  struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;


BiTNode* getnode()
{
  BiTNode* p;
  p = (BiTNode*)malloc(sizeof(BiTNode));
  p->lchild = NULL;
  p->rchild = NULL;
  return p;
}

int *Create_array(int *q)       //创建数组
{
    int n,i;

    printf("please input the number:");
    scanf("%d",&n);

    for(i=0;i    {   printf("please input the data:");
        scanf("%d",q++);
    }
    *q='\0';
    return q;
}

void insert(BiTNode **T,BiTNode *S)    //插入
{
    if(*T==NULL)*T=S;
    else if((*T)->data>S->data)
        insert(&(*T)->lchild,S);
    else if((*T)->data<=S->data)
        insert(&(*T)->rchild,S);
}

BiTNode **CreateBiTree(BiTNode **T,int *w)  //创建二叉排序树
{
    BiTNode *S;
    *T=NULL;

    while(*w!='\0')
    {
        S=getnode();
        S->data=*w;
        insert(T,S);
        w++;
    }
    return T;
}

BiTree deleteBST(BiTree tptr)//删除
{
    BiTree p,tmp,parent=NULL;
    p=tptr;
 int key;
 printf("please input the data to delete:");
 scanf("%d",&key);
    while(p)
    {
        if(p->data==key)
            break;
        parent=p;
        p=(keydata)?p->lchild:p->rchild;
    }
    if(!p) return NULL;
    tmp=p;
    if(!p->rchild&&!p->lchild) /*p的左右子树都为空*/
    {
        if(!parent)    //要删根,须修改根指针
            tptr=NULL;
        else if(p==parent->rchild)
            parent->rchild=NULL;
        else
            parent->lchild=NULL;
        free(p);
    }
    else if(!p->rchild)   //p的右子树为空,则重接p的左子树
    {
        p=p->lchild;
        if(!parent)    //要删根,须修改根指针
            tptr=p;
        else if(tmp==parent->lchild)
            parent->lchild=p;
        else
            parent->rchild=p;
        free(tmp);
    }
    else if(!p->lchild)    //的左子树为空,则重接p的左子树
    {
        p=p->rchild;
        if(!parent)    //要删根,须修改根指针
            tptr=p;
        else if(tmp==parent->lchild)
            parent->lchild=p;
        else
            parent->rchild=p;
        free(tmp);
    }
    else if(p->rchild&&p->lchild)   //p有左子树和右子树,用p的后继覆盖p然后删去后继
    {                       //另有方法:用p的前驱覆盖p然后删去前驱||合并p的左右子树 
        parent=p;           //由于用覆盖法删根,则不必特殊考虑删根
        p=p->rchild;
        while(p->lchild)
        {
            parent=p;
            p=p->lchild;
        }
        tmp->data=p->data;
        if(p==parent->lchild)
            parent->lchild=NULL;
        else
            parent->rchild=NULL;
        free(p);
    }
    return tptr;
}


int Inorder(BiTree T)
{
    if(T!=NULL)
    {
        Inorder(T->lchild);
        printf("%d ",T->data);
        Inorder(T->rchild);
    }
    else
     return 0;

}


void main(void)
{

  BiTNode **T;
  int n;
  int *s,*q,*w;
  s=(int *)malloc(100*sizeof(int));
  T=(BiTNode **)malloc(100*sizeof(BiTNode));
  q=s;
  while(1)
  {
    printf("please selcet the function :\n");
    printf("0 for exit\n");
    printf("1 for input the data to insert to the binary tree\n");
    printf("2 for rmmod the data from the binary tree\n");
    printf("3 for Inorder the binary tree\n");
    printf("please select:");
    scanf("%d",&n);
    if(n==0)
        break;

    if(n==1)
    {   w=s;
        q=Create_array(q);
        T=CreateBiTree(T,w);
        if(n==2)
    {
        deleteBST(*T);
    }

    if(n==3)
    {
        Inorder(*T);
        printf("\n");
    }

  }
 
  system("pause");

}

阅读(1289) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~