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

楼主

已结贴√ 问题点数：20 回复次数：43

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

这么多天了，搜索二叉树才搞定了最基础的部分。

程序代码：

#include <stdio.h>
#include "STree.h"
#include <stdlib.h>
#include <time.h>

int
main( void )
{
    Tree Root;
    int a[ 20 ];
    int i;

    srand( ( unsigned int )time( NULL ) );
    Root = NULL;

    for( i = 0; 20 > i; ++i )
    {
        a[ i ] = rand() % 10000;
        Insert( &Root, a[ i ] );
    }
    Print( Root );//测试用函数
    printf( "\n" );
    PostorderTraversal( Root );
    printf( "\n" );
//    PrevTraversal( Root );

for( i = 0; 20 > i; ++i ){
    printf( "\n" );
    printf( "被删除的节点为%d\n", a[ i ] );
    DeleteNode( &Root, a[ i ] );
    //PrevTraversal( Root );
    //printf( "\n" );
    //InorderTraversal( Root );
    //printf( "\n" );
    PostorderTraversal( Root );
    printf( "\n" );
    //LevelTraversal( Root );
    //printf( "\n" );
}

    return 0;
}

}

程序代码：

#ifndef _S_TREE_H_
#define _S_TREE_H_
#define T Tree
typedef struct T *T;

int
Insert( T *TreePP, int Value );

void
DeleteNode( T *TreeP, int Value );

T
FindMin( T TreeP );

T
FindMax( T TreeP );

T
Find( T TreeP, int value );

void
Print( T TreeP );//测试用函数，可删除。

void
PrevTraversal( T TreeP );

void
InorderTraversal( T TreeP );

void
PostorderTraversal( T TreeP );

void
LevelTraversal( T TreeP );

struct T{
    int Element;
    T Left;
    T Right;
};

#undef T
#endif

程序代码：

#include "STree.h"
#include <stdlib.h>
#include <stdio.h>
#define T Tree
enum{ OK = 0, NOT };


int
Insert( T *TreePP, int Value )
{
    T Next;
    T NewCell;

    while( NULL != ( Next = *TreePP ) )
    {
        if( Value > Next->Element )
            TreePP = &Next->Right;
        else if( Value < Next->Element )
            TreePP = &Next->Left;
        else
            return NOT;
    }

    NewCell = ( T )malloc( sizeof( struct T ) );
    if( NULL != NewCell )
    {
        NewCell->Left = NULL;
        NewCell->Right = NULL;
        NewCell->Element = Value;
        *TreePP = NewCell;
        return OK;
    }
    else
        return NOT;
}


T
FindMin( T TreeP )
{
    while( NULL != TreeP->Left )
        TreeP = TreeP->Left;

    return TreeP;
}


T
FindMax( T TreeP )
{
    while( NULL != TreeP->Right )
        TreeP = TreeP->Right;
    
    return TreeP;
}


T
Find( T TreeP, int Value )
{
    while( NULL != TreeP )
    {
        if( Value > TreeP->Element )
            TreeP = TreeP->Right;
        else if( Value < TreeP->Element )
            TreeP = TreeP->Left;
        else
            break;
    }

    return TreeP;
}


void
DeleteNode( T *TreePP, int Value )
{
    T Next;
    T Min;

    while( NULL != ( Next = *TreePP ) )
    {
        if( Value == Next->Element )
        {
            if( NULL == Next->Left || NULL == Next->Right )
                break;
            Min = FindMin( Next->Right );
            Next->Element = Min->Element;
            Value = Min->Element;
            TreePP = &Next->Right;
        }
        else if( Value > Next->Element )
            TreePP = &Next->Right;
        else if( Value < Next->Element )
            TreePP = &Next->Left;        
    }
    if( NULL != Next )
    {
        if( NULL != Next->Left )
            *TreePP = Next->Left;
        else if( NULL != Next->Right )
            *TreePP = Next->Right;
        else
            *TreePP = NULL;
        free( Next );
    }

}


void
Print( T TreeP )//测试用函数，可删除。
{
    if( NULL == TreeP )
        return;

    Print( TreeP->Left );

    Print( TreeP->Right );
    printf( "%5d ",TreeP->Element );
}


static void
Posh( T Node );

static T
Pop( void );

static int
Empty( void );

static int
Full( void );

static void
DeleteStack( void );


void
PrevTraversal( T TreeP )
{
    if( NULL == TreeP )
        return;

    Posh( TreeP );
    while( !Empty() )
    {
        TreeP = Pop();
        printf( "%5d ", TreeP->Element );
        if( NULL != TreeP->Right )
            Posh( TreeP->Right );
        if( NULL != TreeP->Left )
            Posh( TreeP->Left );
    }
    DeleteStack();
}


void
InorderTraversal( T TreeP )//中序遍历并不算我写的，因为大量参考了网上找到的代码，甚至在结果上也跟参考的代码近乎一致。
{

    while( NULL != TreeP || !Empty() )
    {
        if( NULL != TreeP )
        {
            Posh( TreeP );
            TreeP = TreeP->Left;
        }
        else
        {
            TreeP = Pop();
            printf( "%5d ", TreeP->Element );
            TreeP = TreeP->Right;
        }
    }

    DeleteStack();
}


void
PostorderTraversal( T TreeP )
{
    T Signed;

    if( NULL == TreeP )
        return;

    Posh( TreeP );
    while( !Empty() )
    {
        TreeP = Pop();

        if(  ( NULL != TreeP->Right || NULL != TreeP->Left )
                && ( Signed != TreeP->Right && Signed != TreeP->Left ) )
        {
            Posh( TreeP );
            if( NULL != TreeP->Right )
                Posh( TreeP->Right );
            if( NULL != TreeP->Left )
                Posh( TreeP->Left );
        }
        else
        {
            Signed = TreeP;
            printf( "%5d ", TreeP->Element );
        }
    }

    DeleteStack();
}


#include "d:\mylib\queue.h"
MakeQueue( T, _Tree )

void
LevelTraversal( T TreeP )
{
    if( NULL == TreeP )
        return;

    Create_Tree();
    Insert_Tree( TreeP );

    while( !Is_Empty_Tree() )
    {
        TreeP = First_Tree();
        Delete_Tree();
        printf( "%5d ", TreeP->Element );
        if( NULL != TreeP->Left )
            Insert_Tree( TreeP->Left );
        if( NULL != TreeP->Right )
            Insert_Tree( TreeP->Right );
    }
    Destroy_Tree();
}


#define INITSIZE 128
static T *Stack;
static int Top = -1;
static int CurrentSize = INITSIZE;


int
Empty( void )
{
    return -1 == Top;
}


int
Full( void )
{
    if( Top == CurrentSize - 1 )
    {
        CurrentSize += INITSIZE;
        T *Temp;
        Temp = ( T * )realloc( Stack, CurrentSize * sizeof( T ) );
        if( NULL == Temp )
        {
            CurrentSize -= INITSIZE;
            return NOT;
        }
        Stack = Temp;
        return OK;
    }
    else
        return OK;
}


void
Posh( T Node )
{
    if( NULL == Stack )
    {
        Stack = ( T * )malloc( CurrentSize * sizeof( T ) );
        if( NULL == Stack )
            exit( EXIT_FAILURE );
    }
    if( !Full() )
        Stack[ ++Top ] = Node;
}


T
Pop( void )
{
    return Stack[ Top-- ];
}


void
DeleteStack( void )
{
    free( Stack );
    Stack = NULL;
    Top = -1;
    CurrentSize = INITSIZE;
}

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

搜索更多相关主题的帖子: color　二叉树　

第 2 楼

得分:10

树其实这方面可以涉及到很深的部分~看样子一般学数据结构顶多学到非递归的三种遍历并且会解一些基本题目就完工了~记得学得深的还有什么AVL树红黑树伸展树~搜索结构记得还有索引树这个我还没去弄~这些打算学完基本数据结构再回来学~

PS一下~记得还有哈希和堆这两个很重要的结构~不知道数据结构教材里面有没有提及过~

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

第 3 楼

得分:0

回复 2楼九转星河

只要普通的二叉树搞定，AVL树不是问题,伸展树是AVL树的进阶，一个搞定另一个也不是太大的问题。所以，基础很重要。

删除节点，终于搞定了。

Debug了半天，才发现原来DeleteNode函数本身没有问题，问题出在FindMin函数上，我靠。

现在已经差不多了，就剩下迭代版本的四种遍历和树的深度了。希望下周之前搞定，嗯……希望这周工作不忙，要不然完全没时间想编程。

[此贴子已经被作者于2017-5-9 23:35编辑过]

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

第 4 楼

得分:0

下周之前啊~看来学起来比我还赶进度呢~还是先好好消化吧

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

第 5 楼

得分:0

回复 4楼九转星河

树的四种遍历能够多难啊，大概也就花点时间整理下思路，然后就可以开写了。

反正这周尽可能完成普通树。下周进入AVL环节。

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

第 6 楼

得分:0

回复 5楼 renkejun1942

不不不

~你不是已经整理了通用栈和队列么~就是用栈来代替递归啊~按层遍历可以用队列~很快可以完工的~至于二叉树~这个要慢慢来~删除节点是个坎~还可以看看二叉索引树的穿插遍历~那个好像数据结构上没怎么讲~AVL树我等着~因为我还没去消化

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

第 7 楼

得分:0

回复 6楼九转星河

删除节点我已经写出来了呀。
我自己看着还挺好。

通用性以后再说吧。

我并不是太想直接调用我完成的泛型栈和队列，我不想让彼此产生依赖关系。

我现在的想法是写一些简易版本的栈和队列函数来支持四种遍历的迭代版本。

慢慢来也是个好办法，但是我的做法是搞不懂的东西就先放着，某些时候想破头都想不到的东西，但是放一放，思路也许在某个时间点突然就冒出来了。

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

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

第 8 楼

得分:10

你写的这些代码有没有上传到GitHub或者什么博客上啊？在论坛上发没有形成系统查阅使用起来并不方便。

φ(゜▽゜*)♪

第 9 楼

得分:0

回复 8楼书生牛犊

没有，我不发博客。可以点开我的个人资料，看主题帖呀。这不就是一个统计么？
论坛我都当我的一个记录，同时也算分享一下。
因此我的代码从来不写注释，就算有注释，在发出来的时候我也会全部删掉。

我的理论是，想弄懂，自己写注释。又有几个学习编程的人不是从抄代码写注释开始的呢？

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

第 10 楼

得分:0

提个建议。T的结构不妨写成这样子

程序代码：

typedef struct T *T;
struct T{
    void* Node;/*比起 int Element;用无类型指针类型可以容纳的数据类型更多，也更加实用*/
    T Left;
    T Right;}

涉及到要比较“大小”区分左右的时候可以模仿qsort（）等系统函数，交给通过函数指针int cmp(void*Node1,void*Node2)把皮球提给代码使用者

反正所有类型的指针都是一样的，而且通常情况下这会更节约空间。

不过malloc() free()多了，程序运行速度也会相对慢一些。各有利弊吧

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

φ(゜▽゜*)♪