首页
登录 | 注册

二叉查找树的实现

  二叉查找树是满足以下条件的二叉树:

     1.左子树上的所有节点值均小于根节点值,

     2.右子树上的所有节点值均不小于根节点值,

     3.左右子树也满足上述两个条件。

  二叉查找树的插入过程如下:

      1.若当前的二叉查找树为空,则插入的元素为根节点,2.若插入的元素值小于根节点值,则将元素插入到左子树中,3.若插入的元素值不小于根节点值,则将元素插入到右子树中。

  二叉查找树的删除,分三种情况进行处理:

  1.p为叶子节点,直接删除该节点,再修改其父节点的指针(注意分是根节点和不是根节点),如图a。

  2.p为单支节点(即只有左子树或右子树)。让p的子树与p的父亲节点相连,删除p即可;(注意分是根节点和不是根节点);如图b。

  3.p的左子树和右子树均不空。找到p的后继y,因为y一定没有左子树,所以可以删除y,并让y的父亲节点成为y的右子树的父亲节点,并用y的值代替p的值;或者方法二是找到p的前驱x,x一定没有右子树,所以可以删除x,并让x的父亲节点成为y的左子树的父亲节点。如图c。

      1. z结点没有孩子。

  如下图a所示,我们要删除值为13的结点,因为结点没有孩子,所以删除之后不会影响到二叉树的整体性质,也就是说,直接将13这个结点删除即可,如图a所示,从左边的二叉树删除13这个点之后变到右边的二叉树。

   2. z结点有一个孩子。

  如下图b所示,要删除的值为16的结点有一个孩子,而且是右孩子,那么从图上来看,如果,我们将16去掉,然后把以20为结点的子树作为15的右子树,那么整棵树还是符合二叉查找树的性质的,因此,有一个孩子的结点的删除操作,就是要将其孩子作为其父结点的孩子即可。如图b所示。

   3. z结点有两个孩子。

  如下图c所示,要删除的值为5的结点,有两个孩子,删除之后肯定整棵树就不符合二叉查找树的性质了,因此要进行调整,我们发现,将5的后继,值为6的结点来放到5的位置,然后将6的孩子7作为6的父结点10的孩子,如下图c所示,我们要删除的是z结点,而我们实际要删除y结点,并替换z结点。这里需要注意的一点是,如果一个结点有右孩子,则该结点的后继,至多有一个子女,而且是右孩子。因为假如该结点的后继有左孩子和右孩子,那么其左孩子的值肯定是介于该结点和其后继之间的,那么按照二叉查找树的性质,这个左孩子就应该是该结点的后继,所以,这与原先的后继相互矛盾,因此,结论成立。

 

 

二叉查找树的实现

 

 

tree.h

 1         /*二叉查找树的类型声明*/
 2         typedef int ElementType;
 3 
 4 /* START: fig4_16.txt */
 5         #ifndef _Tree_H
 6         #define _Tree_H
 7 
 8         struct TreeNode;
 9         typedef struct TreeNode *Position;
10         typedef struct TreeNode *SearchTree;
11 
12         SearchTree MakeEmpty( SearchTree T );
13         Position Find( ElementType X, SearchTree T );
14         Position FindMin( SearchTree T );
15         Position FindMax( SearchTree T );
16         SearchTree Insert( ElementType X, SearchTree T );
17         SearchTree Delete( ElementType X, SearchTree T );
18         ElementType Retrieve( Position P );
19 
20         #endif  /* _Tree_H */
21 
22 /* END */

tree.c

  1         #include "tree.h"
  2         #include <stdlib.h>
  3         #include "fatal.h"
  4 
  5         struct TreeNode
  6         {
  7             ElementType Element;
  8             SearchTree  Left;
  9             SearchTree  Right;
 10         };
 11 
 12 /* START: fig4_17.txt */
 13 
 14         /*让二叉查找树为空*/
 15         SearchTree
 16         MakeEmpty( SearchTree T )
 17         {
 18             if( T != NULL )
 19             {
 20                 MakeEmpty( T->Left );
 21                 MakeEmpty( T->Right );
 22                 free( T );
 23             }
 24             return NULL;
 25         }
 26 /* END */
 27 
 28 /* START: fig4_18.txt */
 29         /*找元素在二叉查找树中的位置*/
 30         Position
 31         Find( ElementType X, SearchTree T )
 32         {
 33             if( T == NULL )
 34                 return NULL;
 35             if( X < T->Element )
 36                 return Find( X, T->Left );
 37             else
 38             if( X > T->Element )
 39                 return Find( X, T->Right );
 40             else
 41                 return T;
 42         }
 43 /* END */
 44 
 45 /* START: fig4_19.txt */
 46         //递归实现
 47         Position
 48         FindMin( SearchTree T )
 49         {
 50             if( T == NULL )
 51                 return NULL;
 52             else
 53             if( T->Left == NULL )
 54                 return T;
 55             else
 56                 return FindMin( T->Left );
 57         }
 58 /* END */
 59 
 60 /* START: fig4_20.txt */
 61         //非递归实现
 62         Position
 63         FindMax( SearchTree T )
 64         {
 65             if( T != NULL )
 66                 while( T->Right != NULL )
 67                     T = T->Right;
 68 
 69             return T;
 70         }
 71 /* END */
 72 
 73 /* START: fig4_22.txt */
 74 
 75         /*二叉查找树的插入*/
 76         SearchTree
 77         Insert( ElementType X, SearchTree T )
 78         {
 79 /* 1*/      if( T == NULL )
 80             {
 81                 /* Create and return a one-node tree */
 82 /* 2*/          T = malloc( sizeof( struct TreeNode ) );
 83 /* 3*/          if( T == NULL )
 84 /* 4*/              FatalError( "Out of space!!!" );
 85                 else
 86                 {
 87 /* 5*/              T->Element = X;
 88 /* 6*/              T->Left = T->Right = NULL;
 89                 }
 90             }
 91             else
 92 /* 7*/      if( X < T->Element )
 93 /* 8*/          T->Left = Insert( X, T->Left );
 94             else
 95 /* 9*/      if( X > T->Element )
 96 /*10*/          T->Right = Insert( X, T->Right );
 97             /* Else X is in the tree already; we'll do nothing */
 98 
 99 /*11*/      return T;  /* Do not forget this line!! */
100         }
101 /* END */
102 
103 /* START: fig4_25.txt */
104 
105         /*二叉查找树的删除*/
106         /*
107           分三种情况
108           1.两个子节点
109           2.1个子节点(左节点或者右节点)
110           3.叶子节点(0个子节点)
111          */
112         SearchTree
113         Delete( ElementType X, SearchTree T )
114         {
115             Position TmpCell;
116 
117             if( T == NULL )
118                 Error( "Element not found" );
119             else
120             if( X < T->Element )  /* Go left */
121                 T->Left = Delete( X, T->Left );
122             else
123             if( X > T->Element )  /* Go right */
124                 T->Right = Delete( X, T->Right );
125             else  /* Found element to be deleted */
126             if( T->Left && T->Right )  /* Two children 两个孩子*/
127             {
128                 /* Replace with smallest in right subtree */
129                 TmpCell = FindMin( T->Right );
130                 T->Element = TmpCell->Element;
131                 T->Right = Delete( T->Element, T->Right );
132             }
133             else  /* One or zero children */
134             {
135                 TmpCell = T;
136                 if( T->Left == NULL ) /* Also handles 0 children 也处理了0个孩子的情况*/
137                     T = T->Right;
138                 else if( T->Right == NULL )
139                     T = T->Left;
140                 free( TmpCell );
141             }
142 
143             return T;
144         }
145 /* END */
146 
147         /* 返回某个节点的元素 */
148         ElementType
149         Retrieve( Position P )
150         {
151             return P->Element;
152         }

 

 

 

 

参考资料

二叉查找树--插入、删除、查找

《算法导论》CLRS算法C++实现(十)P151 二叉查找树

二叉查找树(五)

二叉查找树的插入和删除详解



2019 cecdns.com webmaster#cecdns.com
11 q. 0.073 s.
京ICP备10005923号