| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 608 人关注过本帖
标题:数据结构c语言问题,在删除树节点出错,求帮助啊
只看楼主 加入收藏
战斗!立
Rank: 2
等 级:论坛游民
帖 子:29
专家分:43
注 册:2011-11-26
结帖率:100%
收藏
 问题点数:0 回复次数:1 
数据结构c语言问题,在删除树节点出错,求帮助啊
程序代码:
#include<stdio.h>
#include<stdlib.h>

#define N 10

typedef struct tree{
    int data;
    struct tree *left;
    struct tree *right;
}Tree;

typedef struct queue{
    Tree *store[N];
    int f;
    int r;
}Queue;

void init_queue(Queue *q)
{
    q->f=0;
    q->r=0;
}

void inqueue(Queue *s,Tree *value)
{
    if((s->r+1)%(N)==s->f)
    {
        printf("error\n");
        return;
    }
    s->store[s->r]=value;
    s->r=(s->r+1)%(N);
}

Tree *dequeue(Queue *s)
{
    Tree *temp;
    if(s->r==s->f)    return NULL;
    temp=s->store[s->f];
    s->f=(s->f+1)%(N);
    return temp;
    
}

void init_array(int a[],int n)
{
    int i;
    for(i=0;i<n;i++)
        a[i]=i;
}

Tree *init_tree(int value)
{
    Tree *newnode=(Tree *)malloc(sizeof(Tree));
    newnode->data=value;
    newnode->right=NULL;
    newnode->left=NULL;
    return newnode;
}

int is_empty(Queue *q)
{
    if(q->f==q->r)    return 1;
    else    return 0;
}
/*void insert_tree(Tree *root,int value)
{
    Tree *subtree=(Tree *)malloc(sizeof(Tree));
    subtree->data=value;
    subtree->right=NULL;
    subtree->left=NULL;
    while(root->right&&root->data<value)
        root=root->right;
    while(root->left&&root->data>value)
        root=root->left;
    if(root->data<value)    root->right=subtree;
    if(root->data>value)    root->left=subtree;
    if(root->data=value)    return;    
}*/
void insert_tree(Tree *root,int value)
{
    while(root)
    {
        if(root->data==value)    return;
        if(root->data>value)
        {
            if(root->left)    root=root->left;
            else
            {    
                Tree *t=init_tree(value);
                root->left=t;
                return;
            }
        }
        else//(root->data<value)
        {
            if(root->right)    root=root->right;
            else    
            {
                Tree *t=init_tree(value);
                root->right=t;
                return;
            }
        }
    }
}

void inorder(Tree *root)
{
    if(root==NULL)    return;
    inorder(root->left);
    printf("%d\n",root->data);
    inorder(root->right);
}

int tree_lenght(Tree *root)
{
    int lenght;
    if(root==NULL) return    0;
    else
    {
        int left_lenght=tree_lenght(root->left);
        int right_lenght=tree_lenght(root->right);
        lenght=((left_lenght>=right_lenght)?left_lenght:right_lenght)+1;
        return lenght;
    }
    
}

void levelorder(Tree *root)
{
    Tree *t;
    Queue *q=(Queue *)malloc(sizeof(Queue));
    init_queue(q);
    inqueue(q,root);
    while(q->f!=q->r)
    {
        t=dequeue(q);
        printf("%d\n",t->data);
        if(t->left)        inqueue(q,t->left);
        if(t->right)    inqueue(q,t->right);
    }
}

Tree *search_tree(Tree *root,int value)
{
    if(root==NULL)    return    NULL;
    if(root->data==value)    return root;
    if(root->data>value)    return search_tree(root->left,value);
    else    return search_tree(root->right,value);
}

Tree *search_max(Tree *root)
{
    Tree *temp;
    if(!root->right&&!root->left)    return NULL;
    if(!root->right&&root->left)
    {
        temp=root->left;
        root->left=NULL;
        return temp;
    }
    if(root->right&&!root->left)
    {
        temp=root->right;
        root->right=NULL;
        return temp;
    }
    if(root->right&&root->left&&root->left->right==NULL)
    {
        temp=root->right;
        root->right=NULL;
        return temp;
    }
    root=root->left;
    while(root->right->right)
        root=root->right;
    temp=root->right;
    root->right=NULL;
    return temp;
}

Tree *search(Tree *root,int value)
{
    if(root==NULL)    return NULL;
    if(root->data==NULL)    return NULL;
    while(1)
    {
        if(root->data>value)
        {
            if(root->left==NULL)    return NULL;
            else if(root->left->data==value)
                return root;
            else
                root=root->left;
        }
        if(root->data<value)
        {
            if(root->right==NULL)    return NULL;
            else if(root->right->data==value)
                return root;
            else
                root=root->right;
        }
    }
}

int extent(Tree *root)
{
    if(!root->right&&root->left)
        return 0;
    if(root->right&&!root->left)
        return 1;
    if(root->right&&root->left)
        return 2;
}

void delet_tree(Tree *root,int value)
{
    Tree *s;
    Tree *node;
    Tree *temp;
    if(!search(root,value))    return ;
    node=search(root,value);
    
    if(node->left->data==value)
    {
        temp=search_max(node->left);
        if(!temp)    
        {
            s=node->left;
            node->left=NULL;
            free(s);
        }
        else
        {
            s=node->left;
            node->left=temp;
            if(extent(s)==0)
            {
                temp->left=s->left;
            }
            if(extent(s)==1)
            {
                temp->right=s->right;
            }
            if(extent(s)==2)
            {
                temp->left=s->left;
                temp->right=s->right;
            }
            free(s);
        }
    }
    if(node->right->data==value)
    {
        temp=search_max(node->right);
        if(!temp)    
        {
            s=node->right;
            node->right=NULL;
            free(s);
        }
        else
        {
            s=node->right;
            node->right=temp;
            if(extent(s)==0)
            {
                temp->right=s->right;
            }
            if(extent(s)==1)
            {
                temp->left=s->left;
            }
            if(extent(s)==2)
            {
                temp->left=s->left;
                temp->right=s->right;
            }
            free(s);
        }
    }
    
    
}

void main()
{
    int i;
    Tree *root=(Tree *)malloc(sizeof(Tree));
    root->data=N/2;
    root->right=NULL;
    root->left=NULL;
    
    for(i=0;i<N;i++)
        insert_tree(root,random()%N);
    //levelorder(root);
    delet_tree(root,7);
    levelorder(root);
}
搜索更多相关主题的帖子: c语言 store 
2011-12-19 21:47
xuxiong517
Rank: 2
等 级:论坛游民
帖 子:35
专家分:29
注 册:2011-11-1
收藏
得分:0 
哥你放上来这程序太长了,要是你看到这么长的会有兴趣看吗??
2012-01-01 22:39
快速回复:数据结构c语言问题,在删除树节点出错,求帮助啊
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029668 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved