第三节四叉树 假定一个平面图形是黑白的二值图形， 即组成图形象素阵列的仅有黑色象素值1，白 色象素值0，设表现图形的象素阵列由2n×2” 个象素组成。 表示该图形的四叉树结构可以如下形成： 图形显然包括2nX2的正方形中，这个正方 形是四叉树的根结点。 若图形整个地占据这个正方形，则图形 就用该正方形表示，否则将该正方形均分为 四个小正方形，每个小正方形边长为原正方 形边长的一半.它们是根结点的四个子结点， 可编号为0,1,2,3
第三节 四叉树 假定一个平面图形是黑白的二值图形, 即组成图形象素阵列的仅有黑色象素值1,白 色象素值0,设表现图形的象素阵列由2 n×2 n 个象素组成。 表示该图形的四叉树结构可以如下形成: 图形显然包括2 n×2 n的正方形中，这个正方 形是四叉树的根结点。 若图形整个地占据这个正方形,则图形 就用该正方形表示,否则将该正方形均分为 四个小正方形，每个小正方形边长为原正方 形边长的一半.它们是根结点的四个子结点, 可编号为0,1,2,3
再考查每个小正方形，若整个被图 形占据，则标记相应结点为1，可称为黑 结点。若整个与图形不相交，则标记相 应结点为0，可称为白结点。 若不是上述两情形，即与图形部分 相交，则称相应结点是灰结点并将其一 分为四。当再分生成小正方形边长达到 一个象素单位时，再分终止，此时一般 应将仍是灰结点的改为黑结点，如此形 成了平面图形的四叉树表示
再考查每个小正方形,若整个被图 形占据,则标记相应结点为1,可称为黑 结点。若整个与图形不相交,则标记相 应结点为0，可称为白结点。 若不是上述两情形，即与图形部分 相交，则称相应结点是灰结点并将其一 分为四。当再分生成小正方形边长达到 一个象素单位时，再分终止，此时一般 应将仍是灰结点的改为黑结点，如此形 成了平面图形的四叉树表示
0 2 3 2 3 0 2 3 (1)原图形 (2)第一层分等分 (3)第二层等分 1 1 (4)四叉树：灰结点 黑结点 白结点
四叉树的存储结构，即规则方式、线 性方式和一对四方式，相应的四叉树也就 称为规则四叉树、线性四叉树和一对四式 四叉树。 规则四叉树是用五个字段的记录来表 示树中的每个结点，其中一个用来描述结 点的特性，即是灰、黑、白三类结点中的 哪一种。其余四个用于存放指向四个子结 点的指针。 线性四叉树以某一预先确定的次序遍 历四叉树形成一个线性表结构 RA'abcdBCD'efgh。其中R表示根，字母 右上角加'表示是灰结点
四叉树的存储结构，即规则方式、线 性方式和一对四方式，相应的四叉树也就 称为规则四叉树、线性四叉树和一对四式 四叉树。 规则四叉树是用五个字段的记录来表 示树中的每个结点，其中一个用来描述结 点的特性，即是灰、黑、白三类结点中的 哪一种。其余四个用于存放指向四个子结 点的指针。 线性四叉树以某一预先确定的次序遍 历四叉树形成一个线性表结构 。 RA’abcdBCD’efgh。其中R表示根，字母 右上角加’表示是灰结点
一对四式四叉树的存储结构每个结 点有五个字段，其中四个字段用来描述该 结点的四个子结点的状态，另一个结点存 放指向子结点记录存放处的指针。四个子 结点对应的记录是依次连续存放的。 0 1 2 3
一对四式四叉树的存储结构 每个结 点有五个字段，其中四个字段用来描述该 结点的四个子结点的状态，另一个结点存 放指向子结点记录存放处的指针。四个子 结点对应的记录是依次连续存放的