二、二叉搜索树的插入与删除

树形结构的一个重要应用是用来组织索引，二叉搜索树是适用于内存储器的一种重要的树形索引。二叉搜索树里每个结点的左子树中所有结点的关键码值都小于该结点的关键码值，而右子树中所有结点的关键码值都大于该结点的关键码值。二叉树的插入和删除需要保证插入和删除以后仍符合二叉搜索树的定义。

1、插入是这样进行的：将待插入结点的关键码值与树根的关键码值比较，若待插入的关键码值小于树根的关键码值，则进入左子树，否则进入右子树。在子树里又与子树根比较，如此进行下去，直到把新结点插入到二叉树里作为一个新的树叶。
    对于给定的关键码集合，为建立二叉搜索树，可以从一个空的二叉搜索树开始，将关键码一个个插进去。
    将关键码集合组织成二叉搜索树，实际上起了对集合里的关键码进行排序的作用，按中序周游二叉搜索树，就能得到排好的关键码序列。

2、从二叉搜索树里删除一个结点时，不能把以这个结点为根的子树都删除掉，只能删除掉这一个结点，并且还要保持二叉搜索树原来的性质。
    设p，p1，r是指针变量，p↑表示s要删除的结点，p1↑表示p↑的父母结点，则删除可以按如下规定进行：若结点p↑没有左子树，则用右子树的根代替被删除的结点p↑。若结点p↑有左子树，则在左子树里找按中序周游的最后一个结点r↑，将r↑的右指针置成指向p↑的右子树的根，然后用结点p↑的左子树的根去代替被删除的结点p↑。
    改进的删除算法：设p，p1，r是指针变量，p↑表示s要删除的结点， p1↑表示p↑的父母结点，则删除可以按如下规定进行。若结点p↑没有左子树，则用右子树的根代替被删除的结点p↑。若结点p↑有左子树，则在左子树里找按中序周游的最后一个结点r↑，将r↑的右指针置成指向p↑的右子树的根，然后用结点r↑去代替被删除的结点p↑。