【算法面试】二叉搜索树
每一个内心仰望理想的人，都在低头干活
摘要
顾名思义，二叉搜索树是由两个孩子节点组成的树状的数据结构，由于其特殊的性质，任意一个节点的左子树的每个节点总比这个节点小，右子树的每个节点总比这个节点大，所以二叉搜索树的查询性能比较好。
本文只讲解二叉搜索树，二叉平衡树不是本文重点
正文
不得不承认，递归思想在二叉树中展现的淋漓尽致，本文讲解的二叉搜索树主要操作如下：
-
插入节点
-
先序遍历
-
中序遍历
-
后续遍历
-
层序遍历
-
求最小节点
-
求最大节点
-
搜索
-
求子节点的父节点
-
求最大深度
-
求树的节点个数
-
求叶子节点个数
-
返回深度从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+",");
}另外说一点：中序遍历可以从小到大输出所有节点，这个性质要牢记。
层序遍历
层序遍历，与先中后续遍历思想不同，层序遍历利用了队列这个数据结构，思路如下：
-
将根节点入队
-
一直循环，直到队列为空结束循环
-
对头节点出队
-
将对头节点的左右孩子分别入队
-
返回第2步
代码如下：
/**
* 层序遍历
* @param root
*/
public void levelOrderTraval(Node root){
if(root == null)
return;
Queue<Node> 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<root.value)
return getParent(root.left,node);
else
return getParent(root.right,node);
}获取树节点个数和叶子节点个数
/**
* 获取树的节点个数
* @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;
}好了，二叉搜索树最难的操作到了，删除节点
删除节点
删除的逻辑是这样的
-
如果该节点没有孩子节点，那么直接删除该节点，并修改其父节点，使父节点的左右孩子都指向null
-
如果该节点只有一个孩子，那么将该节点提升为父节点，当然这里需要判断一下该节点是父节点的左孩子还是右孩子
-
如果该节点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<arr.length;i++){
Node node = new Node(arr[i]);
binaryTree.insertNode(root,node);
}
System.out.println(binaryTree.getTreeNodeCount(root));
}结束
好了，二叉搜索树基本操作就到这里，如果大家有什么疑问可以加笔者微信或者关注笔者公众号，获取更多后端技术干货。