二叉排序树_二叉排序树怎么构造_怎样构造二叉排序树

今天的收获就是二叉搜索树，“好记性不如烂笔头”，写下来加深一下印象；

1、首先是了解了二叉搜索树（Binary Sort Tree）又称二叉查找树，亦称二叉排序树。二叉排序树 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

2、接下来看的是查询二叉搜索树，查询二叉搜索树的内容比较多；

（1）查找：即是查询关键字，若存在，返回该节点的指针；否则，返回空；这个书中给了两段伪码，迭代、递归随意；

（2）最大关键字及最小关键字元素：顾名思义，肯定是二叉搜索树的最大最小值，以最大关键字为例，一直查询树的右孩子，直到改节点无右孩子为止，该节点就是最大关键字，当然，最小关键字同理；

（3）后继与前驱：对一个节点来说，最大的小于该节点值的即是前驱，最小的大于该节点值的即是后继。以后继为例，如果该节点的右子树不为空，那么后继就是右子树中最小关键字元素；若是该节点右孩子不存在，这时，只需由该节点往上寻找，直到这个节点是其父节点的左孩子即可。当然，前驱也是类似情况；

3、然后看的是插入与删除，这一节也挺关键的；

（1）插入：插入我们都知道，建立的二叉搜索树就是一个节点一个节点的进行插入的。二叉排序树遍历该树，找到适合的位置，就将节点插入了；

（2）删除：这个就比较复杂了，考虑的情况比较多；

一：该节点是叶子节点，这个删除是最简单的，将其改为空，并修改父节点即可；

二：该节点只有一个孩子（左孩子或右孩子，这个在具体实现时不同操作），这时只要将该节点的孩子节点放在该节点上，同时修改该节点的父节点即可；

三：该节点有两个孩子，这个是最复杂的，不过由于后来没思路，编代码的时候参考一位仁兄，他的思想是直接找到该节点的后继节点，将其删除（这个后继节点一定是存在的，因为它有两个孩子啊，至少右孩子就比它大，故而存在），然后将该节点的值改为后继节点的值即可（当然提前把后继的值留下...）

4、最后看的是随机构建二叉搜索树，貌似这样二叉树的高度比较理想，平均深度是lgn，不会发生“过激”的情况。

这一章是《算法导论》的内容，书中写得还是比较详细的，伪码也给了不少，建的二叉搜索树如下；

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-23871-1.html