二叉树及二叉树的应用
1、基本概念
叶子节点：叶子节点只有父节点没有子节点；
根节点：起始的节点叫做根节点,整棵树只有一个根节点；
父节点：除了根节点之外，每个节点都有且只有一个父节点；
满二叉树：每个枝节点都有两个子节点，则该二叉树叫做满二叉树；
完全二叉树：二叉树中除了最下面一层之外，每层节点个数均达到最大值，并且最下面一层的节点都连续集中在左侧，则该二叉树叫做完全二叉树；
2、基本特征
二叉树具有递归嵌套式的空间结构，也就是说对于一棵二叉树来说，可以拆分为若干个小二叉树组成，因此采用递归的方法处理二叉树比较方便，处理方式如下：
处理(二叉树)
{
if(是空树) 直接处理完毕;
else
{
处理根节点;
处理左子树; => 递归
处理右子树; => 递归
}
}
3、二叉树遍历3.1 所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。
遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算的基础。
3.2 二叉树遍历方式：先序遍历、中序遍历(投影)、后序遍历
图 3.2 二叉树遍历
4、存储结构
4.1 线性(顺序)存储结构
一般来说，从上到下，从左到右依次存储节点，对于非完全二叉树来说，采用虚节点来补成完全二叉树
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。图4.1.1(a)是一棵完全二叉树，图4.1.1（b）给出的图4.1.1(a)所示的完全二叉树的顺序存储结构。
(a) 一棵完全二叉树 (b) 顺序存储结构
图 4.1.1 完全二叉树的顺序存储示意图
对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。如图4.1.2给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。最坏的情况是右单支树，如图4.1.2 所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。
(a) 一棵二叉树 (b) 改造后的完全二叉树
(c) 改造后完全二叉树顺序存储状态
图4.1.2 一般二叉树及其顺序存储示意图
(a) 一棵右单支二叉树 (b) 改造后的右单支树对应的完全二叉树
(c) 单支树改造后完全二叉树的顺序存储状态
图 4.1.3 右单支二叉树及其顺序存储示意图
结构5-1二叉树的顺序存储
#define Maxsize 100 //假设一维数组最多存放100个元素 typedef char Datatype; //假设二叉树元素的数据类型为字符 typedef struct { Datatype bt[Maxsize]; int btnum; }Btseq;
4.2 链式存储结构
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：
其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表，如图4.2.1所示。
(a) 一棵二叉树 (b) 二叉链表存储结构
图 4.2.1 二叉树的二叉链表表示示意图
为了方便访问某结点的双亲，还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。每个结点由四个域组成，其结点结构为：
这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。
图4.2.2 给出了图4.2.1 (a)所示的一棵二叉树的三叉链表表示。
图4.2.2 二叉树的三叉链表表示示意图
尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。
结构4.2二叉树的链式存储
#define datatype char //定义二叉树元素的数据类型为字符 typedef struct node //定义结点由数据域，左右指针组成 { Datatype data; struct node *lchild,*rchild; }Bitree;
一般来说,每个节点中除了存储数据元素本身之外，还需要两个指针，分别记录左右子节点的地址
如：
typedef struct Node
{
int data;//数据内容
struct Node* left;//记录左子树的地址
struct Node* right;//记录右子树的地址
}Node;
5、有序二叉树
当左子树不为空时，则左子树的元素值小于等于根节点；
当右子树不为空时，则右子树的元素值大于等于根节点，左右子树也分别有序，满足上述特征的二叉树，叫做有序二叉树
50 70 20 60 40 30 10 90 80
要求以元素50作为根节点，将上述元素组成一棵有序二叉树，并且使用三种方法进行遍历
解析：
50 80
/ \
20 70
/ \ / \
10 40 60 90
/ /
30 80
先序遍历：50 20 10 40 30 70 60 90 80
中序遍历：10 20 30 40 50 60 70 80 90 (掌握)
后序遍历：10 30 40 20 60 80 90 70 50
6、实际应用
主要用于搜索和查找数据的程序中，查找速度比较快，也比较方便，叫做二叉查找树。
7、二叉树考点
7.1 二叉树深度：
深度为m的满二叉树有2^m-1个结点；
具有n个结点的完全二叉树的深度为[log2n]+1.（log2n是以2为底n的对数）；
7.2某二叉树共有七个结点，其中叶子结点只有一个，则该二叉树的深度为——
因为叶子节点为1个，按二叉树理论得出（任意一棵二叉树中度为0的节点总是比度为2的节点多一个），故得出此二叉树度为2的节点为0个；
7（总节点）-1（度为0）- 0（度为2）=6（度为1）。故证明此二叉树每层只有1个节点，总共7层。