二叉搜索树简单解析


		前天的笔试题，遇到了二叉搜索树，当然题很简单，回来后没事做写写吧。
 
 
二叉搜索树（又叫二叉排序树）的关键字key，一节点的左子树若存在，所有的key都是小于该节点的，同理右子树是大于该节点的。
 
插入、查找很简单，递归的在左右子树上找
 
 
删除复杂些，首先考虑只有单个子树的情况，比如是左子树，那就把左子树移上来，再将该节点删掉。
 
如果左右子树都有，从二叉搜索树的性质可知，选左子树中最大的 或 右子树中最小的，移到该节点位置，仍然还是一颗二叉搜索树。
 
找到了要交换的节点，又有几种情况要考虑（详见代码）
 
 
嘛，既然有二叉平衡树这种高级结构了，搜索树也没什么技术含量，我都不好意思要分
 
 
ps.封装成类是一个愉快的事

补充：综合编程 , 其他综合 ,