11、数据结构与算法 - 二叉树 （一）基本概念

二叉树

 1、二叉树的一些概念

（1）、度
 结点拥有的子树数目成为结点的度

（2）、层
 从跟开始定义，根为第1层，根的子结点为第2层，以此类推。

（3）、高度
 树中结点的最大层次。根结点为最高。从下往上数

（4）、深度
 同高度，从上往下

 
 2、树的5种形态

（1）、满二叉树
 双亲结点都有2个子结点

 
（2）、完全二叉树
 从根结点开始，最深一层以上的都是满二叉树。
 最后一层的叶子结点从左至右是连续的，不存在中间有空结点的情况
 
 

 3、二叉树的性质

 1、在二叉树的第 i 层上最多有2^(i-1) (2的i-1次方)个结点
 2、深度为 k 的二叉树最多有 2^k - 1 （2的k次方 - 1）个结点
 3、对于任何一颗二叉树T，如果其终端结点数为n0 ,度为2 的结点数为n^2，则n0 = n^2 +1
 4、具有那个结点的完全二叉树深度为（log2(n)）+1 (2的k次方=n 深度为 k + 1)
 5、对具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对二叉树的所有结点从1开始编号，则对于任意的序号为i的结点有
 （1）、如果i>1,那么序号为i的结点的双亲结点序号为i/2;（取整）
 （2）、如果i=1,那么序号为i的结点为根结点，无双亲结点；
 （3）、如果2i<=n,那么序号为i的结点的左孩子结点序号为2i；（非叶子结点）
 （4）、如果2i>n,那么序号为i的结点无左孩子；（叶子结点）
 （5）、如果2i+1<=n,那么序号为i的结点右孩子序号为2i+1;（非叶子结点）
 （6）、如果2i+1>n,那么序号为i的结点无右孩子。
 
 

 4、二叉树的遍历

 二叉树的遍历(Traversing binary tree)是指的从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅访问一次。
 关键词：访问、次序
 二叉树的遍历根据不同的需要分为

 1、前序遍历
 若二叉树为空，则空操作返回；
 否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
 也就是从根结点开始，先左子树的左结点，然后一直到叶子结点。然后访问对应叶子结点的双亲结点，的右结点。再向上双亲结点的双亲结点的右子树的左子结点等依次遍历如下图所示

 
 2、中序遍历
 若二叉树为空，则空操作返回；
 否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
 也就是从左子树的最下面一个结点依次开始，左结点、双亲结点、右结点（如果最下面的左结点下面还有右子节点，先当前左节点，然后右子节点，然后q双亲结点）
 如下图

 
 3、后序遍历
 若二叉树为空，这空操作返回；
 否则从左到右先叶子后结点的方式遍历左右子树，最后访问根结点。
 如下图

 
 4、层序遍历
 若二叉树为空，这空操作返回；
 否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中。按从左到右的顺序对接地那逐个访问。

 
 遍历对比