二叉搜索树
二叉搜索树的定义
查找
由于非递归函数执行效率高 可以将尾递归改为迭代函数
查找最大值和最小值
代码如下
二叉搜索树的插入
关键是找到元素插入的对应位置 可以采用Find类似的方法
二叉搜索树的删除
要考虑三种情况;
要删除的是叶结点 直接删除 并修改其父结点的指针置为NULL
要删除的有一个孩子其父结点要指向删除结点的孩子结点
要删除的有两个孩子用另外结点代替被删除结点 右子树的最小元素或者左子树最大元素 因为最大和最小元素一定在根的最右边或最左边 其一定没有两个孩子