2018-04-24 478 views 评论

数据结构【浙江大学】（第4节）整理

标签：数据结构

第四节：二叉搜索树

4.1 二叉搜索树

二叉搜索树（BST），也称二叉排序树和二叉查找树。一棵这个树，可以为空。如果不为空，满足以下性质：

（1）非空左子树的所有键值小于其根结点的键值。

（2）非空右子树的所有键值大于其根结点的键值。

（3）左、右子树都是二叉搜索树。

1.二叉搜索树操作的函数：

Position Find(ElementType X, BinTree BST)：从二叉搜索树BST中查找元素X，并返回其结点地址；

Position FindMin(ElementType X, BinTree BST)：从二叉搜索树BST中查找最小元素X，并返回其结点地址；

Position FindMax(ElementType X, BinTree BST)：从二叉搜索树BST中查找最大元素X，并返回其结点地址；

BinTree Insert(ElementType X, BinTree BST)

BinTree Delete(ElementType X, BinTree BST)

2.二叉搜索树的查找操作：Find

查找从根结点开始，如果树为空，返回NULL。

若树非空，则根结点关键字与X进行比较，并进行以下处理：

（1）若X小于根结点键值，则在左子树中继续搜索；

（2）若X大于根节点键值，则在右子树中搜索；

（3）若两者相等，搜索完成，返回指向此结点的指针。

代码如下：

Position&nbsp;Find(ElementType&nbsp;X,&nbsp;BinTree&nbsp;BST)
{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!BST)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;NULL;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(X&gt;BST-&gt;Data)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;Find(X,BST-&gt;Right);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(X&lt;BST-&gt;Data)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;Find(X,&nbsp;Bst-&gt;Left);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;BST;
}

Position Find(ElementType X, BinTree BST)

{

       if(!BST)

              return NULL;

       if(X>BST->Data)

              return Find(X,BST->Right);

       else if(X<BST->Data)

              return Find(X, Bst->Left);

       else

              return BST;

}

由于非递归函数的执行效率高，可将尾递归函数修改为迭代函数：

Position&nbsp;Find(ElementType&nbsp;X,&nbsp;BinTree&nbsp;BST)
{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(BST){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(X&gt;BST-&gt;Data)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST=&nbsp;BST-&gt;Right;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(X&lt;BST-&gt;Data)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST=&nbsp;BST-&gt;Left;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;BST;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;NULL;
}

Position Find(ElementType X, BinTree BST)

{

       while(BST){

              if(X>BST->Data)

                     BST= BST->Right;

              else if(X<BST->Data)

                     BST= BST->Left;

       else

              return BST;

       }

       return NULL;

}

3.查找最大和最小元素

最大元素一定在树的最右分支的端结点上；最小元素在最左分支的端结点上。

/*查找最小元素的递归函数*/
Position&nbsp;FindMin(BinTree&nbsp;BST)
{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!BST)&nbsp;return&nbsp;NULL;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(!BST-&gt;Left)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;BST;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;FindMin(BST-&gt;Left);
}
/*查找最大元素的迭代函数*/
Position&nbsp;FindMax(BinTree&nbsp;BST)
{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(BST)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(BST-&gt;Right)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST&nbsp;=&nbsp;BST-&gt;Right;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;BST;
}

/*查找最小元素的递归函数*/

Position FindMin(BinTree BST)

{

       if(!BST) return NULL;

       else if(!BST->Left)

              return BST;

       else

              return FindMin(BST->Left);

}

/*查找最大元素的迭代函数*/

Position FindMax(BinTree BST)

{

       if(BST)

              while(BST->Right)

                     BST = BST->Right;

       return BST;

}

4.二叉搜索树的插入

分析：关键是要找到元素应该插入的位置，可以采用与Find类型的方法。

BinTree&nbsp;Insert(ElementType&nbsp;X,&nbsp;BinTree&nbsp;BST)
{
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!BST){
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST&nbsp;=&nbsp;malloc(sizeof(struct&nbsp;TreeNode));
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST-&gt;Data&nbsp;=X;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST-&gt;Left&nbsp;=&nbsp;BST-&gt;Right&nbsp;=NULL;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(X&lt;BST-&gt;Data)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST-&gt;Left&nbsp;=&nbsp;Insert(X,&nbsp;BST-&gt;Left);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(X&gt;BST-&gt;Data)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST-&gt;Right&nbsp;=&nbsp;Inser(X,BST-&gt;Right);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;BST;
}

BinTree Insert(ElementType X, BinTree BST)

{

       if(!BST){

              BST = malloc(sizeof(struct TreeNode));

              BST->Data =X;

              BST->Left = BST->Right =NULL;

       }

       else if(X<BST->Data)

              BST->Left = Insert(X, BST->Left);

       else if(X>BST->Data)

              BST->Right = Inser(X,BST->Right);

       return BST;

}

4.二叉搜索树的删除

我们需要考虑三种情况：

（1）要删除的是叶结点：直接删除，并再修改其父结点指针为NULL。

（2）要删除的结点只有一个孩子结点：要将其父结点的指针指向要删除结点的孩子结点。

（3）要删除的结点有左、右两棵子树：用另一结点代替被删除的结点：右子树的最小元素或者左子树的最大元素。如图2所示。

图1

代码如下所示：

BinTree&nbsp;Delete(&nbsp;ElementType&nbsp;X,&nbsp;BinTree&nbsp;BST&nbsp;)
{&nbsp;&nbsp;&nbsp;Position&nbsp;Tmp;
&nbsp;&nbsp;&nbsp;&nbsp;if(&nbsp;!BST&nbsp;)&nbsp;printf(&quot;要删除的元素未找到&quot;);
&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(&nbsp;X&nbsp;&lt;&nbsp;BST-&gt;Data&nbsp;)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST-&gt;Left&nbsp;=&nbsp;Delete(&nbsp;X,&nbsp;BST-&gt;Left);&nbsp;/*&nbsp;左子树递归删除&nbsp;*/
&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(&nbsp;X&nbsp;&gt;&nbsp;BST-&gt;Data&nbsp;)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST-&gt;Right&nbsp;=&nbsp;Delete(&nbsp;X,&nbsp;BST-&gt;Right);&nbsp;/*&nbsp;右子树递归删除&nbsp;*/
&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;/*找到要删除的结点&nbsp;*/
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(&nbsp;BST-&gt;Left&nbsp;&amp;&amp;&nbsp;BST-&gt;Right&nbsp;)&nbsp;{&nbsp;/*被删除结点有左右两个子结点&nbsp;*/
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Tmp&nbsp;=&nbsp;FindMin(&nbsp;BST-&gt;Right&nbsp;);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*在右子树中找最小的元素填充删除结点*/
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST-&gt;Data&nbsp;=&nbsp;Tmp-&gt;Data;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST-&gt;Right&nbsp;=&nbsp;Delete(&nbsp;BST-&gt;Data,&nbsp;BST-&gt;Right);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/*在删除结点的右子树中删除最小元素*/
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;{&nbsp;/*被删除结点有一个或无子结点*/
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Tmp&nbsp;=&nbsp;BST;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(&nbsp;!BST-&gt;Left&nbsp;)&nbsp;/*&nbsp;有右孩子或无子结点*/
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST&nbsp;=&nbsp;BST-&gt;Right;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else&nbsp;if(&nbsp;!BST-&gt;Right&nbsp;)&nbsp;/*有左孩子或无子结点*/
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BST&nbsp;=&nbsp;BST-&gt;Left;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;free(&nbsp;Tmp&nbsp;);
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;BST;
}