目录

• 1.树的概念
• 2.二叉树的概念、结构及其性质
• • 2.1二叉树的概念
  • 2.2二叉树的特点
  • 2.3二叉树的结构
  • 2.4特殊的二叉树
  • 2.5二叉树的性质
• 3.二叉树的遍历
• • 3.1前序遍历
  • 3.2中序遍历
  • 3.3后序遍历
• 4.遍历的代码实现
• • 4.1前序递归实现(preorder)
  • 4.2中序递归实现(inorder)
  • 4.3后序递归实现(postorder)
• 5.判断叶子结点的个数
• 6.二叉树第 K 层的结点个数
• 7.二叉树的层序遍历(levelOrder)
• 8.前、中、后序遍历的非递归写法

1.树的概念

在数据结构中树是一种非线性的结构，它是由 n (n >= 0) 个有限的结点组成的一个具有层次的结构，结构上看起来像一个倒置的树

根结点：没有父节点（双亲结点），如结点 A
叶子结点：没有孩子结点的结点，如结点 D、E、F、G、H
兄弟结点：有相同的父节点两个结点，如结点 G 和 H
祖先结点：根到该结点之间经过的所有结点都是该结点的祖先结点
子孙结点：以某一结点为根结点的树中的任意结点都是该结点的子孙结点
结点的度：结点含有的子树的个数为该结点的度，叶子结点的度为 0
树的度：在树中最大的结点的度，该树的度为 2
树的层次：从根开始算，根为第一层，根的子结点为第二层，以此类推
森林：由 m 棵互不相交的树组成的集合

2.二叉树的概念、结构及其性质

2.1二叉树的概念

二叉树是由多个结点构成的集合，该集合可能为空，或者是一个根结点与其左右两个二叉子树所构成
二叉树是一种特殊的树

2.2二叉树的特点

1.二叉树的度是 <= 2 的，也就是说如果有孩子，最多就只有两个孩子
结点可以有 0，1，2 个孩子

2.二叉树是一种有序树

2.3二叉树的结构

将二叉树根结点的两个孩子，分别为左孩子 (left child) 和右孩子 (right child)

区分：左孩子和左子树，右孩子和右子树
孩子是一个结点
子树是一个结构(其中无论是否有结点 )

2.4特殊的二叉树

1.满二叉树
二叉树的每一层的结点个数都达到最大值，对于一个层数为 K 的树，其结点总数为 (2 ^ K) - 1 ，这种树就是满二叉树
2.完全二叉树
二叉树的叶子结点只出现在最后两层，而且最后一层的叶子结点都是靠左对齐的，这种树就是完全二叉树

2.5二叉树的性质

1.若规定根结点的层数为 1，那么一棵非空二叉树第 K 层上最多有 2 ^ (K - 1) {K > 0} 个结点
2.若规定只有根结点的二叉树的深度为 1，那么深度为 K 的二叉树最大结点个数为 (2 ^ K) - 1 {K >= 0} ，也就是一棵满二叉树
3.对任意一棵二叉树，如果其叶子结点的个数为 n0，度为 2 的结点个数为 n2，那么有 n0 = n2 + 1

3.二叉树的遍历

3.1前序遍历

一棵树的前序遍历 ：根【左子树的前序遍历】【右子树的前序遍历】
有 9 个结点，可以看作有 9 棵树存在
A : A B H I C D F G C
B : B H I
C : C D E F G
D : D E F G
E : E
F : F G
G : G
H : H
I : I

所以这棵树的前序遍历为：A B H I C D F G C

3.2中序遍历

一棵树的中序遍历 ：【左子树的中序遍历】根【右子树的中序遍历】
A : H B I A E D F G C
B : H B I
C : E D F G C
D : E D F G
E : E
F : F G
G : G
H : H
I : I

所以这棵树的中序遍历为：H B I A E D F G C

3.3后序遍历

一棵树的后序遍历 : 【左子树的后序遍历】【右子树的后序遍历】根
A : H I B E G F D C A
B : H I B
C : E G F D C
D : E G F D
E : E
F : G F
G : G
H : H
I : I

所以这棵树的后序遍历为 ：H I B E G F D C A

4.遍历的代码实现

4.1前序递归实现(preorder)

前序遍历时首先访问根结点，然后前序遍历其左子树，最后前序遍历其右子树，当二叉树为空树时直接返回即可，总结为：

1.访问根结点
2.前序遍历其左子树
3.前序遍历其右子树

代码实现
TreeNode 类

public class TreeNode {    public int val;     // 使用 public 是方便我们之后操作    public TreeNode left;   // 左孩子，如果左孩子不存在，通过 null 表示，左孩子不存在    public TreeNode right;    public TreeNode(int val) { this.val = val; this.left = null; this.right = null;    }

public static void preorder(TreeNode root) { if (root != null) {     System.out.printf("%c ", root.val);//首先打印根结点     preorder(root.left);//前序遍历其左子树     preorder(root.right);//前序遍历其右子树 }    }

4.2中序递归实现(inorder)

中序遍历时首先中序遍历左子树，然后访问根结点，最后中序遍历右子树，当二叉树为空树时直接返回即可，总结为：

1.中序遍历其左子树
2.访问根结点
3.中序遍历其右子树

代码实现

public static void inorder(TreeNode root) { if (root != null) {     inorder(root.left);//中序遍历左子树     System.out.printf("%c ", root.val);//打印根结点     inorder(root.right);//中序遍历右子树 }    }

4.3后序递归实现(postorder)

后序遍历时首先后序遍历左子树，然后后序遍历右子树，最后访问根结点，当二叉树为空树时直接返回即可，总结为：

1.后序遍历左子树
2.后序遍历右子树
3.访问根结点

代码实现

public static void postorder(TreeNode root) { if (root != null) {     postorder(root.left);//后序遍历左子树     postorder(root.right);//后序遍历右子树     System.out.printf("%c ", root.val);//打印根结点 }    }

5.判断叶子结点的个数

给定一棵二叉树，我们要求出其叶子结点的个数
1.首先我们的思路是，对二叉树进行遍历，对每一个结点进行确认是否为叶子结点，发现叶子结点则统计变量++
2.我们可以将大问题转化为小问题进行解决

我们规定：
左子树中的叶子结点个数为 leftLeafCount
右子树中的叶子结点的个数为 rightLeafCount
整棵树的叶子结点个数为 leftLeafCount + rightLeafCount
情况分为如上图所示的几种：
1.当二叉树为空树时，叶子结点个数为 0
2.当只有根结点时，叶子结点个数为 1
3.剩余情况，叶子结点个数为 leftLeafCount + rightLeafCount

还是以这棵树为例，该树的叶子结点个数为 4 ，分别是 H I E G
我们简单举例：
A 树的叶子结点个数 = B 树的叶子结点个数 + C 树的叶子结点个数
B 树的叶子结点个数 = H 树的叶子结点个数 + I 树的叶子结点个数
H 树和 I 树都没有左右孩子，那么满足第二种情况
则 H 和 I 树的叶子结点个数为 1
所以 B 树的叶子结点个数为 2
同理也可以得出 C 树的叶子结点个数进而得知 A 树的叶子结点个数，即整棵树的叶子结点个数

判断叶子结点的逻辑我们已经懂了，那么接下来就要将思路逻辑转化为我们的代码了，其实代码十分简单，我们已经有了思路就很好写了
代码实现

public static int leafCount(TreeNode root){ if(root == null){//空树的情况     return 0; } if(root.left == null && root.right == null){//只有根结点的情况     return 1; }//剩余情况 int leftLeafCount = leafCount(root.left);//计算其左子树的叶子结点个数 int rightLeafCount = leafCount(root.right);//计算其右子树的叶子结点个数 return leftLeafCount + rightLeafCount;//返回叶子结点总数    }

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

给定一棵二叉树，求出该树第 K 层的结点个数
1.我们要求第 K 层的结点个数，那么我们可以先求出该层作为第 K - 1 层时分布在左右子树中的结点个数，将大问题简化为小问题
2.收敛到一个特殊的情况：书的结点会越来越小，K 的值也会越来越小

root == null -> 0
root != null && k == 1 -> 1

以上图中的树为例，求第 3 层的结点个数
先求以 B 和 C 为根的两棵子树中该层为第 2 层时的结点个数
求该层为第 2 层时的结点个数，就要求出以 D E F G为根的 4 棵子树中该层为第1 层时的结点个数
代码实现

public static int calcLevelNodeCount(TreeNode root,int k){ if(root == null){//空树的情况     return 0; } if(k == 1){//处于第一层时结点个数就是 1      return 1; } int leftCount = calcLevelNodeCount(root.left,k - 1);//计算左子树中 k - 1 层时的个数 int rightCount = calcLevelNodeCount(root.right,k - 1);//计算右子树中 k - 1 层时的个数 return leftCount + rightCount;//返回结点总数    }

7.二叉树的层序遍历(levelOrder)

层序遍历就是首先从根结点出发，先访问第 1 层的根结点，然后从左向右访问第 2 层的结点，以此类推，自上而下，从左往右
层序遍历需要用到队列，需要将先进入队列的结点进行取出打印，先来的先服务

基本步骤如下：
1.首先将根结点放入队列，判断队列是否为空，不为空则进行循环
2.循环内容：
(1).取出队首结点并打印
(2).然后将其左右孩子按顺序放入队列(要对左右孩子是否为空进行判断)
3.按照前两部一直循环，直到遍历完所有结点，即队列为空

代码实现

 public static void levelOrder(TreeNode root) { if (root == null) {//空树则直接返回     return; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root);//将根结点放入队列 while (!queue.isEmpty()) {//若队列不为空一直循环     TreeNode node = queue.poll();//取出队首元素     System.out.printf("%c ", node.val);     if (node.left != null) {//左孩子不为空则放入队列  queue.offer(node.left);     }     if (node.right != null) {//右孩子不为空则放入队列  queue.offer(node.right);     } }    }

8.前、中、后序遍历的非递归写法

【数据结构】二叉树的遍历(非递归)