《数据结构初阶》从零极速上手二叉树

“剑气纵横三万里，一剑光寒十九洲”

一、本章重点

1. 介绍树的概念
2. 介绍二叉树的概念
3. 掌握递归核心要义
4. 二叉树的oj题与详解

二、树

2.1树的概念

树是n个结点的有限集合T。当n=0时，称为空树；当n>0时，该集合满足如下条件：

​ ①其中必有一个称为根（root）的结点，它没有直接前驱，但有0个或多个直接后继。

​ ②其余n-1个结点可以划分成m（m>=0）互不相交的有限集T1，T2，T3，...Tm，其中Ti又是一棵树，称为根的子树。每棵子树的根节点有且仅有一个直接前驱，但有0个或多个直接后继。

（树是以递归的形式定义的）

下图为一棵树的逻辑结构图示，类似一棵倒长的树:

** 注：没有节点的树也是树，被称作空树，只有一个节点的树也是树。**

测试一：

下列是树还是非树？

答：不是树，不满足这一条件：每棵子树的根节点有且仅有一个直接前驱，即不能成环。

比如G的直接前驱有两个分别是A和D，所以该结构不是树。

2.2关于树的基本知识

以该树为例

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为3.。

叶节点或终端节点：度为0的节点称为叶节点； 如上图：K、L、F、G、M、I、J.节点都是叶节点。
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点、C是G的父节点。

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点、G是C的孩子节点。

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点，E和G这种表兄弟不算兄弟节点。

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为3.

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4。
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先。

三、二叉树

3.1二叉树的概念

概念：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

特点：

1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

以下就是一个普通二叉树

3.2特殊的二叉树

3.2.1满二叉树

概念：满二叉树是一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉
树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

3.2.2完全二叉树

3.3二叉树的性质

**二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1。
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1。
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(N+1）。**

3.4二叉树性质相关选择题练习

**1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A 不存在这样的二叉树
B 200
C 198
D 199**

**2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A n
B n+1
C n-1
D n/2**

解析：

1：选B.根据上述性质3，n0=n2+1=200.即叶子节点的个数为200（叶子节点是度为0的节点）

2：选A。二叉树只有0度、1度、2度节点，***所以n2+n1+n0=2n

又因为n0=n2+1，***所以2n0+n1-1=2*n

因为该树是完全二叉树，所以n1只能为0或者1.

当n1为0时，n0为小数，该情况省略、

所以n1等于1，因此n0等于n。

3.5二叉树链式结构的实现

3.5.1二叉树链式结构的遍历

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访
问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行
其它运算之基础。

遍历方式

1. NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。
3. LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

4.层序遍历：层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历图：

练习：请写出下面的前序/中序/后序/层序遍历

** 前序遍历：**

A->B->D->NULL->NULL->E->H->NULL->NULL->I->NULL->NULL->C->F->NULL->NULL->G

->NULL->NULL

中序遍历：

NULL->D->NULL->B->NULL->H->NULL->E->NULL->I->NULL->A->NULL->F->NULL->C->NULL

->G->NULL

后续遍历:

NULL->NULL->D->NULL->NULL->H->NULL->NULL->I->E->B-NULL->NULL->F->NULL->NULL

->G->C->A

层序遍历：A->B->C->D->E->F->G->NULL->NULL->H->I->NULL->NULL->NULL->NULL

3.5.2选择题训练

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（
）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为
（）
A E
B F
C G
D H

3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde

1.A

解析：通过层序遍历可画出二叉树的结构，根据二叉树的结构可得到前序序列。
2.A

解析：根据先序遍历可得到E是根。
3.D

解析：根据后序遍历可得到二叉树的根是a，后续遍历得到b是左子树，dce是右子树。可画出二叉树的结构，然后得到先序遍历序列。

四、递归

4.1递归的概念

递归概念：递归，即函数在运行的过程中调用自己。

构成递归需具备的条件：
1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

4.2递归的核心要义

将一个问题分成若干个相同的子问题，将大问题交给子问题去做，子问题交给子子问题去做.......最后被安排完成任务的即为递归的出口。

以斐波那契数列为例：

我们要求斐波那契数列第n个数的值

化简为求n-1和n-2的值

再把求n-1和n-2的值化简为求n-2和n-3和n-3和n-4的值

..........

这就是将n化简为若干个相同的子问题，这个子问题就是：它们都需要求前两个数的值。

一直递归到n==1，此时返回1或者递归到n==0，返回1.这就是递归的出口，也是最后被安排完成任务的语句。

4.3如何写一个递归？

** 三步走：**

1. 将问题化简为若干个相同的子问题。
2. 写出递归的出口
3. 调用函数自己，

以下是实现斐波那契数列的递归写法

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int fabonacci(int n)
{
    if (n < 3)//递归出口
    {
        return 1;
    }
    return fabonacci(n - 1) + fabonacci(n - 2);//根据函数功能实现函数
}
int main()
{
    //1 1 2 3 5 8 13
    int n = 7;
    printf("%d\n", fabonacci(n));
    return 0;
}

五、二叉树常见OJ题练习

5.1二叉树的前序遍历（力扣）

给你二叉树的根节点

root

，返回它节点值的 前序* *遍历

**输入：**root = [1,null,2,3]
**输出：**[1,2,3]

要实现的接口：

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{

}

思路：在堆区申请一块空间，用来存放节点值，再用递归思想，将节点1先放进堆区空间，再将它的左子树放入空间，再放入它的右子树。

递归写法：

先写递归出口：

if(root==NULL)
{
    return;
}

再放入根节点

ret[*returnSize]=root->val;
*returnSize=(*returnSize)+1;

最后需要遍历剩下的左子树和右子树，这是我们需要一个函数解决剩下遍历问题，而解决这个问题的函数就是我们写的函数本身，即调用函数本身即可。
还有一个问题是我们在堆区该开辟多大的空间，这里我用递归求了该二叉树的节点个数

三步写递归

1.将问题化为若干个小问题，每个树都需满足：树的节点个数==1+左子树的节点个数+右子树的节点个数。

2.写递归出口：如果该树为空，返回0。

3.调用函数自己。

 int size(struct TreeNode* root)
 {
     return root==NULL?0:1+size(root->left)+size(root->right);
 }

 void traversal(struct TreeNode* root,int* returnSize,int* ret)
 {
    if(root==NULL)
    {
        return;
    }
    ret[*returnSize]=root->val;
    *returnSize=(*returnSize)+1;
    traversal(root->left,returnSize,ret);
    traversal(root->right,returnSize,ret);
 }
 int size(struct TreeNode* root)
 {
     return root==NULL?0:1+size(root->left)+size(root->right);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int s=size(root);
    *returnSize=0;
    int* ret=malloc(sizeof(int)*s);
    traversal(root,returnSize,ret);
    return ret;
}

5.2二叉树的最大深度（力扣）

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

  3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

思路：直接递归

三步走：

1.将问题化为若干个相同的小问题，每个树都需满足：最大深度==1+（左子树的高度>右子树的高度?左子树的高度：右子树的高度）。

2.递归出口，当节点的地址为空时，返回0。

3.调用函数自己。

int maxDepth(struct TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return 1+fmax(maxDepth(root->left),maxDepth(root->right));
}

5.3平衡二叉树(力扣）

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过 1 。

**输入：**root = [3,9,20,null,null,15,7]
**输出：**true

思路：直接递归

三步走：

1.将问题化为若干个相同的小问题，每棵树都需满足：根节点满足平衡树的条件 && 左子树是棵平衡树 && 右子树是棵平衡树。

2.递归出口，当节点的地址为空时，返回true。

3.调用函数自己。

int height(struct TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return 1+fmax(height(root->left),height(root->right));
}
bool isBalanced(struct TreeNode* root)
{
    if(root==NULL)
    {
        return true;
    }
    return abs(height(root->left)-height(root->right))<=1 && 
    isBalanced(root->left) && 
    isBalanced(root->right);
}

谢谢观看，欢迎大家点赞评论收藏，如有任何问题，欢迎与作者交流。