目录
1.前言
二叉树是数据结构中比较难的数据结构之一，树在计算机中的应用也是非常广泛，例如文件系统、数据库查询、图形处理等。树结构的优点是：可以用来表示关系，可以用来存储和查询大量数据，可以用来实现文件管理和数据库管理等功能。接下来，让我们一起去认识并学习树和二叉树！
2.树
2.1树的概念
树是一种 非线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看 起来像一棵 倒挂的树，也就是说它是根朝上，而叶朝下的 。它具有以下的特点：
有一个特殊的结点，称为 根结点，根结点没有前驱结点 ；除根结点外，其余结点被分成 M(M > 0) 个互不相交的集合 T1 、 T2 、 ...... 、 Tm ，其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每 棵子树的根结点有且只有一个前驱 ，可以有 0 个或多个后继；树是 递归 定义的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构 。
2.2树中的重要概念
- 结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6。
- 树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6。
- 叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I...等节点为叶结点。
- 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点。
- 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点。
- 根结点：一棵树中，没有双亲结点的结点；如上图：A。
- 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
- 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4。
2.3树的表示形式
实际中树有很多种表示方式，如： 双亲表示法 ， 孩子表示法 、 孩子双亲表示法 、 孩子兄弟表示法 等等。最常用的是 孩子兄弟表示法 。
class Node {
int value; // 树中存储的数据
Node firstChild; // 第一个孩子引用
Node nextBrother; // 下一个兄弟引用
}
2.4树的应用
树的应用非常广泛，比如文件系统管理（目录和文件）。
3.二叉树
3.1概念
一棵二叉树是结点的一个有限集合，该集合：1. 或者为空2. 或者是由 一个根节 点加上两棵别称为 左子树 和 右子树 的二叉树组成。
从上图可以看出：
1. 二叉树不存在度大于2的结点
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的
3.2两种特殊的二叉树
1. 满二叉树:一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是2^k -1，则它就是满二叉树。
2. 完全二叉树 : 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n个结点的二叉树，当且仅当其每一个结点都与深度为K 的满二叉树中编号从 0 至 n-1的结点一一对应时称之为完全二叉树。要注意的是 满二叉树是一种特殊的完全二叉树 。
3.3二叉树的性质
1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个节点(i > 0)。2.若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大节点数是2^k - 1(k >= 0)
3.对任何一棵二叉树，如果其叶节点个数为n0，度为2的非叶节点个数为n2，则有n0 = n2 +1
4.具有n个节点的完全二叉树的深度k为log₂(n + 1)向上取整
5.对于具有n个节点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的节点有：
- 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
- 若2i+1<n，左孩子序号：2i+1，否则无左孩子
- 若2i+2<n，右孩子序号：2i+2，否则无右孩子
下面给大家来几道例题牛刀小试一下。
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 1992.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/23.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 3864.一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12答案：
1.B (199+1)
2.A 2n = n0 + n1 + n2，n0 = n2 + 1，n1 = 1，因此 n0 = n
3.B n0 + 0 + n0 - 1 = 767 可得n0 = 384
4.B log₂(531 + 1) 解出h = 10
3.4二叉树的存储
二叉树的存储结构 分为： 顺序存储 和 类似于链表的链式存储 。
下面我们主要以链式存储来讲解。
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式 ，具体如下：
//孩子表示法
class Node {
int val; //数据域
Node left; //左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; //右孩子的引用，常常代表右孩子为根的整棵右子树
}
//孩子双亲表示法
class Node {
int val; //数据域
Node left; //左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; //右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; //当前节点的根节点
}本文后面主要采用孩子表示法创建二叉树。
3.5二叉树的遍历方式
3.5.1创建二叉树
目前我们这里是手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，并不是真正的创建二叉树的方式。
public class BinaryTree {
public class TreeNode {
TreeNode left;
TreeNode right;
int val;
public TreeNode(int val) {
this.val = val;
}
}
public TreeNode createTree() {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
return node1;
}
}3.5.2二叉树的遍历
1. 前中后序遍历
所谓遍历 (Traversal) 是指沿着某条搜索路线，依次对树中每个结 点均做一次且仅做一次访问 。 访问结点所做的操作依赖于具体的应用问题 ( 比如：打印节点内容 ) 。遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算的基础。
根据遍历根节点的先后次序有以下遍历方式：
前序遍历 ： 访问根结点—— > 根的左子树—— > 根的右子树。中序遍历：根的左子树——>根节点—— >根的右子树。后序遍历：根的左子树——>根的右子树—— >根节点。
- 前序遍历
代码实现如下：
//前序遍历
public void preOrder(TreeNode root) {
//如果是空树则不需要遍历
if (root == null) {
return;
}
System.out.print(root.val + " ");//访问根节点
preOrder(root.leftNode);//前序遍历左子树
preOrder(root.rightNode);//前序遍历右子树
}- 中序遍历
代码实现如下：
//中序遍历
public void inOrder(TreeNode root) {
//如果是空树则不需要遍历
if (root == null) {
return;
}
inOrder(root.leftNode);//中序遍历左子树
System.out.print(root.val + " ");//访问根节点
inOrder(root.rightNode);//中序遍历右子树
}- 后序遍历
代码实现如下：
//后序遍历
public void postOrder(TreeNode root) {
//如果是空树则不需要遍历
if (root == null) {
return;
}
postOrder(root.leftNode);//后序遍历左子树
postOrder(root.rightNode);//后序遍历右子树
System.out.print(root.val + " ");//访问根节点
}下面简单举个例子：
public class Test {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root =binaryTree.createTree();
System.out.println("前序遍历：");//前序遍历结果：1 2 4 5 3 6
binaryTree.preOrder(root);
System.out.println();
System.out.println("中序遍历：");//中序遍历结果：4 2 5 1 6 3
binaryTree.inOrder(root);
System.out.println();
System.out.println("后序遍历：");//后序遍历结果：4 5 2 6 3 1
binaryTree.postOrder(root);
}
}运行结果如下：
上面所创建出来的二叉树画出来就是下面这样子。
2.层序遍历
设二叉树的根节点所在层数为1 ，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推， 自上而下，自左至右 逐层访问树的结点的过程就是层序遍历。
以上面创建的二叉树为例，实现层次遍历的代码如下：
public void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return;
}
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val + " ");
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
System.out.println();
}我们通过队列实现层序遍历的功能，只要队列不为空，就把获取到的队头元素给cur，并且同时将这个元素打印出来，在把cur的左右两边代进去，如果左右两边为空的则不能代进去，只有非空才能代入里面。
下面给大家来几道关于二叉树遍历的习题练练手。
1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为 ()A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA2. 二叉树的先序遍历和中序遍历如下：先序遍历： EFHIGJK; 中序遍历： HFIEJKG. 则二叉树根结点为 ()A: E B: F C: G D: H3. 设一课二叉树的中序遍历序列： badce ，后序遍历序列： bdeca ，则二叉树前序遍历序列为 ()A: adbce B: decab C: debac D: abcde4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出 ( 同一层从左到右 ) 的序列为 ()A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF答案：1.A 2.A 3.D 4.A
3.6二叉树的基本操作
1.获取树中节点的个数
//获取树的节点个数
//方法1：递归
public int size(TreeNode root) {
if (root == null) {
return 0;
}
int ret = size(root.left) + size(root.right) + 1;
return ret;
}
//方法2：遍历
public static int nodeSize;
public void size1(TreeNode root) {
if (root == null) {
return;
}
nodeSize++;
size1(root.left);
size1(root.right);
}public class Test {
//二叉树的基本操作
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BinaryTree.TreeNode root = binaryTree.createNode();
binaryTree.preOrder(root);
System.out.println();
binaryTree.inOrder(root);
System.out.println();
binaryTree.postOrder(root);
System.out.println();
System.out.print("树的节点个数：");
System.out.println(binaryTree.size(root));
}
}运行结果如下：
2.获取叶子节点的个数
//获取叶子节点的个数
//方法1
public int getLeafNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
//方法2：遍历
public int leafSize;
public void getLeafNodeCount1(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
leafSize++;
}
getLeafNodeCount1(root.left);
getLeafNodeCount1(root.right);
}
3. 获取第K层节点的个数
//第K层有多少个结点
public int getKLeaveNodeCount(TreeNode root, int k) {
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return getKLeaveNodeCount(root.left, k - 1)
+ getKLeaveNodeCount(root.right, k - 1);
}
4.获取二叉树的高度
//求二叉树的高度
//时间复杂度：O(N)
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leafHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return leafHeight > rightHeight ?
leafHeight + 1 : rightHeight + 1;
}
5.检测值为value的元素是否存在
// 检测值为value的元素是否存在
public TreeNode find(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
TreeNode ret = find(root.left, val);
if (ret != null) {
return ret;
}
ret = find(root.right, val);
if (ret != null) {
return ret;
}
return null;
}
6.判断一棵树是不是完全二叉树
//判断一棵树是不是完全二叉树
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return true;
}
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur == null) {
break;
}
queue.offer(cur.left);
queue.offer(cur.right);
}
while (!queue.isEmpty()) {
TreeNode node = queue.peek();
if (node != null) {
return false;
} else {
queue.poll();
}
}
return true;
}
4.总结
本文的重点是树中的重要概念和二叉树的性质、遍历方式以及基本操作，小伙伴们在学习有关二叉树的内容，一定要画出二叉树，能够帮助我们更好地理解，再去编写代码。
