基本算法之二叉树

这几天忙于考PMP(Project Management Professional), 连续几个周末都在看书，终于在昨天考完试了，不知道能不能过，1个月后看吧，🙏~
言归正传，今天来学习了解一下二叉树。

什么是二叉树

![二叉树][1]

其实在程序中二叉树长这样

![二叉树][2]

二叉树是数据结构中非常重要的内容，在计算机科学中，每个结点最多有两个子树的结构被称作二叉树.

以下摘自百度:

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。
二叉树的第i层至多有2^{i-1} 个结点；深度为k的二叉树至多有2^k-1个结点；
对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。
而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。
具有n个节点的完全二叉树的深度为log2n+1。深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点。

基本概念

结点/子树

二叉树每个结点的的分支称作该结点的子树，其左侧分支称为左子树，右侧分支称为右字树。

树的结点

包含一个数据元素及若干指向子树的分支；

孩子结点

结点的子树的根称为该结点的孩子；

结点层次

一个结点的层次直观上来说就是其所在的行，其中根结点层次为1（第一行），其子结点层次为2（第二行），以此类推，第x行的结点为x。

二叉树的深度/高度

二叉树的深度（高度）指的是二叉树中的最大叶子结点所在的层。
二叉树的深度=max(左子树深度，右子数深度)+1，可用递归的方式实现。

结点的度

二叉树结点的度指该结点分支的个数，一棵非空二叉树结点的度只有以下三种情况：

• 没有分支的结点度为0 ：如下图中6、7、8、9、10
• 只有一个分支（左或右）结点度为1 ：如下图中
• 有两个分支的结点度为2：如下图中1、2、3、4

树的度

树中最大的结点度。

叶子结点

也叫终端结点，是度为 0 的结点；

分枝结点

度不为0的结点；

![二叉树][3]**二叉树结点的度最大为2.**

二叉树性质

1. 在非空二叉树中，第i层的结点总数不超过$2^{i-1}$, i>=1；
2. 深度为h的二叉树最多$2^h-1$有个结点_(h>=1)_，最少有h个结点
3. 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则: $N0=N2+1$；
4. 给定N个节点，能构成h(N)种不同的二叉树。
   h(N)为卡特兰数的第N项。$h(n)=C(2*n，n)/(n+1)$。
5. 设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和 $J=I+2i$;
6. 具有n个结点的完全二叉树的深度为$[log_2n]+1$([x] 表示不大于x的最大整数).

二叉树遍历方式

二叉树的基本遍历有三种：前序遍历、中序遍历和后序遍历，除此之外还有分层遍历等。其中基本遍历代码实现时可采用递归方式，其过程如下：

前序遍历

• 首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树，C语言代码如下：

void XXBL(tree*root){
//DoSomethingwithroot(处理根节点)
if(root->lchild!=NULL)
XXBL(root->lchild);
if(root->rchild!=NULL)
XXBL(root->rchild);
}

中序遍历

• 首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树，C语言代码如下

voidZXBL(tree*root)
{
if(root->lchild!=NULL)
ZXBL(root->lchild);
//DoSomethingwithroot(处理根节点)
if(root->rchild!=NULL)
ZXBL(root->rchild);
}

后序遍历

• 首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根，C语言代码如下

voidHXBL(tree*root){
if(root->lchild!=NULL)
HXBL(root->lchild);
if(root->rchild!=NULL)
HXBL(root->rchild);
//DoSomethingwithroot(处理根节点)

层次遍历

• 即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）
• 分层遍历（广度优先搜索）：用队列实现。队列初始化，压入根结点，队列不为空时，弹出一个结点，访问，左右子结点不为空时，压入左右子结点。

二叉树分类

完全二叉树

若设二叉树的高度为h，除第 h 层外，其它各层 (1-h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布

满二叉树

除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树

平衡二叉树(AVL)

二叉排序树，空，或左子树和右子树都是平衡二叉树，且深度差<=1

![二叉树类型图][4]

>