1、二叉排序树
二叉排序树是这样一棵树
a.空树
b.
1)如果左子树不空，左子树的所有节点的值小于其根节点的值
2)如果右子树不空，右子树所有节点的值大于其根节点的值
3)其左右子树都是二叉排序树
2、遍历
对于拥有指针next的数据结构，遍历的时候，一般都是以指针p作为游标进行遍历
一般有2种方式判断游标p是否到尽头
a p==NULL
b p->next==NULL
b的好处是遍历条件结束后，p依然指向最后一个有效节点，但是初始的时候，要对p进行非空判断。
3、查找
查找一般有几种目的
a 简单查找只为获取一个节点的值。
b 查找并且删除，一般这种情况下，不但要获取该节点的指针，还要获取该节点的前驱节点。
c 查找某一个位置并且插入。
也是查找一个节点，通常查找不到，但此时却可以找到适合插入该节点的合适位置。
4、查找插入（假定没有重复，所以一般是找不到该结点）
采用某个限定条件，对遍历的游标进行检查。当游标条件不符合的时候，遍历停止。
而此时我们要查找的位置一般是该游标的前一个位置，所以遍历的时候一般也要一个指针来保存其前驱结点的位置（有时候不需要，如下）。
比如在链表最后一个结点插入
void append(LinkNode *head, ElemType item) { //assume head!=NULL LinkNode *p=head->next; LinkNode *pre = p; while(p){p=p->next;pre=p;} pre->next=(malloc)(sizeof(LinkNode)); pre->next->element=item; p->next->next = NULL; }
这里比较特殊，pre->next 就是p所以可以省略一下
void append(LinkNode *head, ElemType item) { //assume head!=NULL LinkNode *p=head->next; while(p){p=p->next;} p=(malloc)(sizeof(LinkNode)); p->element=item; p->next = NULL; }5、查找删除
查找删除和查找插入相似，都是采用某个限定条件，对遍历的游标p进行检查。当游标条件不符合的时候，遍历停止。
不同的是，查找删除能找到一个节点。
不过，删除时候要操作的依然是p的前驱，所以依然需要保存其前驱。
6、二叉排序树的查找
a、简单查找
BSTree SearchBST(BSTree T, KeyType key) { if ((!T)||EQ(T->data.key,key)) return T; else if LT(key, T->data.key) return (SearchBST(T->lchild,key)); else return (SearchBST(T->rchild,key)); }b.查找插入为了插入目的的查找，一方面需要和简单查找一样，需要一个返回值来区别是否找到该节点。
除此以外，如上面讨论，而且要一个节点返回该节点的前驱节点。
也就是该函数需要2个输出，因此仅仅依靠一个返回值已经不能满足要求，因此我们需要加一个输出参数。
与此同时，由于在某种情况下，要输出该树的前驱节点，因此还函数还需要一个该节点T的前驱，作为另一个输入参数。to be continued