那些年错过的数据结构与算法(九)

本篇文章将结合《算法》第4版、业界大牛的博客和自己的理解，具体描述二叉树的一些概念，如有错误，请大佬指出。如有侵权，请联系我删除，谢谢。

二叉树

1.基本概念

• (1)二叉树是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树所组成。
  二叉树具有以下特点：二叉树可以为空，空的二叉树没有结点，非空二叉树有且只有一个根结点；每一个结点最多只有2棵子树，且分别称为该结点的左子树和右子树；二叉树的子树有左、右之分，其次序不能任意颠倒。

• (2)满二叉树和完全二叉树
  满二叉树是指除了最后一层外，每一层上的所有结点都有2个子结点的二叉树。
  完全二叉树是指除了最后一层外，每一层上的结点树均达到最大值，在最后一层上只缺少右边的若干结点。
  满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

2.主要性质(原谅我不知道怎么打上标>.<)

• 一棵非空二叉树的第k层上最多有(2的k-1次方)个结点(K≥1)；
• 深度为m的满二叉树中有(2的m次方-1)个结点；
• 对任何一棵二叉树而言，度为0的结点(即叶子结点)总是比度为2的结点多一个；
• 具有n个结点的二叉树的深度k至少为[log₂n]+1,其中[log₂n]取log₂n的整数部分；
• 具有n个结点的完全二叉树的深度为[log₂n]+1；
• 设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左往右)用自数1，2···，n给结点进行编号，则对于编号为k(k=1,2···,n)的结点有以下结论：
  若 k = 1，则该结点为根结点，它没有父结点；
  若 k > 1，则该结点的父结点编号为k/2;
  若 2k ≤ n，则编号k的结点的左子结点编号为2k，否则该结点无左子结点(显然也没有右子结点)；
  若 2k + 1 ≤ n，则编号为k的结点的右子结点编号为2k+1，否则该结点无右子结点。

3.存储结构

二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由数据域和指针域组成。由于每个元素可以有2个后件(即2个子结点)，所以用于存储二叉树的存储结点的指针域有2个：一个指向该结点的左子节点的存储地址，称为左指针域；另外一个指向该结点的右子结点的存储地址，称为右指针域。因此二叉树的链式存储结构也成为二叉链表。二叉树的一个存储结点如下：

左指针域	数据域	右指针域
L(i)	Data(i)	R(i)

对于满二叉树和完全二叉树，可以按层级进行顺序存储。

4.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有结点。分为前序遍历，中序遍历和后序遍历。

• 前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树。
• 中序遍历首先访问左子树，然后遍历根结点，最后遍历右子树。
• 后序遍历首先访问左子树，然后遍历右子树，最后遍历根结点。

下面用一个二叉树的例子进行说明，

tree.png

对该二叉树进行3种遍历，

• 前序遍历的结果为：A-B-D-G-E-H-C-F-I
• 中序遍历的结果为：G-D-B-E-H-A-C-F-I
• 后序遍历的结果为：G-D-B-E-H-I-F-C-A

总结：

• 已知前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树；
• 已知后序遍历序列和中序遍历序列，可以唯一确定这棵二叉树；
• 已知前序遍历序列和后序遍历序列，不能确定二叉树。

这一篇讲的是二叉树的基本要点，内容挺多，还很重要，笔试常考点，需要重视。下一篇讲查找技术，讲应用最广泛的顺序查找和二分法查找。敬请期待哦<(￣︶￣)>。