树的应用—二叉排序树

二叉排序树可以为空树，也可以为非空树，为非空树时有以下特点

• 若左子树非空，则左子树上所有结点值均小于根结点的值
• 若右子树非空，则右子树上所有结点值均大于根结点的值
  注意这里没有等于，也就是说二叉排序树中默认是没有相同值结点的
• 左，右子树本身也是一颗二叉排序树

二叉排序树进行中序遍历后，序列即为一个递增的有序序列

二叉排序树

查找操作
二叉树非空时，查找根结点，若相等则查找成功；
若不等，则小于根结点查左子树，大于查右子树
当查找到叶子结点还未找到，查找失败
代码实现，看懂就行

查找操作
插入操作
若二叉排序树为空时，直接插入结点
若二叉排序树非空时，值小于根结点值时，插入左子树；大于插入右子树，等于不能插入。（使用递归来实现）

int BST_Insert(BiTree &T,KeyType k){
    if (T == NULL){
        T = (BiTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if (k == T->key){
        return 0;
    }
    else if (k < T-key){
        return BSTNode(T->lchild,k);
    }
    else if (k > T-key){
        return BSTNode(T->rchild,k);
    }
}

构造二叉排序树
构造的过程是一个动态的过程，不断的调用插入函数来进行构造
读入一个元素并建立结点，若二叉树为空将其作为根结点；
若二叉排序树非空，小于插左子树，大于插右子树。

void Create_BST(BiTree &T,keyType str[],int n){
//str存放插入的元素，n为插入的个数
     T = NULL;
     int i = 0;
     while(i<n){
        BST_Insert(T,str[i]);
        i++;
     }
}

删除

• 若删除结点为叶子结点，则直接删除
• 若删除结点z有一颗子树y，那么选取这棵子树y代替该结点z的位置
• 若删除结点z有两颗子树，直接让z的中序遍历直接后继x，直接代替z的位置，然后执行删除x的操作，以此类推。最终会变成上面的两种情况。

删除一个结点，然后再插入该结点，所得到的二叉排序树可能会不一样