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

【那些年错过的数据结构与算法(九)】本篇文章将结合《算法》第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个：一个指向该结点的左子节点的存储地址，称为左指针域；另外一个指向该结点的右子结点的存储地址，称为右指针域。因此二叉树的链式存储结构也成为二叉链表。二叉树的一个存储结点如下：