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

2015-05-10 12:23:16 +08:00
 zhufree

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

二叉搜索树(Binary Search Tree)

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

几个常用函数及实现:

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

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

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

哦靠,晕了

2971 次点击
所在节点    编程
4 条回复
znoodl
2015-05-10 12:32:00 +08:00
我觉得平衡二叉树比这个难,怎么平衡使查询效率高,数据结构算法就是耗脑子的东西
Reficul
2015-05-10 13:06:59 +08:00
那会我上这个公开课的时候,只会C,各种边界上出错。简直痛苦。😰
feiyuanqiu
2015-05-10 14:26:30 +08:00
之前看算法的时候,二叉搜索树我觉得还行,挺好理解的,我是倒在 avl 树那里的,根本都想不通旋转是怎么弄的
zhufree
2015-05-10 14:49:41 +08:00
@znoodl 都开始怀疑自己智商了OAO

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/189901

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX