算法（5）—— 二叉查找树

这个几天前写过一遍，现在写就发现又差点很快忘掉，常复习，顺便通过这段时间的学习，把常见的树结构都搞懂。

1. 头文件

 1 #ifndef  TREE_H
 2 #define  TREE_H
 3 
 4 typedef int ElementType;
 5 
 6 struct TreeNode;
 7 typedef struct TreeNode *Position;
 8 typedef struct TreeNode *SearchTree;
 9 
10 SearchTree MakeEmpty( SearchTree T );
11 Position Find( ElementType X, SearchTree T );
12 Position FindMin( SearchTree T );
13 Position FindMax( SearchTree T );
14 SearchTree Insert( ElementType X, SearchTree T );
15 SearchTree Delete( ElementType X, SearchTree T );
16 ElementType Retrieve( Position P );
17 void PrintElement(ElementType X);
18 void PrintTree(SearchTree T);
19 
20 #endif  /* TREE_H */

tree.h

2.实现

  1 #include "tree.h"
  2 #include <stdlib.h>
  3 #include "fatal.h"
  4 #include <stdio.h>
  5 
  6 
  7 struct TreeNode  {
  8   ElementType Element;
  9   SearchTree  Left;
 10   SearchTree  Right;
 11 };
 12 
 13 SearchTree  MakeEmpty( SearchTree T )  {
 14   if( T != NULL )
 15     {
 16       MakeEmpty( T->Left );
 17       MakeEmpty( T->Right );
 18       free( T );
 19     }
 20   return NULL;
 21 }
 22 
 23 Position   Find( ElementType X, SearchTree T )   {
 24   if( T == NULL )
 25     return NULL;
 26   if  ( X < T->Element )
 27          return Find( X, T->Left );
 28   else if( X > T->Element )
 29       return Find( X, T->Right );
 30   else
 31       return T;
 32 }
 33 
 34 Position   FindMin( SearchTree T )  {
 35   if( T == NULL )
 36     return NULL;
 37   else if( T->Left == NULL )
 38       return T;
 39   else
 40       return FindMin( T->Left );
 41 }
 42 
 43 Position  FindMax( SearchTree T )    {
 44   if( T != NULL )
 45     while( T->Right != NULL )
 46       T = T->Right;
 47 
 48   return T;
 49 }
 50 
 51 SearchTree Insert( ElementType X, SearchTree T )  {
 52   if( T == NULL )  {
 53     /* Create and return a one-node tree */
 54     T = malloc( sizeof( struct TreeNode ) );
 55     if( T == NULL )
 56       FatalError( "Out of space!!!" );
 57     else  {
 58       T->Element = X;
 59       T->Left = T->Right = NULL;
 60     }
 61   }
 62   else if( X < T->Element )
 63       T->Left = Insert( X, T->Left );
 64   else if( X > T->Element )
 65     T->Right = Insert( X, T->Right );
 66   /* Else X is in the tree already; we'll do nothing */
 67 
 68   return T;  /* Do not forget this line!! */
 69 }
 70 
 71 SearchTree   Delete( ElementType X, SearchTree T )  {
 72   Position TmpCell;
 73 
 74   if( T == NULL )
 75     Error( "Element not found" );
 76   else  if( X < T->Element )  /* Go left */
 77       T->Left = Delete( X, T->Left );
 78   else  if( X > T->Element )  /* Go right */
 79             T->Right = Delete( X, T->Right );
 80     else     if ( T->Left && T->Right ) /* Two children */  {
 81         /* Found element to be deleted */
 82       /* Replace with smallest in right subtree */
 83       TmpCell = FindMin( T->Right );
 84       T->Element = TmpCell->Element;
 85       T->Right = Delete( T->Element, T->Right );
 86     }
 87     else  /* One or zero children */ {
 88       TmpCell = T;
 89       if( T->Left == NULL ) /* Also handles 0 children */
 90         T = T->Right;
 91       else if( T->Right == NULL )
 92         T = T->Left;
 93       free( TmpCell );
 94     }
 95 
 96   return T;
 97 }
 98 
 99 ElementType Retrieve( Position P )  {
100   return P->Element;
101 }
102 
103 void PrintElement(ElementType X)  {
104   printf("%d
",X);
105 }
106 
107 void PrintTree (SearchTree T)  {
108   if (T != NULL)  {
109     PrintTree(T->Left);
110     PrintElement(T->Element);
111     PrintTree(T->Right);
112   }
113 }

tree.c

3.测试

 1 #include "tree.c"
 2 #include <stdio.h>
 3 
 4 int main(int argc,char **argv )    {
 5   SearchTree T;
 6   Position P;
 7   int i;
 8 
 9   T = MakeEmpty  ( NULL );
10   for( i = 0; i < 50; i += 5)
11     T = Insert  ( i, T );
12   PrintTree  (T);
13     printf  ("
");
14 
15     for  (i = 0;i < 50; i += 10)
16     T = Delete (i,T);
17     PrintTree  (T);
18   printf ("
");
19   printf ("Min is %d,Max is %d. 
",Retrieve(FindMin(T)),Retrieve((FindMax(T))));
20   
21     return 0;
22 }

testtree.c