本文共 8700 字，大约阅读时间需要 29 分钟。

每一个内心仰望理想的人，都在低头干活

 摘要

顾名思义，二叉搜索树是由两个孩子节点组成的树状的数据结构，由于其特殊的性质，任意一个节点的左子树的每个节点总比这个节点小，右子树的每个节点总比这个节点大，所以二叉搜索树的查询性能比较好。

本文只讲解二叉搜索树，二叉平衡树不是本文重点

 正文

不得不承认，递归思想在二叉树中展现的淋漓尽致，本文讲解的二叉搜索树主要操作如下：

• 插入节点

• 先序遍历

• 中序遍历

• 后续遍历

• 层序遍历

• 求最小节点

• 求最大节点

• 搜索

• 求子节点的父节点

• 求最大深度

• 求树的节点个数

• 求叶子节点个数

• 返回深度从1-deepth的节点总个数

• 返回深度为deepth的节点个数

• 返回第level层节点个数

• 返回中序遍历的后继节点

• 删除节点

其中，删除节点的操作最为复杂，大家一定要多理解。 

节点类型 

class Node{    //值域    public int value;    //左孩子    public Node left;    //右孩子    public Node right;    public Node(int value){        this.value = value;        this.left = null;        this.right = null;    }}

插入节点

根据二叉搜索树的性质，如果node.value<root.value，则向左递归，否则向右递归，所以代码如下

public void insertNode(Node root,Node node){    if(root == null){        root = new Node(node.value);        return;   }    Node x = root;    Node p = x; //表示node要插入p后    while(x != null){        p = x;        if(node.value < x.value){            x = x.left; //向左        }else if(node.value > x.value){            x = x.right;    //向右        }else{            return;        }    }    if(node.value < p.value){        p.left = new Node(node.value);    }else{        p.right = new Node(node.value);    }}

前序、中序、后续遍历

先序：根-->左-->右

中序：左-->根-->右

后续：左-->右-->根

/** * 先序遍历 * @param node */public void preOrderTraval(Node node){    if(node == null)        return;    System.out.print(node.value+",");    preOrderTraval(node.left);    preOrderTraval(node.right);}/** * 中序遍历 * @param root */public void inOrderTravel(Node root){    if(root == null)        return;    inOrderTravel(root.left);    System.out.print(root.value+",");    inOrderTravel(root.right);}/** * 后序遍历 * @param root */public void postOrderTraval(Node root){    if(root == null)        return;    postOrderTraval(root.left);    postOrderTraval(root.right);    System.out.print(root.value+",");}

另外说一点：中序遍历可以从小到大输出所有节点，这个性质要牢记。

层序遍历 

层序遍历，与先中后续遍历思想不同，层序遍历利用了队列这个数据结构，思路如下：

1. 将根节点入队

2. 一直循环，直到队列为空结束循环

3. 对头节点出队

4. 将对头节点的左右孩子分别入队

5. 返回第2步

代码如下：

/** * 层序遍历 * @param root */public void levelOrderTraval(Node root){    if(root == null)        return;    Queue
   
     queue = new LinkedList<>();    queue.offer(root);    while(!queue.isEmpty()){        Node head = queue.poll();        System.out.print(head.value+",");        Node left = head.left;        Node right = head.right;        if(left != null)            queue.offer(left);        if(right != null)            queue.offer(right);    }}
   

求最小、最大节点

由二叉搜索树的性质可知，最小节点是树中最左下角的那个节点，最大节点是树中最右下角的那个节点 

/** * 返回最左（小）节点 * @param node * @return */public Node getMin(Node node){    if(node == null)        return null;    if(node.left==null)        return node;    return getMin(node.left);}/** * 返回最右（大）节点 * @param node * @return */public Node getMax(Node node){    if(node == null)        return null;    if(node.right==null)        return node;    return getMax(node.right);}

 搜索某个节点，返回节点指针

当然用到了递归的性质，如果node.value<root.value，向左递归，否则向右递归

/** * 搜索 * @param root * @param node * @return */public Node search(Node root,Node node){    if(root==null || node==null)        return null;    if(node.value < root.value){        return search(root.left,node);    }else if(node.value > root.value){        return search(root.right,node);    }else{        return root;    }}

 获取父节点

/** * 获取父节点 * @param root * @param node * @return */public Node getParent(Node root,Node node){    if(root==null || node==null)        return null;    if((root.left!=null && root.left.value==node.value)||(root.right!=null && root.right.value==node.value))        return root;    if(node.value

 获取树节点个数和叶子节点个数

/** * 获取树的节点个数 * @param root * @return */public int getTreeNodeCount(Node root){    if(root == null)        return 0;    int leftTreeNodeCount = getTreeNodeCount(root.left);    int rightTreeNodeCount = getTreeNodeCount(root.right);    return leftTreeNodeCount+rightTreeNodeCount+1;}/** * 获取树叶子节点个数 * @param root * @return */public int getTreeLeafNodeCount(Node root){    if(root == null)        return 0;    //该节点是叶子节点    if(root.left==null && root.right==null)        return 1;    return getTreeLeafNodeCount(root.left)+getTreeLeafNodeCount(root.right);}

 获取树的最大深度

这里用图说明一下，树的深度和层数之间的关系

/** * 获得树深度 * @param root * @return */public int getMaxDeepth(Node root){    if(root==null)        return 0;    int leftDeepth = getMaxDeepth(root.left)+1;    int rightDeepth = getMaxDeepth(root.right)+1;    return leftDeepth>rightDeepth?leftDeepth:rightDeepth;}

获取深度从1-deepth的节点的总个数

/** * 返回深度从1到deepth的节点总个数 * @param root * @param deepth * @return */public int getDeepthAllNodeCount(Node root, int deepth){    if(deepth <= 0 || root==null)        return 0;    return getDeepthAllNodeCount(root.left,deepth-1)+ getDeepthAllNodeCount(root.right,deepth-1)+1;}

 获取深度为deepth的节点个数

/** * 返回深度为deepth的节点个数 * @param root * @param deepth * @return */public int getDeepthNodeCount(Node root, int deepth){    if(deepth <= 0 || root==null)        return 0;    //这就是要求的那一行    if(deepth == 1){        return 1;    }    return getDeepthNodeCount(root.left,deepth-1)+ getDeepthNodeCount(root.right,deepth-1);}

 返回第level层节点的个数

/** * 返回第level层节点个数 * @param root * @param level * @return */public int getLevelNodeCount(Node root,int level){    //找出深度deepth与层level之间的关系    int maxDeepth = getMaxDeepth(root);    int k = maxDeepth - level;    return getDeepthNodeCount(root,k);}

 返回中序遍历时node节点的后继节点

这一块比较难理解，大家需要完全熟悉中序遍历

/** * 返回中序遍历时node的后继节点 * @param root * @param node * @return */public Node getNext(Node root,Node node){    //判断node节点是否存在    Node exit = search(root,node);    if(exit==null)        return null;    //如果node有右孩子，那么node的后继节点一定是getMin(node.right);    if(exit.right!=null)        return getMin(exit.right);    //如果node是叶子节点，且是父节点的右孩子，那么一直沿着父节点向上找    Node parent = getParent(root,exit);    while(parent!=null && parent.right!=null && parent.right.value==exit.value){        exit = parent;        parent = getParent(root,parent);    }    return parent;}

 好了，二叉搜索树最难的操作到了，删除节点

删除节点

删除的逻辑是这样的

1. 如果该节点没有孩子节点，那么直接删除该节点，并修改其父节点，使父节点的左右孩子都指向null

2. 如果该节点只有一个孩子，那么将该节点提升为父节点，当然这里需要判断一下该节点是父节点的左孩子还是右孩子

3. 如果该节点node有两个孩子，那么找出node的后继节点nextNode，并把nextNode提升为node节点，如果nextNode有右孩子，并把nextNode.right提升为nextNode父节点的左孩子

/** * 删除某一节点 * @param root * @param node */public Node deleteNode(Node root,Node node){    Node exit = search(root,node);    //没有这个节点    if(exit == null)        return root;    //是叶子节点    if(exit.left==null && exit.right==null){        Node parent = getParent(root,exit);        if(parent.left!=null && parent.left.value==exit.value){            parent.left = null;        }else{            parent.right = null;        }        return root;    }    //有孩子节点    Node parent = getParent(root,node);    if(parent == null){ //如果是根节点        Node next = getNext(root,root);        if(next == null){            root = root.left;            root.right = null;            return root;        }        next.left = root.left;        Node nextParent = getParent(root,next);        if(nextParent != root){            nextParent.left = next.right;            next.right = root.right;        }        //返回根节点指针        return next;    }    //如果要删除的节点是parent的左孩子    if(parent.left!=null && parent.left.value == exit.value){        if(exit.left!=null && exit.right==null){    //只有左孩子            parent.left = exit.left;        }else if(exit.right!=null &&exit.left==null){   //只有右孩子            parent.left = exit.right;        }else if(exit.left!=null && exit.right!=null){  //有左右孩子            Node next = getNext(root,exit);            if(next!=null){                next.left = exit.left;                Node nextParent = getParent(root,next);                if(exit != nextParent){                    nextParent.left = next.right;                    next.right = exit.right;                }                parent.left = next;            }        }    }else{  //如果要删除的节点是parent的右孩子        if(exit.left!=null && exit.right==null){    //只有左孩子            parent.right = exit.left;        }else if(exit.right!=null &&exit.left==null){   //只有右孩子            parent.right = exit.right;        }else if(exit.left!=null && exit.right!=null){  //有左右孩子            Node next = getNext(root,exit);            if(next!=null) {                next.left = exit.left;                Node nextParent = getParent(root, next);                if (exit != nextParent) {                    nextParent.left = next.right;                    next.right = exit.right;                }                parent.right = next;            }        }    }    exit = null;    return root;}

 删除节点的操作是最复杂的，希望大家画图理解

测试

public static void main(String[] args) {    int arr[] = {50,40,30,45,20,35,43,47,80,70,60,75,90,85,100,55,65,57,53};    BinaryTree binaryTree = new BinaryTree();    Node root = new Node(arr[0]);    for(int i = 1;i

 结束

好了，二叉搜索树基本操作就到这里，如果大家有什么疑问可以加笔者微信或者关注笔者公众号，获取更多后端技术干货。