这么多天了，搜索二叉树才搞定了最基础的部分（蹉跎了好些岁月，终于搞定了四种遍历） - C语言论坛

第 21 楼

得分:0

回复 20楼九转星河

嗯……找时间吧。

还是那个字……忙。

09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。

第 22 楼

得分:0

回复 21楼 renkejun1942

其实二叉树删除节点不简单~你用的是更改节点的值而不是完全通过改变节点指针~你那个真正删除节点并不是查找到的节点而是右子树最小值那个替身~树遍历不可逆这是个难点~如果树结构一变则删除节点就要变得麻烦了~或许像书生牛犊说的那样用void*指针提高其通用性~不然一个树结构体里面有N多个元素时要逐个逐个改变值域很麻烦~

PS:曾经写了一个完全改变指针指向的删除节点感觉比链表排序还复杂~记得用了5个指针变量才完成任务~似乎我那样写二叉查找树的删除节点的复杂度和AVL树删除节点的复杂度差不多~那块弄了很久~

[此贴子已经被作者于2017-5-11 00:28编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 23 楼

得分:0

回复 22楼九转星河

如果通过修改节点指针来删除，那么假设有下面这棵树，删除节点10，指针应该怎么调整？我想不到答案。

                10
            5         15
       4        6   11     16

另外一点，为什么你会觉得删除只有一种方法呢？惰性删除是一种删除，寻找替换，永远删除叶节点或只有一个子字节的节点，就不是删除了呢？

[此贴子已经被作者于2017-5-11 05:49编辑过]

09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。

第 24 楼

得分:0

回复 23楼 renkejun1942

~~这样啊~记得注释没有修改value的值~难怪删除会有bug~~行得通就好~不过你这种方法应对AVL树就没那么好玩了~~

PS:方法是有的~删除难点在于要找到要删除的父节点~这个比较麻烦~可以试试做个双向树结构~似乎没有人怎么做过~而且上网搜了搜删除似乎看到都是像你那样寻找替身的~只能说我那个注释有点奇葩~

[此贴子已经被作者于2017-5-11 06:18编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 25 楼

得分:0

回复 24楼九转星河

那说明很多人看过我看的书。

《C和指针》和《算法》提供了这个方法。
《数据结构与算法分析》提供了一个递归版本的删除函数，正是对这个递归函数的研究，我写出了迭代版本。

[此贴子已经被作者于2017-5-11 18:32编辑过]

09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。

第 26 楼

得分:0

回复 25楼 renkejun1942

看看这个删除版本~感觉写得很复杂的样子~~不过是通过纯交换指针节点来进行删除操作的~还用了双向树来简化删除操作~

程序代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<assert.h>
#define LEN sizeof(TREE)

typedef int ElemType;

typedef struct TREE
{
    ElemType Value;
    struct TREE* left;
    struct TREE* right;
    struct TREE* prior;
}TREE,*PTREE;

void Init(PTREE* t);

void Creat_Node(void** t,size_t size);

int Insert_Value(PTREE* t,ElemType Value);
void Insert_Node(PTREE t,ElemType Value);

void Pre_Order_Traversal(PTREE t); 
void In_Order_Traversal(PTREE t);  
void Post_Order_Traversal(PTREE t);

PTREE Find_Min(PTREE t);
PTREE Find_Max(PTREE t);

PTREE Find_Node(PTREE t,ElemType Value);

int Del_Node(PTREE* t,ElemType Value);
int Del_Root(PTREE* t);
int Del_Left(PTREE* t);
int Del_Right(PTREE* t);
int Del_Double(PTREE* t);

int Visit(PTREE t);

void Free_Tree(PTREE* t);

void Free_Node(void** t);

int main()
{
    PTREE t=NULL;
    PTREE tm=NULL;
    int a=0;

    Init(&t);

    Pre_Order_Traversal(t);
    puts("");

    In_Order_Traversal(t);
       puts("");

    Post_Order_Traversal(t);
       puts("");


    printf("请输入要删除的节点:");
    while (    scanf("%d",&a)!=EOF)
    {
        Del_Node(&t,a);

        Pre_Order_Traversal(t);
        puts("");

         In_Order_Traversal(t);
        puts("");

        Post_Order_Traversal(t);
        puts("");

        printf("请输入要删除的节点:");
    }


    Free_Tree(&t);

    return 0;
}

void Init(PTREE* t)
{
    ElemType Value=0;

    int i=10;

    srand((unsigned)time(NULL));
    while (i--)
    {
        Value=rand()%100;
        Insert_Value(t,Value);
    }
}

void Creat_Node(void** t,size_t size)
{
    *t=malloc(size);
    assert(*t!=NULL);

    memset(*t,0,size);
}

int Insert_Value(PTREE* t,ElemType Value)
{
    PTREE* pt=t;
    PTREE s=NULL;


    while (*pt!=NULL)
        if (Value<(*pt)->Value)
        {
            s=*pt;
            pt=&((*pt)->left);
        }
        else if (Value>(*pt)->Value)
        {
            s=*pt;
            pt=&((*pt)->right);
        }
        else 
            return 0;

    Creat_Node(pt,LEN);

    (*pt)->prior=s;
    Insert_Node(*pt,Value);

    return 1;
}

void Insert_Node(PTREE t,ElemType Value)
{
    if (t==NULL)
        return ;

    t->Value=Value;
}

int Visit(PTREE t)
{
    if (t==NULL)
        return 0;

    printf("%-4d",t->Value);

    return 1;
}

void Pre_Order_Traversal(PTREE t)
{
    if (t==NULL)
        return ;

    Visit(t);

    Pre_Order_Traversal(t->left);
    Pre_Order_Traversal(t->right);
}

void In_Order_Traversal(PTREE t)
{
    if (t==NULL)
        return ;

    In_Order_Traversal(t->left);

    Visit(t);

    In_Order_Traversal(t->right);
}

void Post_Order_Traversal(PTREE t)
{
    if (t==NULL)
        return ;

    Post_Order_Traversal(t->left);
    Post_Order_Traversal(t->right);

    Visit(t);
}

PTREE Find_Min(PTREE t)
{
    if (t==NULL)
        return t;

    while (t->left!=NULL)
        t=t->left;

    return t;
}

PTREE Find_Max(PTREE t)
{
    if (t==NULL)
        return t;

    while (t->right!=NULL)
        t=t->right;

    return t;
}

PTREE Find_Node(PTREE t,ElemType Value)
{
    if (t==NULL)
        return t;

    while (t!=NULL)
        if (Value<t->Value)
            t=t->left;
        else if (Value>t->Value)
            t=t->right;
        else 
            return t;

    return t;
}

int Del_Node(PTREE* t,ElemType Value)
{
    PTREE pt=*t;

    if ((pt=Find_Node(*t,Value))==NULL)
        return 0;

    if (pt==*t)
        Del_Root(t);
    else if (pt->prior->left==pt)
        Del_Left(&pt);
    else
        Del_Right(&pt);

    return 1;
}

int Del_Root(PTREE* t)
{
    PTREE ps=NULL;

    if ((*t)->left==NULL&&(*t)->right==NULL)
    {
        Free_Node(t);
        return 1;
    }

    if ((*t)->left!=NULL&&(*t)->right==NULL)
    {
        ps=(*t)->left;
        ps->prior=NULL;

        Free_Node(t);

        *t=ps;

        return 1;
    }

    if ((*t)->right!=NULL&&(*t)->left==NULL)
    {
        ps=(*t)->right;
        ps->prior=NULL;

        Free_Node(t);

        *t=ps;

        return 1;
    }

    ps=Find_Min((*t)->right);
    ps->left=(*t)->left;
    (*t)->left->prior=ps;

    if (ps->prior==*t)
    {
        ps->prior=NULL;
        Free_Node(t);

        *t=ps;

        return 1;
    }

    ps->prior->left=ps->right;

    if (ps->right!=NULL)
        ps->right->prior=ps->prior;

    ps->right=(*t)->right;
    (*t)->right->prior=ps;

    ps->prior=NULL;

    Free_Node(t);

    *t=ps;

    return 1;
}

int Del_Left(PTREE* t)
{
    PTREE pt=(*t)->prior;

    if ((*t)->left==NULL&&(*t)->right==NULL)
    {
        pt->left=NULL;
        Free_Node(t);

        return 1;
    }

    if ((*t)->left==NULL)
    {
        pt->left=(*t)->right;
        (*t)->right->prior=pt;
        Free_Node(t);

        return 1;
    }

    if ((*t)->right==NULL)
    {
        pt->left=(*t)->left;
        (*t)->left->prior=pt;
        Free_Node(t);

        return 1;
    }
    Del_Double(t);

    return 1;

}
int Del_Right(PTREE* t)
{
    PTREE pt=(*t)->prior;

    if ((*t)->left==NULL&&(*t)->right==NULL)
    {
        pt->right=NULL;
        Free_Node(t);

        return 1;
    }

    if ((*t)->left==NULL)
    {
        pt->right=(*t)->right;
        (*t)->right->prior=pt;
        Free_Node(t);

        return 1;
    }

    if ((*t)->right==NULL)
    {
        pt->right=(*t)->left;
        (*t)->left->prior=pt;
        Free_Node(t);

        return 1;
    }

    Del_Double(t);

    return 1;
}

int Del_Double(PTREE* t)
{
    PTREE ps=Find_Min((*t)->right);

    if ((*t)->prior->left==*t)
        (*t)->prior->left=ps;
    else 
        (*t)->prior->right=ps;

    ps->left=(*t)->left;
    (*t)->left->prior=ps;

    if (ps->prior==*t)
    {
        ps->prior=(*t)->prior;
        Free_Node(t);

        return 1;
    }

    ps->prior->left=ps->right;

    if (ps->right!=NULL)
        ps->right->prior=ps->prior;

    ps->right=(*t)->right;
    (*t)->right->prior=ps;

    ps->prior=(*t)->prior;

    Free_Node(t);

    return 1;
}

void Free_Tree(PTREE* t)
{
    if (*t==NULL)
        return ;

    Free_Tree(&(*t)->left);
    Free_Tree(&(*t)->right);

    Free_Node(t);

    *t=NULL;
}

void Free_Node(void** t)
{
    if (*t==NULL)
        return ;

    free(*t);

    *t=NULL;
}

PS:其实那个创建节点和删除节点函数几乎是万能的~用void*指针方便很多~等考完试有时间我来弄个通用链表的快速排序和AVL树玩玩~现在还不知道我到底有没有那等精力去实现~~~

[此贴子已经被作者于2017-5-12 04:41编辑过]

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 27 楼

得分:0

PS:原来把根节点加进树里面挺好玩的~动手改改删除时可以不用考虑根节点了~~~

程序代码：

Insert_Value(&t,INT_MAX);

int Visit(PTREE t)
{
    if (t==NULL||t->prior==NULL)
        return 0;

    printf("%-4d",t->Value);

    return 1;
}

看看这样改改是不是可以把Del_Root函数去掉~~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 28 楼

得分:0

回复 26楼九转星河

晚点再说，我先搞定我自己的先。
不着急。

别习惯性熬夜，睡觉去吧。上班去了，Bye。

09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。

第 29 楼

得分:0

回复 28楼 renkejun1942

看来我那个自己弄的代码还是和主流的有差距啊~建议去脑补一下线索二叉树~那是个好东东~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 30 楼

得分:0

回复 29楼九转星河

没什么主流和非主流，达成目的就行。
这是我学习编程后获得的认识。

四种遍历的迭代版本算是搞定了。
中序遍历找时间来重写。

09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。