浙大数据结构：04-树7 二叉搜索树的操作集

本文主要是介绍浙大数据结构：04-树7 二叉搜索树的操作集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题答案都在PPT上，所以先学会再写的话并不难。

1、BinTree Insert( BinTree BST, ElementType X )

递归实现，小就进左子树，大就进右子树。

为空就新建结点插入。

BinTree Insert( BinTree BST, ElementType X )
{if(!BST){BST=(BinTree)malloc(sizeof(struct TNode));BST->Data=X;BST->Left=BST->Right=NULL;return BST;}if(X < BST->Data)BST->Left=Insert(BST->Left,X);else if(X > BST->Data)BST->Right=Insert(BST->Right,X);return BST;
}

2、BinTree Delete( BinTree BST, ElementType X )

递归遍历直到找到该节点，才准备删除。

而删除结点有两种方法，一种是删左子树的最大值，一种是删右子树的最小值，这里我们取后者。

找到右子树最小值替换该结点的值，然后删除右子树的该结点

如果最多只有一个子树，则直接修改指针为该子树根节点即可。

BinTree Delete( BinTree BST, ElementType X )
{Position tmp;if(!BST)printf("Not Found\n");else{if(X<BST->Data)BST->Left=Delete(BST->Left,X);else if(X>BST->Data)BST->Right=Delete(BST->Right,X);else {
if(BST->Left&&BST->Right)
{tmp=FindMin(BST->Right);BST->Data=tmp->Data;BST->Right=Delete(BST->Right,BST->Data);}else {tmp=BST;if(!BST->Left)BST=BST->Right;else BST=BST->Left;free(tmp);}}}return BST;
}

3、Position Find( BinTree BST, ElementType X )

递归遍历数，小就找左，大就找右直到找到。

Position Find( BinTree BST, ElementType X )
{if(!BST)return NULL;if(X>BST->Data)return Find(BST->Right,X);else if(X<BST->Data)return Find(BST->Left,X);else return BST;
}

4、Position FindMin( BinTree BST )

递归只找左子树到尽头

Position FindMin( BinTree BST )
{
if(!BST)return NULL;else if(!BST->Left)return BST;else return FindMin(BST->Left);
}

5、Position FindMax( BinTree BST )

递归只找右子树到尽头

Position FindMax( BinTree BST )
{if(!BST)return NULL;else if(!BST->Right)return BST;else return FindMax(BST->Right);
}

这篇关于浙大数据结构：04-树7 二叉搜索树的操作集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---