一篇文章详解二叉树

很多同学对二叉树都是懵圈的，尤其是备考计算机二级的同学，经常遇到二叉树的题型就无从下手，那么阿福老师给你们详细讲解二叉树。

一：什么是二叉树？

字面定义：二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

不理解正常，来看下面几个图。

1、空二叉树——（a） ；

2、只有一个根节点的二叉树——（b） ；

3、只有左子树——（c） ；

4、只有右子树——（d） ；

5、完全二叉树——（e） 。

二：接下来看看二叉树的度？

度=节点总数-1。在树中，每个节点有多少条边出去，该节点的度就为多少。

哪一个是度？看一下这个图就知道哪一个是度，

哪一个是节点？看图就知道。

从上面的几个图是不是对二叉树，二叉树的度，二叉树的节点有一个大概了解。

三：接下来我们来看看二叉树的遍历

二叉树（递归）遍历分为三种，分别为先序遍历、中序遍历和后序遍历。

1）先序遍历：按照“根节点->左子树->右子树”的顺序访问二叉树，先序遍历结果：A BDFE CGHI

特别强调：

先序遍历（Preorder Traversal）也称为前序遍历或先根遍历，是一种二叉树遍历方法，

其遍历顺序是：先访问根节点，然后遍历左子树，最后遍历右子树。‌

2）中序遍历：按照“左子树->根节点->右子树”的顺序访问二叉树，中序遍历结果：DBEF A GHCI

中序遍历结果：DBEF A GHCI

3）后序遍历：按照“左子树->右子树->根节点”的顺序访问

后序遍历的结果：DEFB HGIC A

大体上基本对二叉树有简单了解了。

考题一：经常考到的题，二叉树遍历，下图，一般题目给二叉树前序，中序，后续，考察二叉树有多少度，多少节点。

第二题：掌握知识点

叶子节点与度为2的节点数的关系‌：

如果一个二叉树中度为2的节点数量为 n2，那么该二叉树的叶子节点数量 n0必定为 n2+1,

即 n0= n2+1。这表明，通过知道度为2的节点数量，可以直接计算出叶子节点的数量。

高频考题：

12.一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为(A)

A.16

B.10

C.6

D.4

解析：根据二叉树的性质，n=n0+n1+n2(n表示总结点数，n0表示叶子结点数，nl表示度数为1的结点数，n2表示度数为2的结点数)，而叶子结点数总是比度数为2的结点数多1，所以n2=n0-1=5-1=4，而n=25，所以nl=n-n0-n2=25-5-4=16。