这么多天了，搜索二叉树才搞定了最基础的部分（蹉跎了好些岁月，终于搞定了四种遍历）
这么多天了，搜索二叉树才搞定了最基础的部分。 
程序代码：#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编辑过]
~~
~你不是已经整理了通用栈和队列么~就是用栈来代替递归啊~按层遍历可以用队列~很快可以完工的~至于二叉树~这个要慢慢来~删除节点是个坎~还可以看看二叉索引树的穿插遍历~那个好像数据结构上没怎么讲~AVL树我等着~因为我还没去消化
不过malloc() free()多了，程序运行速度也会相对慢一些。各有利弊吧