1、树和二叉树的定义

树型结构是一种非线性的数据结构，节点之间是一种一对多的关系，节点之间有分枝，节点之间具有层次关系。

树(Tree) 的定义：树是n( n≥0)个结点的有限集合。若 n=0，则称之为空树；若  n>0，并且有且仅有一个特定的节点，称之为根(Root) 结点；其余结点可以分为 (m≥0)个互不相交的有限集 T1,T2,...,Tm，其中每一个子集本文又是一个树，称之为根的子树(SubTree)。

1.1 树的基本术语

节点的度：结点拥有的子树的个数。树的度： 树内各结点的度的最大值。叶子节点 ：度为0的结点，也叫终端结点。分枝节点 ：度不为0的节点叫做分枝节点，根节点以外的分枝节点称为内部结点。结点的子树的根称为该结点点的孩子，该结点称为孩子的双亲。结点的祖先：从根节点到该结点所经分枝上的所有的结点；节点的子孙：以某节点为根的子树中的任意一个结点。

树的深度为树中结点的最大层数。

树中结点的各个子树从左至右是有次序的(最左边是第一个孩子)，则称之为有序树；树中节点的各个子树之间是没有次序的，则称之为无序树。

森林是m(m≥0)棵互不相交的树的集合。如果把某一棵树的根节点删除，那这个数就变成了森林。一棵树也可以看成一个特殊的森林。给森林中的各个子树添加一个双亲节点，则森林就可以变成一棵树。

1.2 树型结构和线性结构的比较

1.3 二叉树的定义

普通树(多叉树)若不转化为二叉树，则运算很难实现；二叉树的结构最简单，规律性很强；可以证明，所有树都能转化成为二叉树，二叉树在应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树都可以与二叉树进行转化，这样就解决了树的存储结构及其运算中存在的复杂性。

二叉树是 (n≥0)个结点的有限集，它或者是空集，或者由一个根节点以及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

1.4 二叉树的特点

二叉树每个结点最多有两个孩子，二叉树中不存在度大于2的节点；

子树有左右之分，其次序不能颠倒；

二叉树可以是空集，根可以有空的左子树或者空的右子树

二叉树不是树的特殊情况，他们是两个概念。二叉树和树的主要区别是二叉树是有次序的，二叉树节点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树还是右子树；当树的结点只有一个孩子时，就无需区分它是左还是右的次序。

二叉树的5种基本形态：

1.5 二叉树的抽象类型定义

1.6 二叉树的性质

性质1： 在二叉树的第i层上最多有  2i−1(i≥1)个节点。

性质2： 深度为k的二叉树至多有 2k−1(k≥1)个结点，最少有k个结点。

性质3： 对任意一颗二叉树  T，如果其叶子数为  n0，度为2的节点数为n2，则 n0=n2+1，即叶子节点的数目是度为2的结点的数量再加1。

满二叉树： 一颗深度为k的二叉树，若其结点数量为 2^k-1 个，则称其为满二叉树。

满二叉树的特点： 每一层的结点数都是最大结点数，即每层都满；叶子结点全部在最底部；满二叉树在同样深度的二叉树中结点个数最多；满二叉树在同样深度的二叉树中叶子结点个数最多。

完全二叉树： 深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。

完全二叉树性质： 满二叉树一定是完全二叉树。 在 满二叉树中，从最后一个结点开始，连续去掉人一个结点，得到的是一颗完全二叉树。完全二叉树的叶子结点只可能分布在层次最大的两层上；对任意一个结点，如果其右子树的最大层次为i，则其左子树的最大层次必定为i或者i+1。

性质4： 具有n个结点的完全二叉树的深度为  ⌊log2n⌋+1。

性质5： 如果对一颗有n个结点的完全二叉树，对其进行从上到下，从左到右的编号，则对于任意一个结点有：

如果  i=1，则结点i是二叉树的根，无双亲；如果 i>1，则其双亲节点时 ⌊i/2⌋

如果  2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是节点 2i

如果 2i+1>n，则结点i为叶子结点，无右孩子；否则，其右孩子结点是 2i+1

2 、二叉树的存储结构

2.1 二叉树的顺序存储

按照满二叉树的结点层次进行编号，依次存放二叉树中的数据元素。

#define MAXTSIZE 100
typedef TElemType SqBiTree[MAXTSIZE];
SqBiTree bt;

二叉树顺序存储的缺陷：顺序存储的可用空间固定；对于右单支树而言，顺序存储会造成较多的存储空间的浪费，存储密度过低的问题。结点之间的关系蕴含在其存储位置之中，浪费空间，适于存满二叉树和完全二叉树。

2.2 二叉树的链式存储结构

2.2.1 二叉链表存储结构

typedef struct BiNode
{
  TElemType data;
  struct BiNode *lChild, *rChild;
}*BiTree;

在n个结点的二叉链表中，有  n+1个空指针域。因为在有n个节点的二叉链表中，必定有  2n个链域。另外，除根节点以外，每个结点有且仅有一个双亲，所以只会有 n−1个结点的链域存放指针，指向非空的子女结点。所以空指针域的数量可以计算为： 2n−(n−1)=n+1个。

2.2.2 三叉链表存储结构

typedef struct TriTNode
{
  TElemType data;
  struct TriTNode *lChild, *parent, *rChild;
}*TriTree;

3、遍历二叉树和线索二叉树

3.1 二叉树的遍历

遍历定义： 顺着某一条搜索路径寻访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次，又称为周游。这种访问不破坏原来的数据结构。

遍历目的： 得到树中所有结点的一个线性排列；

遍历用途： 它是树结构插入，删除，修改，查找和排序运算的前提，是二叉树一切运算的基础和核心。

遍历方法： 前序遍历(根-左子树-右子树)；中序遍历(左子树-根-右子树)；后序遍历(左子树-右子树-根) 。

根据遍历序列确定二叉树： 若二叉树中各个结点的值均不相同，则二叉树结点的前序遍历，中序遍历和后序遍历序列都是唯一的。由二叉树的前序和中序序列，或者由二叉树的后序和中序序列可以确定唯一一颗二叉树。

通过前序和中序遍历确定二叉树的示意图如下所示：

通过后序和中序遍历确定二叉树的示意图如下所示：

前序遍历实现：

void PreOrderTraverse(BiTree T)
{
  if (BiTree == nullptr) return;
  visit(T);   //访问根节点
  PreOrderTraverse(T->lChild);//递归遍历左子树
  PreOrderTraverse(T->rChild);//递归遍历右子树 
}

先序遍历递归调用的过程如下图所示：

中序遍历实现：

void InOrderTraverse(BiTree T)
{
  if (BiTree == nullptr) return;
  InOrderTraverse(T->lChild);//递归遍历左子树
  visit(T);   //访问根节点
  InOrderTraverse(T->rChild);//递归遍历右子树  
}

后序遍历实现：

void PostOrderTraverse(BiTree T)
{
  if (BiTree == nullptr) return;
  PostOrderTraverse(T->lChild);//递归遍历左子树
  visit(T);   //访问根节点
  PostOrderTraverse(T->rChild);//递归遍历右子树  
}

从上述实现代码可知，三种遍历算法如果去掉visit(T)语句，三种算法时完全相同的，这三种算法的访问路径是相同的，只是访问的时机不同，二叉树中每个结点访问的次数都是3次。

当第1次经过结点时访问=前序遍历；第2次经过时访问=中序遍历；第3次经过时访问=后序遍历。

递归算法的时间效率： O ( n ) O(n) O(n)，每个节点只访问一次；空间效率： O ( n ) O(n) O(n)，因为最坏情况下栈占用的最大辅助空间是n个。