网易云课堂数据结构二叉搜索树（ 2015.5.9-10）/h1>

 

  zhufree 2015-05-10 12:23:16 +08:00 3473 次点击

好久没上了。。。
数据结构给我的感觉就是，知道是个什么玩意儿，懂这个结构怎么实现的，但是要解决什么问题就感觉无从下手，尤其是带指针的语言，完全晕，上次计蒜客一个cpp的部分逆置单链表的题目卡了一晚上还是没弄出来，不知道到底是哪里不对劲了，心塞。

二叉搜索树(Binary Search Tree)

特征：
- 非空左子树的值小于其根节点的值
- 非空右子树的值大于其根结点的值
- 左右子树都是二叉搜索树

几个常用函数及实现：

• Position Find(ElementType x,BinTree BST):查找元素X，返回地址

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; } 

树空时直接返回NULL，树不空时，和根节点的键值比较，大于则往右找，小于则往左找，循环这一过程，尾递归方式（在返回的时候进行递归），效率不高，从编译的角度尾递归都可以用循环代替,如下

Position IterFind(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; } 

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

• Position FindMin(BinTree BST):查找最小元素并返回结点地址
  
  
Position FindMin(BinTree BST){
if(!BST) return NULL;
else if(!BST->Left)
return BST;
else
return FindMin(BST->Left);
}


  不断往左边走

• Position FindMax(BinTreeBST):查找最大元素并返回结点地址
  
Position FindMax(BinTree BST){
if(BST)
while(BST->Right) BST=BST->Right;
return BST;
}


  不断往右边走

• BinTree Insert(ElementType X,BinTree 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=Insert(X,Bst->Right);
return BST;


  如果是空树，直接申请一个空间，否则则像find一样先比较,找到应该查入在哪一个结点后面之后，进入第一个分支，创建一个结点，挂在上一个结点后面。
  因此不是return Insert(X,BST->Right)
  而是BST->Right=Insert(X,BST->Right)，把这个结点连接上一个结点。

• BinTree Delete(ElementType X,BinTree BST):删除元素。三种情况

  • 叶节点：直接删除，再修改父节点指针置为NULL
  • 有一个孩子的结点：使父节点的指针指向要删除结点的孩子结点
  • 左右都不空：用另一节点替代被删除结点，右子树的最小元素，或左子树的最大元素（这两者一定不是有两个孩子的结点），使二叉搜索树的依然有顺序。

BinTree Delete(ElementType X,BinTree BST){ Postion Tmp; if(!BST) printf("not found"); else if(X<BST->Data) BST->Left=Delete(X,BST->Left);//左子树递归删除 else if(X>BST->Right) BST->Right=Delete(X,BST->Right);//右子树递归删除 else//找到要删除的结点 if(BST->Left && Bst->Right){//左右两边都不空 Tmp=FindMin(BST->Right);//找到右边最小结点 BST->Data=Tmp->Data;//拷贝复制给当前结点，替代 BST->Right=Delete(BST->Data,BST->Right);//把右子树中的最小结点即Tmp删除 }else{//有一个孩子 Tmp=BST; if(!BST->Left)//左边空 BST=BST->Right; else if(!bst->Right)//右边空 BST=BST->Left; free(Tmp); } return BST; } 

哦靠，晕了