注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

永恒的遗失古都-亚特兰蒂斯

一个游戏开发者的个人博客。

 
 
 

日志

 
 

一些程序基础概念1 - 二叉树和堆排序  

2015-08-26 18:16:40|  分类: 程序相关 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
马上要面试了,再复习下面试常见的基础概念。

二叉树的定义:树有且仅有一个根节点,除根节点外,每个子节点仅有一个父节点,且最多有两个子节点(可没有或者仅有一个),子节点有左右之分。
二叉树的结构:存储可以使用顺序存储(类似数组),可使用链式存储。当然链式存储更加灵活多见。链式存储结构类似线性链表,每个节点结构包含三个要点:数据,左子节点指针,右子节点指针。(注意,并未记录父节点指针)
struct BiTreeNode{ 
T value; 
BiTreeNode* pLeft; 
BiTreeNode* pRight; 
};
二叉树的遍历:因为二叉树是个递归结构,主要包含三部分:根节点(N),左子节点(L),右子节点(R)。所以对其遍历有六种方案:NLR、LNR、LRN、NRL、RNL和LNR。
但因为有对称性,只要了解三种即可,另外三种完全对称。NLR、LNR和LRN分别为“先序遍历”、“中序遍历”和“后序遍历”。
递归方式的二叉树遍历比较简单:以中序遍历为例:
//中序遍历--递归  
int traverseBiTreeInOrder(BiTreeNode *ptree,int (*visit)(int))  
{  
    if(ptree)  
    {  
        if(traverseBiTreeInOrder(ptree->left,visit))  
            if(visit(ptree->c))  
                if(traverseBiTreeInOrder(ptree->right,visit))  
                    return 1;  
        return 0;  
    }else return 1;  
}  
// 前序则是先遍历根节点
int traverseBiTreePreOrder(BiTreeNode *ptree,int (*visit)(int))  
{  
    if(ptree)  
    {  
        if(visit(ptree->c))  
            if(traverseBiTreePreOrder(ptree->left,visit))  
                if(traverseBiTreePreOrder(ptree->right,visit))  
                    return 1;  //正常返回  
        return 0;   //错误返回  
    }else return 1;   //正常返回  
}  
还可以进行非递归的遍历,但要自行解组二叉树填充栈结构,较复杂不再赘述。

满二叉树的定义除最后一层外,所有层上的节点数均达到最大值的二叉树。
完全二叉树的定义:除最后一层外,所有层上的节点数均达到最大值(即一定为满二叉树);在最后一层上仅允许缺少右边的节点。
如图为合理的完全二叉树:
一些程序基础概念1 - 二叉树和堆排序 - 自由骑士笃志 - 永恒的遗失古都-亚特兰蒂斯
图解释:上三层为满层。最后一层未满。最后一层仅右侧节点缺失,左侧为完整。
二叉搜索树(又称为 二叉查找树,二叉排序树的定义:它或者是一个空树,或者是具有以下性质的二叉树:若其左子树不为空,则其左子树上的所有节点均小于其根节点的值;若其右子树不为空,则其右子树的所有节点均大于其根节点的值;其左右子树必然也为二叉搜索树。
如图为一个合理的二叉搜索树:
一些程序基础概念1 - 二叉树和堆排序 - 自由骑士笃志 - 永恒的遗失古都-亚特兰蒂斯
图解释:2<5<12 9>5 19>18>12 15<18 17>15 16<17
意义:对二叉排序树进行中序排序可得到一个有序序列。将一个无序数组(树)排序为一个二叉排序树,即为排序过程。其操作的时间复杂度等于树高O(log(2n))

平衡二叉树(又称为AVL树-因为是AV和L这俩人发明的)的定义:它是一颗空树,或者他的左右两个子树高度差的绝对值不超过1,并且左右子树都是一颗平衡二叉树。
如图是一颗平衡二叉树:
一些程序基础概念1 - 二叉树和堆排序 - 自由骑士笃志 - 永恒的遗失古都-亚特兰蒂斯
图解释:只有23,54和72的子节点有1的高度差,其他节点左右子树没有高度差。
意义:因为二叉搜索树,其操作的时间复杂度为O(log2n),取决于树高。当极端情况下(想一下链表或上图中的16-17-16的节点),若二叉搜索树退化为链表状态,其时间复杂度将退化为线性的O(n)。显然这种效率不是我们期望的,于是我们可以将二叉搜索树优化为平衡二叉树,因高度可以良好维持在O(log2n),所以可以提高其时间复杂度。
无序树排序为二叉搜索树的算法为核心,之后将额外专文说明。
 
红黑树的定义:它是一个自平衡二叉查找树(也可理解为是平衡二叉树的一种算法结构),或者我们可以认为是自带颜色属性的二叉查找树,颜色为红色或者黑色。对于颜色定义有以下要求:
1:根节点必然为黑色
2:空节点必然为黑色。
3:一个红节点其两个子节点必然为黑色。
4:从任意一节点到其每个子节点的路径中必然包含相同数目的黑色。
下图为一个合理的红黑树:
一些程序基础概念1 - 二叉树和堆排序 - 自由骑士笃志 - 永恒的遗失古都-亚特兰蒂斯
 
因为上述4个约定的强制要求,则保证了红黑树的关键性质: 其根节点到叶节点最长高度不可能多于最短高度路径的两倍。
该性质保证了红黑树的操作时间复杂度会稳定较低,为O(log(n))。C++的STL中大量使用了红黑树。

堆排序HeapSort的定义:它是算法,是选择排序的一种。它利用数组快速定位元素的特点,将数据组成为一个二叉堆。二叉堆一定是一个完全二叉树,但其又有些定义类似二叉搜索树。
二叉堆的定义:1:父节点值,一定大于等于(小于等于)其两个子节点任一节点值。
2:每个节点左右子树一定也是一个二叉堆。(注意:必须和全树都是大根堆或者小跟堆,必须全局一致。)
二叉堆分为大根堆和小根堆。大根堆的父节点大于等于子节点值,所以,大根堆的根节点一定是最大的值。小根堆反之。
如图所示为一个小根堆:
一些程序基础概念1 - 二叉树和堆排序 - 自由骑士笃志 - 永恒的遗失古都-亚特兰蒂斯
 我们一个乱序数组,目标是最终得到如下的数组堆。该过程就是堆排序。
一些程序基础概念1 - 二叉树和堆排序 - 自由骑士笃志 - 永恒的遗失古都-亚特兰蒂斯
堆排序的意义:排序时使用空间复杂度较少,时间复杂度和快排差不多。因为堆排序最终生成的是一个二叉堆(即一个有序的完全二叉树),二叉堆有其有序性,常用于A*寻路。
注意点堆 处于半有序状态。并非完全的有序(可看上图,并非10,15,25,30,56,70的完全有序),但又并非完全无需。只需建堆,则可获得有序数列。
堆排的大致思路:如图:
一些程序基础概念1 - 二叉树和堆排序 - 自由骑士笃志 - 永恒的遗失古都-亚特兰蒂斯
 
1:无序数组建堆。
2:循环(条件为:堆不为空。从最后一个非叶子节点开始,自下向上的顺序迭代)
{
    取得堆顶元素
    得到最后一个元素,将其移动到堆顶
    调整使其再次成堆
}
解释
图1:用数组建无序完全二叉树。
图1:找到最后的非叶的子节点97并调整父子位置
图2:图3图4:自下向上自右向左遍历,检查65,38,49节点
图5:因为图4的调整,则需要对调整的子节点复检,重新构子堆。
图6:得到小根堆(小顶堆)。
代码
//堆调整算法
void HeapAdjust (HeapType &H, int s, int m)
{   // 已知 H.r[s..m]中记录的关键字除 H.r[s] 之外
    //均满足堆的特征,本函数自上而下调整 H.r[s]
    //的关键字,使 H.r[s..m] 也成为一个大顶堆
     rc = H.r[s];    // 暂存 H.r[s] 
     for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子
    自上而下的筛选过程;
     }
     // 自上而下的筛选过程
      if ( j<m && H.r[j].key>H.r[j+1].key )  ++j;     
             // 左/右“子树根”之间先进行相互比较
             // 令 j 指示关键字较小记录的位置
      if ( rc.key <= H.r[j].key )  break; 
           // 再作“根”和“子树根”之间的比较,
           // 若“>=”成立,则说明已找到 rc 的插
           // 入位置 s ,不需要继续往下调整

      H.r[s] = H.r[j];   s = j;    
        // 否则记录上移,尚需继续往下调整

    H.r[s] = rc;  // 将调整前的堆顶记录插入到 s  (注意插入的位置为s j=2*s)
} // HeapAdjust
  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017