二叉树算法在单总线上的C51软件实现

引 言

单总线技术是将地址线、数据线和控制线合成一根线，并允许在该线上挂接多个单总线器件。其搜索ROM命令可以在线识别挂接在总线上器件的注册码和器件的类型，并可在线确定总线上的器件数量；但是，对于多个在线器件，毫不遗漏搜索出每个器件的注册码比较困难，在本文中，作者把多个器件注册码的数据结构抽象为一种二叉树，从而通过二叉树算法实现对在线所有的单总线器件的注册码的自动搜索，并能根据注册码自动识别器件类型和总线上的器件数量。

1 单总线技术

单总线技术搜索ROM的过程是主设备获取单总线上从器件的注册码的过程，是一种简单的三步操作过程的重复，即先读一位，其次读该位的反码，然后再写一位，选中其中的一部分器件（详见参考文献[1]）。重复执行这三步操作，可获得设备注册码其余各位。

根据每两次读的数据可作如下判断：

00：总线上有器件，且它们的注册码在该位既有“1”，也有“0”；

01：总线上器件的注册码在该位是“1”；

10：总线上器件的注册码在该位是“0”；

11：总线上没有器件。

2 二叉树搜索算法

二叉树（binary tree）是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成，且左子树和右子树有严格的区分。

遍历一棵二叉树就是按某种次序系统地访问二叉树上的所有结点，并且每个结点只允许访问一次。遍历运算的关键在于访问结点的次序，应保证二叉树上每个结点均被访问且仅被访问一次（详见参考文献[2]）。

3二叉树搜索算法的应用

根据多个单总线器件注册码所构成的数据结构和二叉树的特点，可认为单总线上所有器件注册码构成了一个深度为64的二叉树（相关资料见参考文献[2]），在遍历二叉树的过程中可根据读取的两次数据判断结点是左子结点、右子结点还是叶子结点，即：

00：表示既存在左子结点，也存在右子结点，该位有“0”，也有“1”；

01：表示只存在左子结点，该位为“0”；

10：表示只存在右子结点，该位为“1”。

11：表示不存在子结点，也就说明没有从器件挂接在总线上。

在遍历二叉树时，记录所走的路径和搜索到的叶子结点数,可以得到从器件的注册码和从器件数量。

第一次搜索从器件的注册码时，如果左子结点和右子结点都存在，需要记录该分叉结点的深度，并沿左子树的方向向下搜索，当搜索深度达到64时，获得一个从器件的注册码，并取出该搜索路径最后的分叉结点的深度，然后主器件执行第二次搜索过程。在该搜索过程中，如果结点的深度值小于最后一个分叉结点的深度，则发送上次搜索到的在最后一个分叉结点前的注册码的相应位；如果结点的深度值等于最后一个分叉结点的深度，则发送上次搜索到的在最后一个分叉结点处发送的数据的反码，并且删除该分叉结点的记录，如在后面的搜索中遇到分叉结点，同样需要记录分叉结点的深度。这样，每搜索到一个深度为64的叶子结点，就会得到一个从器件的注册码，一直搜索到记录中没有分叉结点为止。

图1 软件流程图

如表1所示，设有三个从器件1、2和3，主设备第一次读取的数据是“10”，可知从器件的注册码的第一位都为“0”，主设备写“0”；第二次读取的数据是“00”，可知在线从器件的注册码在该位既有“0”，也有“1”，记下该分叉结点的深度（记录的位1置“1”）；主设备写“0”，搜索左子树结点，选中从器件1和从器件3（如主设备写“1”则选中从器件2），第三次读取的数据是“01”，可知选中的从器件的注册码在该位都是“1”，主设备写“1”，第四次读取的数据是“00”，从器件的注册码在该位既有“0”，也有“1”，记下该分叉结点的深度（记录的位3置“1”），主设备写“0”，选中从器件1，依次类推搜索从器件1的其余结点，当深度达到64时，即获得从器件1的注册码；从记录中找出最后一个分叉结点，即记录的位3，重新从根结点开始搜索，在分叉结点之前，每读两次数据后，发送前一个从器件（从器件1）注册码的相应位，在分叉结点2，发送前一个从器件的注册码相应位的反码“1”，选中从器件2和3，搜索右子树结点，并把记录分叉结点的相应位（记录的位3）清“0”，依次读取从器件2和3注册码的剩余位；并在记录中记录相应位，按照同样的方法，可获得从器件2的注册码，直到记录中的各位都为“0”时，搜索结束。由搜索得到数据可知，从器件1、从器件2和从器件3的注册码的前8位（家族码）分别是：28H、20H和2CH，所以它们分别是温度传感器DS18B20、模数转换芯片DS2450和单路数字电位器DS2890。

表格 1 搜索注册码

4 软件设计

流程图如图1所示，number[64 ,0 ]表示number为64 位的变量，初始化为0，存储从器件的ROM 序列号，Record 用来记录存在分支的结点位置，list[n]表示记录中的第n位，初始化为“0”，n 表示搜索到的位数。

下面是部分软件：

/**自动识别多个在线芯片序列号***/

void find_serial()

{char n,j,m,k,record,end,ks,mm,nn;

m=0;end=0;

reset_num(); //复位单总线

command_num(0x0F0,0x08);//发搜索命令

while (1)

{for (n=1;n<65;n++)//读深度为64的二叉树

{k=(n-1)/8; //每8位放到数组中

j=Read_serial(0x02);//连续读两次数serial[k]=serial[k]>>1;

if(j==0x01) //第一次为1，第二次为0

{serial[k]=serial[k]|0x80;//存该位1

command_num(0x01,0x01);//发送1

read_bit[n]=0;

}

if (j==0x02) //第一次为0，第二次为1

{serial[k]=serial[k]&0x7f; //存该位0

command_num(0x00,0x01); //发送0

read_bit[n]=0;

}

if(j==0x00) //两次都为0，记录分叉点

{if (n

{ks=(serial1[k]>>((n-1)%8))&0x01;

/*发前一个已搜索器件注册码*/

command_num(ks,0x01);

serial[k]=serial[k]|0x80;//存该位

if (ks==0) {serial[k]=serial[k]&0x7f;}

}

else if (n>record)//深度是大于64

{command_num(0x00,0x01);

read_bit[n]=1;//记录

serial[k]=serial[k]&0x7f;

}

else

{ks=(n-1)/8;mm=(n-1)%8;

nn=serial1[ks]>>mm;

if ((nn&0x01)==1)

{serial[ks]=serial[ks]&0x7f;

command_num(0x00,0x01);

}

if ((nn&0x01)==0)

{serial[ks]=serial[ks]|0x80;

command_num(0x01,0x01);

}

read_bit[n]=0;//清记录

}

}

}

for(nn=0;nn<8;nn++)

{serial1[nn]=serial[nn];}

if (n>64)

{for (j=64;j>0;j--)//从末尾搜索记录

{if (read_bit[j]!=0)

{record=j;n=1;

read_bit[j]=0;

break;

}

else

{record=0;}//清记录

}

}

if (record!=0)//如有分叉点，重新搜索

{reset_num();

command_num(0x0F0,0x08);

}

else

{break;}

}

}

5 结论

在作者设计的温室控制系统的软件中,当系统每次上电时,微处理器首先应用二叉树算法搜索在线的所有单总线器件的注册码，并区分器件类型；对于撤离的或新增加的从器件,系统可以动态的获得它的注册码，实现了对从器件的动态管理。该算法适用于任何具有1-Wire 接口特性单总线器件。