二叉搜索树

定义

二叉搜索树，也称有序二叉树,排序二叉树，是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 任意节点的左、右子树也分别为二叉查找树。

4. 没有键值相等的节点。

二叉树的存储

定义结构体，以链式来存储二叉树

struct BSTree
{
  int key;  //记录键值
  BSTree *left,*right,*parent;
};

插入

bool insert(int value)
{
  /*初始化*/
  BSTree *node = new BSTree;
  node -> key = value;
  node -> left = NULL;
  node -> right = NULL;
  if(root == NULL)  //如果树为空，则node作为根
  {
    node -> parent = NULL;
    root = node;
    return true;
  }
  BSTree *cur,*pre;  //记录当前节点和上一节点
  cur = root;
  pre = NULL;
  while(cur != NULL)
  {
    if(value > cur -> key)
    {
      pre = cur;
      cur = cur -> right;
    }
    else if(value < cur -> key)
    {
      pre = cur;
      cur = cur -> left;
    }
    else return false;  //如果树中已有此键值，插入失败
  }
  node -> parent = pre;
  if(value > pre -> key)  pre -> right = node;
  else pre -> left = node;
  return true;
}

查找

两种查找方法
1.迭代查找

BSTree *find(int value)
{
    BSTree *cur = root;
    while(cur)
    {
        if(node -> key < value)
        {
            cur = cur -> right;
        }
        else if(node -> key > value)
        {
            cur = cur -> right;
        }
        else return cur;
    }
    return NULL;
}