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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3517 天前的主题，其中的信息可能已经有所发展或是发生改变。

好久没上了。。。
数据结构给我的感觉就是，知道是个什么玩意儿，懂这个结构怎么实现的，但是要解决什么问题就感觉无从下手，尤其是带指针的语言，完全晕，上次计蒜客一个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;
}