ds18b20 二叉树搜索算法
1单总线技术
单总线技术搜索 ROM 的过程是主设备获取单总线上从器件的注册码的过程,
是一种简单的三步操作过程的重复,即先读一位,其次读该位的反码,然后再
写一位,选中其中的一部分器件(详见参考文献[1])。重复执行这三步操作,
可获得设备注册码其余各位。
根据每两次读的数据可作如下判断:
00:总线上有器件,且它们的注册码在该位既有“1”,也有“0”;
01:总线上器件的注册码在该位是“1”;
10:总线上器件的注册码在该位是“0”;
11:总线上没有器件。
2二叉树搜索算法
二叉树(binarytree)是 n(n≥0)个结点的有限集合,由一个根结点以
及两棵互不相交的、分别称为左子树和右子树的二叉树组成,且左子树和右子
树有严格的区分。
遍历一棵二叉树就是按某种次序系统地访问二叉树上的所有结点,并且每个
结点只允许访问一次。遍历运算的关键在于访问结点的次序,应保证二叉树上
每个结点均被访问且仅被访问一次(详见参考文献[2])。
3二叉树搜索算法的应用
根据多个单总线器件注册码所构成的数据结构和二叉树的特点,可认为单总
线上所有器件注册码构成了一个深度为 64 的二叉树(相关资料见参考文献
[2]),在遍历二叉树的过程中可根据读取的两次数据判断结点是左子结点、右
子结点还是叶子结点,即:
00:表示既存在左子结点,也存在右子结点,该位有“0”,也有“1”;
01:表示只存在左子结点,该位为“0”;
10:表示只存在右子结点,该位为“1”。
11:表示不存在子结点,也就说明没有从器件挂接在总线上。