二叉树知识点总结

偏执的太偏执、 2022-01-29 01:04 401阅读 0赞

### 二叉树知识点总结 ###

*  二叉树的基本术语定义
 *  二叉树的计算公式
 *  完全二叉树叶节点计算
 *  完全二叉树的节点数计算
 *   *  解题思路—二分思路
     *  Java解题—二分思路

# 二叉树的基本术语定义 #

*  **节点的度**：指该节点所含子树的个数。
 *  **叶子节点（终端节点）**：度为0的节点。
 *  **兄弟节点**：有共同父节点的节点。
 *  **非终端节点**：叶子以外的节点均为非终端节点，即度不为0的节点。
 *  **阶层（级）**：树的层级，树的根节点的层级为1，其余节点的阶层为该节点父节点的阶层+1。
 *  **高度**：树的最大阶层。
 *  **后继节点**：这个节点在中序遍历序列中的下一个节点。
 *  **前驱节点**：这个节点在中序遍历序列中的上一个节点。

# 二叉树的计算公式 #

*  具有 n 个节点的完全二叉树的高度为：**log2(n + 1)**
 *  n 层二叉树的第 n 层最多拥有节点个数：**2n-1**
 *  高度为 n 的满二叉树结点个数为：**2n \- 1**
 *  二叉树中度为 0 的结点个数为度为 2 的结点个数+1 ：**n0 = n2 + 1**
 *  有 n 个节点的二叉树一共有多少种：**(2n)! / n!(n+1)!**

> 证明：  
> 有 1 个节点时，f(1) = 1;  
> 有 2 个节点时，固定根节点，另外一个节点 = 1 + 0 = 0 + 1，有两种，即 f(2) = f(1) + f(1) = 2;  
> 有 3 个节点时，固定根节点，剩余两个节点 = 2 + 0 = 1 + 1 = 0 + 2，有三种，即 f(3) = f(2) + f(1)×f(1) + f(2);  
> 有 n 个节点时，固定根节点，剩余节点 = n-1 + 0 = n-2 + 1 = n-3 + 2 = … = 1 + n-2 = 0 + n-1，即 f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)。  
> **设f(0) = 1，f(1) = 1，f(n) = f(n-1)f(0) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(0)f(n-1)  
> 为卡特兰(Catalan)数，最后的解为 (2n)! / n!(n+1)!。**  
> **其前几项为 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…**  
> 卡特兰数的推导需要构造母函数。

# 完全二叉树叶节点计算 #

**一个具有n个节点的完全二叉树，其叶子节点的个数为多少？**  
设：节点总个数为n，叶子节点个数为n0（即结点度为0的结点个数为n0），度为1的节点个数为n1， 度为2的节点个数为n2，树中边的个数为b。题目最终要求的就是n0的个数。  
一棵二叉树的节点是由度数为0、1和2的节点组成，所以  
**n = n0 + n1 + n2**  
除了根节点没有向上连接的边，其余结点都带有一条边，即  
**b = n - 1**  
所以  
**b = n0 + n1 + n2 - 1**  
一个度为2的节点带边2条，一个度为1的节点带边1条，度为0的结点不带边，所以：  
**b = n1 + 2 × n2**  
可得：  
**n0 + n1 + n2 - 1 = n1 + 2 × n2**  
得出：  
**n0 = n2 + 1 度为0的结点个数为度为2的结点个数+1**  
将 `n0 = n2 + 1` 代入 `n = n0 + n1 + n2` ，求 n0 得：  
**n0 = (n - n1 + 1) / 2**  
**当节点数n为奇数时，说明没有度为1的节点；当节点数n为偶数时，说明有一个度为1的节点。**  
所以：

*  **n为偶数时，n0 = n / 2**
 *  **n为奇数时，n0 = (n + 1) / 2**

# 完全二叉树的节点数计算 #

给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为N，请实现时间复杂度低于O(N)的解法。

## 解题思路—二分思路 ##

想要控制时间复杂度，需要基于**二分思路**。将二叉树以根节点分为作成左右子树：

*  如果**左子树的高度与右子树的高度相等**，则说明右子树可能存在度为1的节点，而**左子树为满二叉树**，此时可以直接通过高度计算出左子树个数，再**递归求解右子树**即可。
 *  若**左子树高度不等于右子树**，通过二叉树的性质可知，左子树高度必须大于等于右子树，所以**右子树是一个满二叉树**，直接通过高度计算出右子树个数，再**递归求解左子树**即可。
 *  **时间复杂度为O(logN2)**

## Java解题—二分思路 ##

public static int nodeNum(TreeNode head){
        if(head==null) return 0;
        TreeNode left = head.left;
        if(left==null) return 1;
        TreeNode right = head.right;
        if(right==null) return 2;
        int leftdepth = 1, rightdepth = 1; // 左右子树的深度
        // 计算左子树的深度
        while(left!=null){
            left = left.left;
            leftdepth++;
        }
        // 计算右子树的深度
        while(right!=null){
            right = right.left;
            rightdepth++;
        }
        if(leftdepth==rightdepth)
            // 只要计算右子树有多少结点，继续递归，左子树是满二叉树，1<<k 即为 2的k次方
            // 深度为k的满二叉树结点个数为 2^k - 1
            // 这里1<<k 中加入了整棵树的根节点
            return 1<<leftdepth + nodeNum(right);
        else 
            return nodeNum(left) + 1<<rightdepth;
    }