二叉查找树是一种基本的数据结构。 它的优势在于其高效的查询，排序过程，且它也支持多种操作，如插
入、删除、前趋，后接等。二叉查找树常被用于其他抽象结构的一个基础，比如字典、优先队列、集合、多
集等。总之，就是用处多多。
二叉查找树基本上各种操作的效率跟树的高度都是直接成比例的。所以查找树的结构就非常重要了，平衡的
结构可使得效率更高。这就带来了随机化版本的二叉树。 具体各种操作的分析在这一节中讲，随机化版本的
分析涉及数学很多，放在下一讲中。
这一讲的主要知识点有：1.二叉树基本结构 2.查找操作 3.插入删除操作
1.二叉树基本结构
二叉树的每个节点(node)就是一个对象，每个node里主要有key、卫星数据(就是主要数据)、left(存储左儿
子), right（存储右儿子）,parent（存储父节点）。如果相应节点不存在，则为NULL
二叉查找树的组织方式很简单，当一个节点进来后，与树中节点比较，如果大于当前节点key，就进入它的右
子树，否则进入左子树。知道找到NULL的位置。下面是两个BST的例子
二叉树的一个基本操作是树的遍历。树的遍历也主要有三种：前序、中序、后序。其主要区别看下面中序
的伪代码就可以很好理解了。
INORDER-TREE-WALK(x)
1 if x != NIL
2 INORDER-TREE-WALK(x.left)
3 print x.key
4 INORDER-TREE-WALK(x.right)
中序就是打印的命令放在了左、右递归的中间。 而实际上，根据二叉查找树的性质，中序遍历打印出来的结
构就是所有键值按从小到大顺序排序后的结果！
树的遍历作为一种遍历，当然其时间复杂度就是Θ(n)
2.查找操作
二叉查找树作为一种查找树，当然常见操作就是查找了。 查询除了常用的查找某个关键字之外，还有找最
大、最小、后续、前趋关键字。对高度为h的的树，这些操作的时间复杂度都是Θ(h)
查找关键字
TREE-SEARCH(x; k)
1 if x == NIL or k == x.key
2 return x
3 if k < x.key
4 return TREE-SEARCH(x.left; k)
5 else return TREE-SEARCH(x.right; k)
其过程是沿着树的根节点比较着往下找，大则右，小则左。所以时间复杂度是O(h)
最大关键字与最小关键字
TREE-MINIMUM(x)
1 while x.left != NULL
2 x = x.left
3 return x
TREE-MAXIMUM(x)
1 while x.right != NULL
2 x = x.right
3 return x
最大与最小是分别沿着右子树或左子树一直下降，时间复杂度O(h)
前趋和后续
TREE-SUCCESSOR(x)
1 if x.right != NULL
2 return TREE-MINIMUM(x.right)
3 y = x.p
4 while y != NIL and x == y.right
5 x = y
6 y = y.p
7 return y
后继操作的过程需要分为两种情况：1 存在右子树，则是右子树当中的最小值(比它大的元素里面的最小值，合
理！)；2 只有左子树，则顺流而上，找到第一次做左子树的地方。图例见下：case1-15 case2-13
前趋的过程与后继是对称的，伪代码就不写了，后面附的代码里面会有。
3.插入删除操作
插入与删除操作因为需要改变一些东西，且还要维持数据结构的性质，稍微会复杂一些
TREE-INSERT(T; z)
1 y = NULL
2 x = T.root
3 while x != NULL
4 y = x
5 if z.key < x.key
6 x = x.left
7 else x = x.right
8 z.p = y
9 if y == NULL
10 T.root = z // tree T was empty
11 elseif z.key < y.key
12 y.left = z
13 else y.right = z
在伪代码里面，y始终指向x的父节点。实现主要注意当是空树的时候，需要将当前节点作为根。否则就是一路下
去直到找到空位置
删除操作比较复杂，需要分为三种情况，所以这里先做分析。 三种情况对应不同的操作方法，1是既没有左子树
也没有右子树 2只有一个子树 3同时有两个子树。对于1直接操作即可； 对于2删除当前节点时，将其子树接到
节点的父节点上去；对于3，需要找到待删除节点的后继节点,然后用这个后继节点替代当前节点并删除那个后继
节点之前的位置。 注意：找到的后继节点是没有左子树的否则它的前趋就不可能是那个待删除节点了。下面用
图示例这三种情况：
下面给出伪代码：
TREE-DELETE(T, z)
1 if left[z] = NIL or right[z] = NIL
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] = NIL
5 then x ← left[y]
6 else x ← right[y]
7 if x = NIL
8 then p[x] ← p[y]
9 if p[y] = NIL
10 then root[T ] ← x
11 else if y = left[p[y]]
12 then left[p[y]] ← x
13 else right[p[y]] ← x
14 if y = z
15 then key[z]← key[y]
16 copy y’s satellite data into z
17 return y
其过程与上面的三种情况顺序是不同的。 首先y是记录需要删除的节点的，即y必然有一个子树是空的；x是记录
y的一个子节点的，若有就是相应子节点，没有则默认是右边的(Row 6); Row9-13是执行将删除点父节点的更
新操作。Row14-16 是如果需要是替换的情况作一个替换。
下面附上C++实现的BST：
本文链接：http://www.cnblogs.com/soyscut/p/3410129.html，转载请注明。
这一篇我的偶像Jackei 致敬：
（关于偶像的问题，发表一下自己的看法，我觉得每个人都应该有“偶像”，偶像是标杆和奋斗目标。关于有些人拿比尔盖茨 和 自己当偶像的，要么活在梦里，要么活在自己的世界，我只能 呵呵 了。）
其实，从刚开始做测试就有学习自动化（基于UI 的web自动动化测试），理解上一直处于非常皮毛的状态。再次的深入学习并实践自动化大概从半年前开始。边学习边总结是我的一贯学习方式。
Jackei 的这篇文章我了好几遍，虽然将的内容并不高深，但随着自己自动化水平的提高，每次看完也会一新体会。基于这篇文章，扩展的来谈一下自己对几种自动化测试模型的理解。
线性测试
通过录制或编写脚本，一个脚本完成用户一套完整的操作，通过对脚本的回放来进行自动化测试。
这是早期进行自动化测试的一种形式。
脚本一
import time
driver = webdriver.Firefox()
driver.get("http://passport.cnblogs.com/login.aspx?ReturnUrl=http://www.cnblogs.com/fnng/admin/EditPosts.aspx")
driver.find_element_by_id("tbUserName").send_keys("admin")
driver.find_element_by_id("tbPassword").send_keys("123456")
driver.find_element_by_id("btnLogin").click()
......
driver.quit ()
脚本二
import time
driver = webdriver.Firefox()
driver.get("http://passport.cnblogs.com/login.aspx?ReturnUrl=http://www.cnblogs.com/fnng/admin/EditPosts.aspx")
driver.find_element_by_id("tbUserName").send_keys("user")
driver.find_element_by_id("tbPassword").send_keys("456123")
driver.find_element_by_id("btnLogin").click()
......
driver.quit ()
通过上面的两个脚本，我们很明显的发现它的问题：
一个用例对应一个脚本，假如界面发生变化，用户名的属性发生改变，不得不需要对每一个脚本进行修改，测试用例形成一种规模，我们可能将大量的工作用于脚本的维护，从而失去自动化的意义。
这种模式下数据和脚本是混在一起的，如果数据发生变也也需要对脚本进行修改。
这种模式下脚本的可重复使用率很低。
模块化与库
我们会清晰的发现在上面的脚本中，其实有不少内容是重复的；于是就有了下面的形式。
from selenium import webdriver
import time
#登录模块
def login():
driver.find_element_by_id("tbUserName").send_keys("user")
driver.find_element_by_id("tbPassword").send_keys("456123")
driver.find_element_by_id("btnLogin").click()
#退出模块
def quit():
..............
driver = webdriver.Firefox()
driver.get("http://passport.cnblogs.com/login.aspx?ReturnUrl=http://www.cnblogs.com/fnng/admin/EditPosts.aspx")
#调用登录模块
login()
#其它个性化操作
......
#调用退出模块
注意，为了省事我把代码写在了一个文件里，真正的实施时需要把模块放到其它文件进行调用。还有上面代码不能完整运行。
通过上面的代码发现，我们可以把脚本中相同的部分独立出来，形成模块或库；当脚本需要进行调用。这样做有两个好处：
一方面提高了开发效率，不用重复的编写相同的脚本。
另一方面提高了代码的复用。
数据驱动
数据驱动应该是自动化的一个进步；从它的本意来讲，数据的改变（更新）驱动自动化的执行，从而引起结果改变。这显然是一个非常高级的概念和想法。
其实，我们能做到的是下面的形式。
d:\abc\data.txt
没有评论:
发表评论