什么是二叉查找树：
 根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。
 本文章重点来讨论一下关于二叉查找树删除节点的问题。
 有一下二叉查找树，如图：
 
 在删除节点的时候我们只需考虑一下三种情况：
 （1）要删除的节点是叶子结点，如图：
 
 （2）要删除的节点有左节点但是没有右节点，或者有右节点但是没有左节点，如图：
 
 （3）要删除的节点既有左节点又有右节点，在这种情况下，我们只需要将找到待删节点的右子树中值最小的节点，将其删除并且获取其值，并用其值替换待删节点的值即可。如图：
 
 如上图所示，如果要删除节点7，则需寻找其右子树中节点值最小的9，并且该值一定位于该右子树的最左子节点；但是还有一种情况，如图一右子树没有左节点，但是只有右节点，这种情况就回到了前面的第二种情况。
 具体代码如下：注意Node类是一个内部类，在使用时注意方法。
 
package com.zc.algorithm;

public class BinarySortTree {

    public class Node{
        int value;
        Node left;
        Node right;

        public Node(int  value)
        {
            this.value = value;
        }
        public void add(Node node)
        {
            if(node == null)
            {
                return;
            }
            //判断传入的节点的值比当前子树的根节点的值大还是小
            if(node.value < this.value)
            {
                //如果左节点为空
                if(this.left == null)
                {
                    this.left = node;
                }
                else
                {
                    this.left.add(node);
                }
            }
            else
            {
                if(this.right == null)
                {
                    this.right =node;
                }
                else
                {
                    this.right.add(node);
                }

            }
        }

        /**
         * 前序遍历二叉排序树
         * @param node
         */
        public void middleOder(Node node)
        {
            if(node == null)
            {
                return;
            }
            middleOder(node.left);
            System.out.println(node.value);
            middleOder(node.right);
        }

        /**
         * 查找某一节点
         * @param value
         * @return
         */
        public Node search(int value)
        {
            if(this.value == value)
            {
                return this;
            }
            else if(value < this.value)
            {
                if(this.left == null)
                {
                    return null;
                }
                 return this.left.search(value);
            }
            else
            {
                if(this.right == null)
                {
                    return null;
                }
                return  this.right.search(value);
            }

        }
        public Node searchParent(int value) {
            if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value))
            {
                return this;
            }
            else
            {
                if(this.value > value&& this.left != null)
                {
                    return this.left.searchParent(value);
                }
                else if(this.value < value && this.right !=null)
                {
                    return this.right.searchParent(value);
                }
            }
            return null;
        }
      }


    Node root;
    /**
     * 向二叉排序树中添加节点
     * @param node
     */
    public void add(Node node)
    {
        if(root == null)
        {
            root = node;
        }
      else
        {
            root.add(node);
        }
    }
    public void frontShow()
    {
        if(root != null)
        {
            this.root.middleOder(root);
        }
    }
    public Node SearchNode(int value)
    {
        if(root == null)
            return null;
        else
        {
            return root.search(value);
        }
    }

    public void delete(int value) {
        if (root == null)
            return;
        else
        {
            Node target = SearchNode(value);
            //如果没有这个节点
            if(target == null)
            {
                return;
            }
            //找到他的父节点
            Node parent = searchParent(value);
            //要删除的节点是叶子结点
            if(target.left == null && target.right == null)
            {
                //要删除的节点是节点的左子节点
                if(parent.left.value == value)
                {
                    parent.left =null;
                }
                else
                {
                    parent.right = null;
                }
            }
            //要删除的节点有两个子节点的情况
            else if(target.left != null && target.right != null)
            {
                   //删除右子树中值最小的节点，并获取到该节点的值
                int min = minDelete(target.right);
                //替换目标节点中的值
                target.value = min;
            }
            else
            {
                //需要删除的目标节点的左节点不为空
                if(target.left != null)
                {
                    //要删除的子节点是其父节点的左子节点，并且有左节点而没有有节点
                    if(parent.left.value == value)
                    {
                        parent.left = target.left;
                    }
                    //要删除的子节点是其父节点的右子节点，并且有左节点而没有有节点
                    else
                    {
                        parent.right = target.left;
                    }
                }
                //需要删除的目标节点的右节点不为空
                else
                {
                    //要删除的节点是父节点的左节点，并且有右节点儿没有左节点
                    if(parent.left.value == value)
                    {
                        parent.left = target.right;
                    }
                    //要删除的节点是其父节点的右节点，并且有右孩子没有左孩子
                    else
                    {
                        parent.right = target.right;
                    }
                }


            }

        }
    }

    /**
     * 删除一颗树中最小的节点
     * @param node
     * @return
     */
    public int minDelete(Node node)
    {
        Node target = node;
        while(target.left != null)
        {
            target = target.left;
        }
       delete(target.value);
        return target.value;

    }
    /**
     * 查找父节点
     * @param value
     * @return
     */
    public Node searchParent(int value)
    {
        if(root == null)
        {
            return null;
        }
        else
        {
            return root.searchParent(value);
        }
    }
    public static void main(String[] args)
    {
        int[] arr = new int[]{7,3,10,12,5,1,9};
        BinarySortTree binTree = new BinarySortTree();
        for(int i : arr)
        {
            binTree.add(binTree.new Node(i));
        }
        binTree.delete(7);
        //查看树中的值
        binTree.frontShow();
        //查找
      //  Node node = binTree.new Node(3);
        //Node res = binTree.SearchNode(node.value);
        //System.out.println(res.value);
       // Node temp = binTree.SearchNode(20);
        //System.out.println(temp.value);
    }
}

写在前边
 
上一篇文章我们讲解了二叉树的基础知识，什么是二叉树、二叉树的特点、二叉树的存储方式、二叉树的遍历等。基础归基础，理论归理论。最重要的最终还要和实践挂钩。
 
动画：二叉树有几种存储方式？(上)
 
今天这篇主要分享一下二叉树的一些简单应用，二叉树涉及到的很多应用也是有难度的，比如红黑树、AVL 树、B+树等，这节不会涉及到。还需要自行深入探索。本篇希望能够给你带来二叉树的应用思考。
 
我们都知道上一节分享到了二叉树的遍历，那么二叉树还能干什么，数据结构之所以为数据结构，对数据进行操作的，查找、删除、插入等，那么二叉树对于这些操作是否更高效呢？
 

 
思维导图
 

 
 
1、什么是二叉查找树？
 
二叉树中能够实现快速插入、删除、查找的特殊二叉树就是二叉查找树了。前边我们讲了数组、链表、二分查找等，以后的文章还会有哈希表、跳表等也是用于数据的插入、查找等，那么二叉查找树又有哪些优势呢？
 
那什么是二叉查找树？为何实现快速的插入、删除操作？有了上一篇文章的基础，都是为这篇的二叉查找树做铺垫。二叉查找树的由来都是由二叉树的特点决定的。
 
但是二叉查找树又对其进行改进，要求在二叉查找树中左子节点必须小于根节点，而右子节点则大于根节点，这种特殊的二叉树就叫做二叉查找树。
 

 二叉查找树的定义非常简单，那么下面我们就见识见识二叉查找树的各种操作。
 

 
2、二叉查找树的插入操作
 
二叉查找树如何插入一个节点元素？因为们知道二叉查找树的特点，左子节点小于根节点右子节点大于根节点。插入一个元素，首先让该元素和根节点比较，如果小于根节点，就插入到左子节点位置，如果左子节点有数据，就继续和插入的数据比较大小，直到当前结点为叶子节点位置 —— 整个过程也是一个递归的过程。
 
动画实现：
 
 
性能分析：
 
 
 
插入操作的时间复杂度跟整棵树的高度成正比，时间复杂度为 0(log2n)。
 
 
代码实现：
 JavaScript 版本
 
 
Java 版本
 
 
3、二叉查找树的查找操作
 
查找一个节点元素同样也是根据二叉查找树的特点进行查找，首先和根节点进行比较大小，小于根节点就在左子节点进行递归，否则在右子节点进行递归查找。如果查找到该元素与某节点相同，则可以返回该节点，否则继续递归直到查找完毕没有查找到。
 
动画实现：
 

 性能分析：
 
 
 
查找的时间复杂度同样和二叉查找树的高度成正比，为 O(log2n)。
 
 
代码实现：
 JavaScript 版本
 
 Java 版本
 
 
4、二叉查找树的删除操作
 
对于删除，我们想一想，会多多少少涉及一些边界条件。比如，二叉查找树只有一个根节点或者删除二叉查找树的叶子节点以及中间结点，我们写代码的时候要做的就是分别判断这几种情况，然后进行一一处理，这样说，逻辑听起来更清晰一点。
 
情况一：如果我们要删除树中的节点没有子节点，也就是说我们删除的节点为叶子节点的话，我们直接将叶子节点的父节点指向删除节点的指针设置为 null。
 
动画实现：
 
 
性能分析：
 
 
 
删除操作同样也是如此，时间复杂度为 O(log2n)。
 
 
情况二：第二种情况就是，如果删除的节点下正好有一个节点（左子节点或者右子节点），直接将删除节点的父节点直接指向该删除节点的子节点。
 
动画实现：
 
 
情况三：如果删除的节点下有两个子节点就有点小复杂了，我们先来看如何操作，然后再解释原因。先将找到删除节点的右子树中递归找到最小的节点元素，将其替换我们要删除的节点。
 
因为删除节点的右子树最小的节点也要比删除节点的左子树要大，而且最小节点没有叶子节点，所以替换后还是符合二叉查找树的特点。
 
动画实现：
 

 代码实现：
 JavaScript 版本
 
 Java 版本
 
 
通过上边二叉树的三种操作，我们做一个总结，为什么各种操作的不相同，都是朝着什么方向去变化的？对了，无论是插入还是查找、删除，都是能够让二叉查找树变化后的结构还能够具备二叉查找树的特点（左子节点小于根节点，右子节点大于根节点）。
 
5、重复数据怎么办？
 
以上我们存储的只是不重复的数据，如果我们数据中有重复数据怎么进行操作呢？
 
我们有以下几种方式进行优化，我们可以用数组和链表等动态的数据结构充当节点，这样就可以把重复的数据存储到一个节点上。
 
 
还有一种策略就是我们把重复的数据当做大于根节点处理，也就是存储到右子树上。
 
 
但是我们的查找和删除要优化下，如果查找一个元素，查找到了，但是需要继续往下查找，因为可能存在重复的数据。删除也是同样的道理，删除一个元素，删除之后继续查找是否还存在重复数据，然后对其重复数据进行删除。
 

 
6、二叉查找树的性能
 
上边我们分别对二叉查找树的插入、删除、查找的时间效率进行了分析，也说了时间效率和树的高度成正比，那么问题来了，树的高度如何求？
 
我们运用我们的数学功底算一下，我们先算算一颗完全二叉树有多少的节点，第一层有1个，第二层2个，第三层，4 个，依次类推，第 n 层有多少就要用到等比数列，也就是 2 的n-1次方。
 
我们粗略估算，让等式等于 1 时，此时n = log2n+1，此时我们的 n 代表是树的第几层，然后转化为高度就是h = log2n。
 
上边我们已经分析过，二叉查找树的无论是插入还是查找、删除，都与树的高度成正比，也就是log2n。
 
但是我们要记住一个前提，我们前边分析的树的高度是完全二叉树，如果不是完全二叉树，那么时间复杂度就会发生改变，比如我们一直插入的数据会导致整棵树会失去平衡，退化成链表，时间复杂度就变成了O(n)。
 
 
那么如何解决上边的问题呢？我们需要构建一棵平衡的二叉查找树，每当节点之间快要失去平衡的时候，经过一定的策略，使其达到平衡的状态，这样就算在最坏的情况下也不会退化成链表。比如，AVL 树、红黑树，这些涉及到的比较难，我们本篇不深入了解。
 

 
7、小结
 
今天我们主要讲了二叉树中的一种特殊二叉树，二叉查找树又叫做二叉搜索树。
 
二叉查找树是根据自身的特点，左子节点小于根节点，右子节点大于根节点。从而达到能够实现动态的插入、删除、查找操作，且操作的时间复杂度和树的高度成正比。但是如果一直不平衡的插入，会导致出现二叉查找树退化成链表的情况，所以我们更需要一种平衡的二叉查找树。
 

 
❤️ 不要忘记留下你学习的脚印 [点赞 + 收藏 + 评论]
 
文章+动画写了好几个小时，不妨点赞支持一下。嘻嘻，你不点赞说明你很自私，你怕那么好的文章让别人也看到。开个小小玩笑。
 
 
 
可以关注小鹿公众号：「小鹿动画学编程」，后台回复：“资源”。送你一份小鹿之前自学的资料和拉你进免费学习群哦！
 
 

 
 
作者Info：
 
 
 
【作者】：小鹿
 
 
【原创公众号】：小鹿动画学编程。
 
 
【简介】：和小鹿同学一起用动画的方式从零基础学编程，将 Web前端领域、数据结构与算法、网络原理等通俗易懂的呈献给小伙伴。先定个小目标，原创 1000 篇的动画技术文章，和各位小伙伴共同努力一起学习！公众号回复 “资料” 送一从零自学资料大礼包！
 
 
【转载说明】：转载请说明出处，谢谢合作！~
 

二叉查找树
 
记录自己的学习过程，如果其中有什么错误欢迎各位大佬指正。
 
二叉查找树，又叫二叉搜索树，二叉排序树。他是一种特殊的二叉树，为提高查找效率而诞生的数据结构。
 
二叉查找树的特征
 
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉查找树；
（4）没有键值相等的结点。
 
二叉查找树种的查找
 
由于二叉查找树的特性左子树上的节点永远小于根节点，右子树的节点永远大于根节点，那么在找寻一个节点的时候可以根据大小来决定查找的方向，具体如图：
 
 
二叉查找树的添加
 
添加都时添加在叶子节点上的，只要在查找到合适的叶子节点在对应的位置加上要添加的节点就行。
 
 
二叉查找树的删除
 
相对于查找和添加来说，删除的实现稍微优点复杂，先分为两种情况：
 
一. 删除的不是根节点
 
删除的是普通节点时，又可以分为三种情况：
 
第一种情况：当要删除节点的左子树和右子树都不为空时，因为二叉查找树的所有子树其实也是二叉查找树，所以我们可以将左子树的最大值或者右子树的最小值与该节点替换，为什么是这两个值？因为只有这两个值在根节点上才能满足左节点的所有节点均小于根节点和右节点的所有节点均大于根节点这两种性质。这里我们用右子树的最小值来举例，如图：
 
先找到右子树种最小值
 
 
然后与要删除的节点替换，再移除右子树的最小值就OK
 
 
最后得到
 
 
第二种情况：只存在左子树或者右子树，这种情况我们直接将要删除节点的父节点断开该节点的链接指向该节点的左子树或者右子树就行了
 
 
最后得到
 
 
第三种情况：当删除节点为叶子节点时，这种情况就很简单了，直接删除就行了。
 
二. 删除的是根节点
 
删除的是根节点这种情况，又要分三种小情况：
 
其实删除根节点和删除普通节点区别不大，极少的区别就是在只有左子树和右子树时时用左子树和右子树直接替代整个树就可以了；还有就是不用操作父节点因为并不存在。
 
Java代码实现
 
树节点类
 
public class TreeNode {

    private TreeNode parent;
    private TreeNode left;
    private TreeNode right;
    private int val;

    public TreeNode() {
    }

    public TreeNode(TreeNode parent, TreeNode left, TreeNode right, int val) {
        this.parent = parent;
        this.left = left;
        this.right = right;
        this.val = val;
    }

    public TreeNode getParent() {
        return parent;
    }

    public void setParent(TreeNode parent) {
        this.parent = parent;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val){
        this.val = val;
    }


}
 
二叉查找树类
 
public class BinSearchTree {
    TreeNode root;

    public BinSearchTree(TreeNode root) {
        this.root = root;
    }

    public BinSearchTree() {
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public TreeNode findMin(){
        TreeNode tempNode = root;
        if (tempNode == null){
            return null;
        }
        while (true){
            if(tempNode.getLeft() == null){
                return tempNode;
            }else {
                tempNode = tempNode.getLeft();
            }
        }
    }

    public TreeNode findMax(){
        TreeNode tempNode = root;
        if (tempNode == null){
            return null;
        }
        while (true){
            while (true){
                if(tempNode.getRight() == null){
                    return tempNode;
                }else {
                    tempNode = tempNode.getRight();
                }
            }
        }
    }

    public boolean add(Integer val){
        TreeNode tempNode = root;
        TreeNode treeNode = new TreeNode(null, null, null, val);
        if (root == null){
            root = treeNode;
        }
        while (true){
            if(tempNode.getVal() == val){
                System.out.println("插入值已经存在");
                return false;
            }else if (tempNode.getVal() > val){
                if (tempNode.getLeft() == null){
                    treeNode.setParent(tempNode);
                    tempNode.setLeft(treeNode);
                    return true;
                }else {
                    tempNode = tempNode.getLeft();
                }
            }else {
                if (tempNode.getRight() == null){
                    treeNode.setParent(tempNode);
                    tempNode.setRight(treeNode);
                    return true;
                }else {
                    tempNode = tempNode.getRight();
                }
            }
        }
    }

    //非递归查询
    public TreeNode find(Integer val){
        TreeNode tempNode = root;
        while (true){
            if(tempNode == null){
                System.out.println("查找值不存在");
                return null;
            }else if (tempNode.getVal() == val) {
                return tempNode;
            }else if(tempNode.getVal() > val){
                tempNode = tempNode.getLeft();
            }else {
                tempNode = tempNode.getRight();
            }
        }
    }

    //删除
    public boolean remove(Integer val){

        TreeNode deleteNode = find(val);
        if(deleteNode == null){
            System.out.println("树中没有这个元素");
            return false;
        }
        TreeNode parentNode = deleteNode.getParent();
        if (parentNode == null){//当删除的节点为根节点时
            if (deleteNode.getRight() !=null && deleteNode.getLeft() != null){
                BinSearchTree rightSub = new BinSearchTree(deleteNode.getRight());//获得右子树
                int rmin = rightSub.findMin().getVal();//找到右子树中最小的值
                rightSub.remove(rmin);//将右子树中最小的值移除
                root.setVal(rmin);//用右子树中最小的值充当现在的根节点
            }else if(deleteNode.getLeft() != null){
                deleteNode.getLeft().setParent(null);
                root = deleteNode.getLeft();
                deleteNode.setLeft(null);
            }else if(deleteNode.getRight() != null){
                deleteNode.getRight().setParent(null);
                root = deleteNode.getRight();
                deleteNode.setRight(null);
            }else{
                root = null;
            }
        }else {
            boolean isLeft = deleteNode == parentNode.getLeft();
            if(deleteNode.getRight()!=null&&deleteNode.getLeft()!=null){
                BinSearchTree rightSub = new BinSearchTree(deleteNode.getRight());
                int rmin = rightSub.findMin().getVal();
                rightSub.remove(rmin);
                deleteNode.setVal(rmin);
            }else if(deleteNode.getLeft()!=null){
                deleteNode.setParent(null);
                if (isLeft){
                    parentNode.setLeft(deleteNode.getLeft());
                    parentNode.getLeft().setParent(parentNode);
                }else {
                    parentNode.setRight(deleteNode.getLeft());
                    parentNode.getRight().setParent(parentNode);
                }
                deleteNode.setLeft(null);
            }else if(deleteNode.getRight()!=null){
                deleteNode.setParent(null);
                if (isLeft){
                    parentNode.setLeft(deleteNode.getRight());
                    parentNode.getLeft().setParent(parentNode);
                }else {
                    parentNode.setRight(deleteNode.getRight());
                    parentNode.getRight().setParent(parentNode);
                }
                deleteNode.setLeft(null);
            }else {
                if (isLeft){
                    parentNode.setLeft(null);
                }else {
                    parentNode.setRight(null);
                }
            }

        }
        return true;
    }

    //输出广义表
    public void output()
    {
        PrintTree(root);
        System.out.println();
    }

    private void PrintTree(TreeNode treeNode) {
        if (treeNode != null) {
            System.out.print(treeNode.getVal());
            if (treeNode.getLeft() != null || treeNode.getRight() != null) {
                System.out.print('(');
                PrintTree(treeNode.getLeft());
                System.out.print(',');
                PrintTree(treeNode.getRight());
                System.out.print(')');
            }
        }
    }
}

什么是二叉搜索树
 二叉搜索树（BST，Binary Search Tree）， 也称二叉排序树或二叉查找树 。一棵二叉树，可以为空；如果不为空，满足以下性质：
 
非空左子树的所有键值小于其根结点的键值(/关键字）。
非空右子树的所有键值大于其根结点的键值。
左、右子树都是二叉搜索树。
 
注意：二叉排序树中没有相同关键字的结点。对二叉搜索树进行中序遍历可以得到按关键字排序的有序序列。*
 
//在讨论二叉排序树上的运算之前,定义其节点的类型如下：
typedef int keyType
typedef struct node         //记录类型
{ KeyType key;              //关键字项
InfoType data;             //其他数据域
struct node *lchild,*rchild;   //左右孩子指针
}
BSTNode;
 
二叉搜索树的指定结点的查找
 顾名思义，这种二叉树就是用来查找的。
 因为二叉排序树可看做是一个有序表，所以在二叉排序树上进行查找，和二分查找类似,也是一个逐步缩小查找范围的过程。
 查找从根结点开始，如果树为空，返回NULL 。
 若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：
 若X小于根结点键值，只需在左子树中继续搜索；如果X大于根结点的键值，在右子树中进行继续搜索； 若两者比较结果是相等，搜索完成，返回指向此结点的指针。
 
//递归
BSTNode *SearchBST(BSTNode *bt,KeyType k)
{  if(bt==NULL || bt->key==k)         //递归终结条件
return bt;
if (k<bt->key)
return SearchBST(bt->lchild,k); //在左子树中递归查找
else return SearchBST(bt->rchild,k); //在右子树中递归查找
}
 
由于非递归函数的执行效率高，可将“尾递归”函数改为迭代函数 ：
 
//非递归
BSTNode *SearchBST1(BSTNode *bt,KeyType k)
{ 
while (bt!=NULL)
{
if (k==bt->key)
   return bt;
else if (k<bt->key)
   bt=bt->lchild;  //在左子树中递归查找
else
   bt=bt->rchild;  //在左子树中递归查找
}
return NULL;     //没有找到返回NULL
}
 
注：查找的效率决定于树的高度
 
查找最大和最小元素
 按照性质，最大元素一定是在树的最右分枝的端结点上 ；最小元素一定是在树的最左分枝的端结点上 。参考代码如下，按英文意思进行理解即可：
 
//查找最小元素的递归函数 
Position FindMin( BinTree BST ) 
{     
if( !BST ) 
return NULL; /*空的二叉搜索树，返回NULL*/ 
else if( !BST->Left ) return BST;  /*找到最左叶结点并返回*/     
else  return FindMin( BST->Left ); /*沿左分支继续查找*/ } 

//查找最大元素的迭代函数 
Position FindMax( BinTree BST ) 
{     
if(BST)           
while( BST->Right )  
BST = BST->Right;         /*沿右分支继续查找，直到最右叶结点*/ 
return BST; 
}    

 
二叉搜索树的插入
 关键是要找到元素应该插入的位置。
 插入过程：
 （1）若二叉排序树T为空，则创建一个key域为k的节点，将它作为根节点；
 （2）否则将k和根节点的关键字比较，若两者相等，则说明树中已有此关键字k，无须插入，直接返回0；
 （3）若kkey，则将k插入根节点的左子树中。
 （4）否则将它插入右子树
 
int InsertBST(BSTNode *&p,KeyType k)     //在以*p为根节点的BST中插入一个关键字为k的节点。插入成功返回1,否则返回0
{  
if(p==NULL)             //原树为空, 新插入的记录为根节点
{   
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if  (k==p->key)               //存在相同关键字的节点,返回0
return 0;
else if (k<p->key) return InsertBST(p->lchild,k);　//插入到左子树中
else  return InsertBST(p->rchild,k);             //插入到右子树中
 }
 
二叉搜索树的生成
 二叉排序树的生成，是从一个空树开始，每插入一个关键字,就调用一次插入算法将它插入到当前已生成的二叉排序树中。
 
BSTNode *CreatBST(KeyType A[],int n) //返回树根指针
{ 
BSTNode *bt=NULL;    //初始时bt为空树
int i=0;
while (i<n) 
{  
InsertBST(bt,A[i]);  //将A[i]插入二叉排序树T中
i++;
}
return bt;         //返回建立的二叉排序树的根指针
 }
 
任何节点插入到二叉排序树时，都是以叶子节点插入的。
 
**二叉搜索树的删除 **
 这个过程是最复杂的。
 1.①被删除的节点是叶子节点：直接删去该节点。其双亲节点中相应指针域的值改为“空”
 ②被删除的节点只有左子树或者只有右子树，用其左子树或者右子树代替它。其双亲节点的相应指针域的值改为 “指向被删除节点的左子树或右子树”。
 ③被删除的节点既有左子树，也有右子树：以其前驱替代之，然后再删除该前驱节点。前驱是左子树中最大的节点
 
int DeleteBST(BSTNode *&bt,KeyType k)          //在bt中删除关键字为k的节点
{  
if(bt==NULL) return 0;   //空树删除失败
else 
{
if (k<bt->key) 
return DeleteBST(bt->lchild,k);//递归在左子树中删除为k的节点
else if (k>bt->key) return DeleteBST(bt->rchild,k);//递归在右子树中删除为k的节点
else 
{  
Delete(bt);    //调用Delete(bt)函数删除*bt节点
return 1;
}
}}

void Delete(BSTNode *&p)    //从二叉排序树中删除*p节点
{ 
BSTNode *q;
if(p->rchild==NULL)      //*p节点没有右子树的情况
{   
q=p; 
p=p->lchild;   //其左子树的根节点放在被删节点的位置上
free(q);  
}
else if (p->lchild==NULL)    //*p节点没有左子树
{   
q=p; 
p=p->rchild;                //其右子树的根节点放在被删节点的位置
free(q);  
}
else Delete1(p,p->lchild);    //*p节点既有左子树又有右子树的情况
}

void Delete1(BSTNode *p,BSTNode *&r) //当被删*p节点有左右子树时的删除过程
{  
BSTNode *q;
if (r->rchild!=NULL) Delete1(p,r->rchild);      //递归找最右下节点
else     //找到了最右下节点*r
{   
p->key=r->key;            //将*r的关键字值赋给*p
q=r; 
r=r->lchild;                   //将左子树的根节点放在被删节点的位置上
free(q); //释放原*r的空间
}
 }
 
2.另一种类似做法：
 考虑三种情况： 
 ①要删除的是叶结点：直接删除，并再修改其父结点指针—置为NULL ；
 
 
②要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点 ；
 
 
③要删除的结点有左、右两棵子树： 用另一结点替代被删除结点：右子树的最小元素 或者 左子树的最大元素 ；取右子树中的最小元素替代 ，取左子树中的最大元素替代 ；
 
 
BinTree Delete( ElementType X, BinTree BST )  
{   
Position Tmp;      
if( !BST ) 
printf("要删除的元素未找到");      
else if( X < BST->Data )              
BST->Left = Delete( X, BST->Left); /* 左子树递归删除 */     
else if( X > BST->Data )              
BST->Right = Delete( X, BST->Right); /* 右子树递归删除 */     
else /*找到要删除的结点 */           
if( BST->Left && BST->Right ) 
{ /*被删除结点有左右两个子结点 */               
Tmp = FindMin( BST->Right );                 /*在右子树中找最小的元素填充删除结点*/              
BST->Data = Tmp->Data;               
BST->Right = Delete( BST->Data, BST->Right);         /*在删除结点的右子树中删除最小元素*/          
} 
else { /*被删除结点有一个或无子结点*/              
Tmp = BST;               
if( !BST->Left ) /* 有右孩子或无子结点*/                   
BST = BST->Right;               
else if( !BST->Right ) /*有左孩子或无子结点*/                   
BST = BST->Left;              
free( Tmp );          
}     
return BST; 
} 
 
二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下.那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度。这样的树就是：平衡二叉树
 
各种树
 平衡二叉树
 B-和B+树的定义、性质特点、举例说明
 线索二叉树
 哈夫曼树Huffman Tree