你可以看到api的解释：
使用二分搜索法搜索指定列表，以获得指定对象。在进行此调用之前，必须根据列表元素的自然顺序对列表进行升序排序（通过 sort(List)
方法）。
如果搜索键包含在列表中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点
被定义为将键插入列表的那一点：即第一个大于此键的元素索引；如果列表中的所有元素都小于指定的键，则为
list.size()。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。
你的ab经过升序排列在第1位(算是第二位，当然此时的0算第一位了)，那么返回值就应该是-2；
先序非递归算法【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
voidPreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{// 基于方法一
InitStack(S)
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data)
Push(S,T)
T = T->lchild
}
if( !StackEmpty(S) ){
Pop(S,T)
T = T->rchild
}
}
}
【算法2】
voidPreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{// 基于方法二
InitStack(S)
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data)
Push(S, T->rchild)
T = T->lchild
}
if ( !StackEmpty(S) ){
Pop(S,T)
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
【算法】
voidInOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S)
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T)
T = T->lchild
}
if( !StackEmpty(S) ){
Pop(S, T)
Visit(T->data)
T = T->rchild
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。 [Page]
typedef struct stackElement{
Bitreedata
chartag
}stackElemType
【算法】
voidPostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S)
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0)
T = T->lchild
}
while ( !StackEmpty(S) &&GetTopTag(S)==1){
Pop(S, T)
Visit(T->data)
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1) // 设置栈顶标记
T = GetTopPointer(S) // 取栈顶保存的指针
T = T->rchild
}else break
}
}
这是先序遍历树的代码，什么是先序遍历呢，一种按照根-左子树-右子树的顺序遍历树就是先序遍历。CBTType TreeFindNode(CBTType treeNode,String data){
CBTType ptr
if(treeNode==null){//输入根节点为空时
return null
}else{
if(treeNode.data.equals(data)){//根节点等于要查找的数据时
return treeNode
}else{
if((ptr=TreeFindNode(treeNode.left,data))!=null){//从左子树查找，为什么可以用TreeFindNode表示呢？
return ptr
}else if((ptr=TreeFindNode(treeNode.right,data))!=null){//从右子树查找
return ptr
}else{
return null
}
}
}
}
从左子树查找，为什么可以用TreeFindNode表示呢？因为，左子树也可以按照先序遍历的顺序查找的，所以当然可以用TreeFindNode表示，如果你想左子树用中序遍历查找，那么就不可以用TreeFindNode表示。
上述例子的查找过程：
1 --根（2，4，5）--左（3，6，7）--右
2--根（4）--左（5）--右
4--根
5--根
返回
