二叉树相关算法

一. 简介

根据维基百科的定义:在计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序,不能颠倒。

二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉查找树和二元堆积,并应用于高效率的搜索和排序。

本文中所有二叉树代码都使用一下结构代表树节点:

/**
 * This class describes a node of the binary tree
 * @author Haibo Yu on 10/08/2017.
 */
public class BinaryTreeNode {
    private int value;
    private BinaryTreeNode leftChild;
    private BinaryTreeNode rightChild;
    ....
}

二. 实际应用

  1. B+和B-树在文件系统中的应用
  2. 红黑树用于调度、虚拟内存管理、跟踪文件描述符和目录条目等
  3. Radix树,用于内存管理、NFS相关查找和网络相关的功能
  4. 二叉树搜索用于中断处理、登记缓存查找等
  5. Merkle 树用于最近比较流行的区块链技术。

三. 相关算法

1. 求二叉树中的节点个数

分析:

可以通过递归的方法:

  1. 如果二叉树为空,节点个数为0
  2. 如果二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

代码如下:

/**
 * Given a root node of a binary tree, get the node count
 * @param rootNode The root node of the binary tree
 * @return The count of the nodes in the binary tree
 */
public int getNodeCountOfBinaryTree(BinaryTreeNode rootNode){
    if(null == rootNode){
        return 0;
    }else{
        return getNodeCountOfBinaryTree(rootNode.getLeftChild()) + getNodeCountOfBinaryTree(rootNode.getRightChild()) + 1;
    }
}

2. 求二叉树的深度

分析:

递归解法:

  1. 如果二叉树为空,二叉树的深度为0
  2. 如果二叉树不为空,二叉树的深度 = max(左子树深度, 右子树深度) + 1

代码如下:

/**
 * Given a root node of a binary tree, get the tree depth
 * @param rootNode The root node of the binary tree
 * @return The depth of the binary tree
 */
public int getDepthOfBinaryTree(BinaryTreeNode rootNode){
    if(null == rootNode){
        return 0;
    }else{
        int leftSubTreeDepth = getDepthOfBinaryTree(rootNode.getLeftChild());
        int rightSubTreeDepth = getDepthOfBinaryTree(rootNode.getRightChild());
        return  (leftSubTreeDepth > rightSubTreeDepth )?(leftSubTreeDepth + 1):(rightSubTreeDepth + 1);
    }
}

3. 前序遍历,中序遍历,后序遍历

分析:

前序遍历递归解法:

(1)如果二叉树为空,空操作

(2)如果二叉树不为空,访问根节点,前序遍历左子树,前序遍历右子树

中序遍历递归解法

(1)如果二叉树为空,空操作。

(2)如果二叉树不为空,中序遍历左子树,访问根节点,中序遍历右子树

后序遍历递归解法

(1)如果二叉树为空,空操作

(2)如果二叉树不为空,后序遍历左子树,后序遍历右子树,访问根节点

代码如下:

这些操作比较简单,类似于求深度和统计节点数,所以这里就不加了。

4. 分层遍历二叉树(按层次从上往下,从左往右)

分析:

相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。

代码如下:

/**
 * Given a root node of a binary tree, iterate the tree by every level
 * @param rootNode The root node of the binary tree
 */
public void iterateBinaryTreeByLevel(BinaryTreeNode rootNode){
    if(null == rootNode){
        return ;
    }

    Queue<BinaryTreeNode> nodes = new LinkedList<>();
    nodes.offer(rootNode);
    while(!nodes.isEmpty()){
        BinaryTreeNode curNode = nodes.poll();
        System.out.println("Pop Node:"+curNode.getValue());
        if(null != curNode.getLeftChild()){
            nodes.offer(curNode.getLeftChild());
        }
        if(null != curNode.getRightChild()){
            nodes.offer(curNode.getRightChild());
        }
    }
}

5. 将二叉查找树变为有序的双向链表

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、multiset、关联数组等。

题目描述:

输入一棵二叉搜索树,现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中,不能创建任何新的结点,只能调整树中的结点指针的指向来实现。

分析:

使用递归算法处理。左子树转换后的最后一个节点为根节点在双向链表中的前一个节点,根节点的后一个节点为右子树转换后的第一个节点。

解题思路:

  • 如果左子树不为null,处理左子树

a)递归转化左子树为双向链表;

b)找出根结点的前驱节点(是左子树的最右的节点)

c)将上一步找出的节点和根结点连接起来

  • 如果右子树不为null,处理右子树(和上面的很类似)

a)递归转化右子树为双向链表;

b)找出根结点的后继节点(是右子树的最左的节点)

c)将上一步找出的节点和根结点连接起来

找到最左边的节点并返回

代码如下:

/**
 * Convert a binary search tree into a doubly linked list, the requirement is not to create
 * new node, only change the pointers based on the existing node.
 * @param rootNode The root node of the binary search tree.
 * @return The head node of the doubly linked list.
 */
public void convertBinaryTreeToDoublyLinkedList(BinaryTreeNode rootNode){
    if(null == rootNode){
        return;
    }

    if(null != rootNode.getLeftChild()){
        convertBinaryTreeToDoublyLinkedList(rootNode.getLeftChild());
        BinaryTreeNode biggestNode = findBiggestNodeInTheTree(rootNode.getLeftChild());
        biggestNode.setRightChild(rootNode);
        rootNode.setLeftChild(biggestNode);
    }
    if(null != rootNode.getRightChild()){
        convertBinaryTreeToDoublyLinkedList(rootNode.getRightChild());
        BinaryTreeNode smallestNode = findSmalledNodeInTheTree(rootNode.getRightChild());
        smallestNode.setLeftChild(rootNode);;
        rootNode.setRightChild(smallestNode);
    }
}

/**
 * Find the smallest node in the binary search tree
 * @param rootNode The root node
 * @return The smallest node in the binary search tree
 */
private BinaryTreeNode findSmalledNodeInTheTree(BinaryTreeNode rootNode){
    while(rootNode.getLeftChild() != null){
        rootNode = rootNode.getLeftChild();
    }
    return rootNode;
}

/**
 * Find the biggest node in the binary search tree
 * @param rootNode The root node
 * @return The biggest node in the binary search tree
 */
private BinaryTreeNode findBiggestNodeInTheTree(BinaryTreeNode rootNode){
    while(rootNode.getRightChild() != null){
        rootNode = rootNode.getRightChild();
    }
    return rootNode;
}

6. 求二叉树第K层的节点个数

分析:

递归解法:

(1)如果二叉树为空或者k<1返回0

(2)如果二叉树不为空并且k==1,返回1

(3)如果二叉树不为空且k>1,返回左子树中k-1层的节点个数与右子树k-1层节点个数之和

代码如下:

/**
 * Get the total node number of the kth level of the binary tree
 * @param rootNode The root node of the binary tree
 * @param k The level number
 * @return The total node number of the kth level.
 */
public int getNodeNumberForKthLevel(BinaryTreeNode rootNode, int k){
    if(null == rootNode || k<1){
        return 0;
    }

    if(k ==1){
        return 1;
    }

    int totalLeft = getNodeNumberForKthLevel(rootNode.getLeftChild(),k-1);
    int totalRight = getNodeNumberForKthLevel(rootNode.getRightChild(),k-1);
    return totalLeft + totalRight;
}

7. 求二叉树中叶子节点的个数

分析:

递归解法:

(1)如果二叉树为空,返回0

(2)如果二叉树不为空且左右子树为空,返回1

(3)如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数

代码如下:

/**
 * Get the total leaf node number of the binary tree
 * @param rootNode The root node of the binary tree
 * @return The total leaf node number
 */
public int getLeafNodeNumberForBinaryTree(BinaryTreeNode rootNode){
    if(null == rootNode){
        return 0;
    }

    if(null == rootNode.getLeftChild() && null == rootNode.getRightChild()){
        return 1;
    }

    int totalLeft = getLeafNodeNumberForBinaryTree(rootNode.getLeftChild());
    int totalRight = getLeafNodeNumberForBinaryTree(rootNode.getRightChild());

    return totalLeft + totalRight;
}

8. 判断两棵二叉树是否结构相同

分析:

递归解法:

(1)如果两棵二叉树都为空,返回真

(2)如果两棵二叉树一棵为空,另一棵不为空,返回假

(3)如果两棵二叉树都不为空,如果对应的左子树和右子树都同构返回真,其他返回假

代码如下:

/**
 * Given 2 binary tree, check if they are same structure.
 * @param rootNode1 The root node of the 1st binary tree
 * @param rootNode2 The root node of the 2nd binary tree
 * @return If they have same strcture
 */
public boolean checkIfTwoBinaryTreeHaveSameStructure(BinaryTreeNode rootNode1,BinaryTreeNode rootNode2){
    if(null == rootNode1 && null == rootNode2){
        return true;
    }else if(null == rootNode1 || null == rootNode2){
        return false;
    }


    boolean leftEqual = checkIfTwoBinaryTreeHaveSameStructure(rootNode1.getLeftChild(), rootNode2.getLeftChild());
    boolean rightEqual = checkIfTwoBinaryTreeHaveSameStructure(rootNode1.getRightChild(),rootNode2.getRightChild());

    return (leftEqual && rightEqual);
}

9. 判断二叉树是不是平衡二叉树

平衡二叉树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:

  • 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,
  • 同时,平衡二叉树必定是二叉搜索树,反之则不一定。

平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,可以参考Fibonacci(斐波那契)数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。

分析:

递归解法:

(1)如果二叉树为空,返回真

(2)如果二叉树不为空,如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1,返回真,其他返回假

代码如下:

/**
 * Given a binary tree, check if it is AVL tree.
 * @param rootNode The root node of the binary tree
 * @return If the tree is AVL tree
 */
public boolean checkIfAVLBinaryTree(BinaryTreeNode rootNode){
    if(null == rootNode){
        return true;
    }

    boolean leftAVL = checkIfAVLBinaryTree(rootNode.getLeftChild());
    boolean rightAVL = checkIfAVLBinaryTree(rootNode.getRightChild());

    int leftDepth = this.getDepthOfBinaryTree(rootNode.getLeftChild());
    int rightDepth = this.getDepthOfBinaryTree(rootNode.getRightChild());

    return (leftAVL && rightAVL && (Math.abs(leftDepth - rightDepth)<=1));
}

10. 求二叉树的镜像

分析:

递归解法:

(1)如果二叉树为空,返回空

(2)如果二叉树不为空,求左子树和右子树的镜像,然后交换左子树和右子树

代码如下:

/**
 * Given a binary tree, get it's mirror tree.
 * @param rootNode The root node of the binary tree
 * @return The mirror tree
 */
public BinaryTreeNode getMirrorBinaryTree(BinaryTreeNode rootNode){
    if(null == rootNode){
        return null;
    }

    BinaryTreeNode leftMirror = getMirrorBinaryTree(rootNode.getLeftChild());
    BinaryTreeNode rightMirror = getMirrorBinaryTree(rootNode.getRightChild());

    rootNode.setLeftChild(rightMirror);
    rootNode.setRightChild(leftMirror);

    return rootNode;
}

11. 求二叉树中两个节点的最低公共祖先节点

分析:

当节点带有parent指针时,可以方便的从给定节点遍历到根节点,经过的路径其实一条链表。因此,求最低公共祖先,就是求两链表的第一个交点。

当节点没有父指针时,使用递归解法:

(1)如果两个节点分别在根节点的左子树和右子树,则返回根节点

(2)如果两个节点都在左子树,则递归处理左子树;如果两个节点都在右子树,则递归处理右子树

代码如下:

/**
 * Given a binary tree and 2 node, get their lowest common node.
 * @param rootNode The root node of the binary tree
 * @return The mirror tree
 */
public BinaryTreeNode getLowestCommonNodeOfTwoNode(BinaryTreeNode rootNode, BinaryTreeNode node1, BinaryTreeNode node2){
    if(null == rootNode || null == node1 || null == node2){
        return null;
    }

    if(findNodeInTheTree(rootNode.getLeftChild(),node1)){
        //If node1 and node2 are found separately in left and right tree,then rootNode is the lowest common node.
        if(findNodeInTheTree(rootNode.getRightChild(),node2)){
            return rootNode;
        }else{
            return getLowestCommonNodeOfTwoNode(rootNode.getLeftChild(),node1,node2);
        }
    }else{
        if(findNodeInTheTree(rootNode.getLeftChild(),node2)){
            return rootNode;
        }else{
            return getLowestCommonNodeOfTwoNode(rootNode.getRightChild(),node1,node2);
        }
    }
}

/**
 * Check if the node is in the tree
 * @param rootNode The root node of the tree
 * @param node The node
 * @return If the tree has this node
 */
private boolean findNodeInTheTree(BinaryTreeNode rootNode, BinaryTreeNode node){
    if(null == rootNode){
        return false;
    }
    if(rootNode.equals(node)){
        return true;
    }
    boolean findInLeft = findNodeInTheTree(rootNode.getLeftChild(),node);
    boolean findInRight = findNodeInTheTree(rootNode.getRightChild(),node);
    return findInLeft||findInRight;
}

12. 求二叉树中节点的最大距离

分析:

递归解法:

(1)如果二叉树为空,返回0,同时记录左子树和右子树的深度,都为0

(2)如果二叉树不为空,最大距离要么是左子树中的最大距离,要么是右子树中的最大距离,要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离,同时记录左子树和右子树节点中到根节点的最大距离。

代码如下:

/**
 * Get the biggest distance between nodes of binary tree
 * @param rootNode The root node of the binary tree
 * @return The distance
 */
private int getBiggestDistanceBetweenNodeOfBinaryTree(BinaryTreeNode rootNode){
    if(null == rootNode){
        return 0;
    }

    int disLeft = getBiggestDistanceBetweenNodeOfBinaryTree(rootNode.getLeftChild());
    int disRight = getBiggestDistanceBetweenNodeOfBinaryTree(rootNode.getRightChild());

    int maxLeft = 0, maxRight = 0;
    if(null != rootNode.getLeftChild()){
        maxLeft = this.getDepthOfBinaryTree(rootNode.getLeftChild())+1;
    }
    if(null != rootNode.getRightChild()){
        maxRight = this.getDepthOfBinaryTree(rootNode.getRightChild())+1;
    }

    return Math.max(Math.max(disLeft,disRight),maxLeft+maxRight);
}

13. 由前序遍历序列和中序遍历序列重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

分析:

在二叉树的前序遍历序列中,第一个数字总是树的根结点的值。但在中序遍历序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列,才能找到根结点的值。

  前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列,就能确定根结点的值的位置。根据中序遍历特点,在根结点的值1前面的3个数字都是左子树结点的值,位于1后面的数字都是右子树结点的值。

  在二叉树的前序遍历和中序遍历的序列中确定根结点的值、左子树结点的值和右子树结点的值的步骤如下图所示:

Rebuild Binary Tree

  分别找到了左、右子树的前序遍历序列和中序遍历序列,我们就可以用同样的方法分别去构建左右子树。换句话说,这是一个递归的过程。  
  
思路总结:

先根据前序遍历序列的第一个数字创建根结点,接下来在中序遍历序列中找到根结点的位置,这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后,就可以递归地去分别构建它的左右子树。
  
代码如下:

/**
 * Rebuild the binary tree based on the pre-order and middle-order output of the tree.
 * @param preOrderArr The pre-order array output
 * @param midOrderArr The middle-order array output
 * @return The head node of the binary tree
 */
public BinaryTreeNode rebuildBinaryTree(int[] preOrderArr, int[] midOrderArr){
    if (preOrderArr == null || midOrderArr == null || preOrderArr.length != midOrderArr.length || preOrderArr.length < 1 || midOrderArr.length < 1) {
        return null;
    }

    return rebuildBinaryTree(preOrderArr, 0, preOrderArr.length - 1, midOrderArr, 0, midOrderArr.length -1);
}

/**
 * Recursively build the tree
 * @param preOrderArr The pre order array
 * @param preStart The start index of pre order array
 * @param preEnd The end index of the pre order array
 * @param midOrderArr The middle order array
 * @param midStart The start index of middle order array
 * @param midEnd The end index of middle order array
 * @return The root node of the sub tree after building.
 */
public BinaryTreeNode rebuildBinaryTree(int[] preOrderArr, int preStart, int preEnd, int[] midOrderArr, int midStart, int midEnd){
    if (preStart > preEnd) {
        return null;
    }

    // Get current root node
    int rootValue = preOrderArr[preStart];
    //Get the index of current root node in the midOrderArray
    int indexInMid = midStart;
    while (indexInMid <= midEnd && midOrderArr[indexInMid] != rootValue) {
        indexInMid++;
    }

    // Create the current root node
    BinaryTreeNode rootNode = new BinaryTreeNode(rootValue);

    // Rebuild the left sub tree
    BinaryTreeNode leftChild = rebuildBinaryTree(preOrderArr, preStart + 1,
            preStart + indexInMid - midStart,
            midOrderArr, midStart, indexInMid - 1);
    //Rebuild the right sub tree
    BinaryTreeNode rightChild = rebuildBinaryTree(preOrderArr, preStart + indexInMid - midStart + 1,
            preEnd, midOrderArr, indexInMid + 1, midEnd);

    rootNode.setLeftChild(leftChild);
    rootNode.setRightChild(rightChild);
    return rootNode;
}

14. 判断二叉树是不是完全二叉树

完全二叉树(Complete Binary Tree)

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

分析:

按层次(从上到下,从左到右)遍历二叉树,当遇到一个节点的左子树为空时,则该节点右子树必须为空,且后面遍历的节点左
右子树都必须为空,否则不是完全二叉树。

代码如下:

/**
 * Given a binary tree, check if it's complete binary tree.
 * @param rootNode The root node of the tree
 * @return The flag of if it is complete binary tree
 */
public boolean checkIfCompleteBinaryTree(BinaryTreeNode rootNode){
    if(null == rootNode){
        return false;
    }

    Queue<BinaryTreeNode> nodes = new LinkedList<>();
    nodes.offer(rootNode);
    boolean startHavingEmptyChild = false;
    while(!nodes.isEmpty()){
        BinaryTreeNode curNode = nodes.poll();
        System.out.println("Pop Node:"+curNode.getValue());
        //If already there's node which has empty child, then this is not complete tree.
        if(startHavingEmptyChild
                && (null == curNode.getLeftChild() || null == curNode.getRightChild())){
            return false;
        }

        if(null != curNode.getLeftChild() && null != curNode.getRightChild()){
            nodes.offer(curNode.getLeftChild());
            nodes.offer(curNode.getRightChild());
        }else if(null != curNode.getLeftChild() && null == curNode.getRightChild()){
            startHavingEmptyChild = true;
            nodes.offer(curNode.getLeftChild());
        }else if(null == curNode.getLeftChild() && null != curNode.getRightChild()){
            return false;
        }else{
            startHavingEmptyChild = true;
        }
    }
    return true;
}

四. 代码

本文中所有代码,可访问Github获取:BinaryTreeAlgorithms.java

五. 参考文献

  1. 各种排序算法总结
  2. 二叉树
  3. 轻松搞定面试中的二叉树题目