树的定义

树(Tree)是n(n≥0）个结点的有限集。n=O时称为空树。
在任意一棵非空树中:
(1)有且仅有一个特定的称为根( Root)的结点;
(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、……、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree )

1）n>0时，根节点是唯一的
2）m>0时，子树的个数没有限制，但是子树一定是互不相交的

• 结点分类

1. 结点拥有的子树数称为结点的度（Degree），度为0的结点称为叶节点或终端节点，度不为0的结点称为非终端结点或分支节点（内部节点）。
2. 树的度是树内各节点的度的最大值
   
   结点关系
   

树的存储结构

1. 双亲表示法
   每个结点中，附设一个指示器指向其双亲结点到链表中的位置
   

data：数据域，存储结点的数据信息
parent：指针域，存储该结点的双亲在数组中的下标

2. 孩子表示法

每个结点有多个指针域，其中每个指针指向一颗子树的根结点，我们吧这种方法叫做多重链表表示法

方案1：指针域的个数等于树的度。
如果树中各结点的度相差很大时，是很浪费空间的，有很多的结点，指针域都是空的，但是当各结点的度相差很小时，那就意味开辟的空间被充分的利用
方案2：每个结点的指针域的个数等于该结点的度，专门取一个位置存储结点指针域的个数
克服浪费空间的缺点，对空间的利用率提高，但是由于各结点的链表是不同的结构，还需要维护结点度的数值，带来了时间上的损耗
- 孩子表示法： 每个结点的孩子结点排列起来，以单链表做存储结构，则n个结点有n个孩子链表，叶子结点则表示该单链表为空，然后n个头指针组成一个线性表，采用顺序存储结构，存放进一维数组中

3. 孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，因此设计两个指针，分别指向该结点的第一个孩子和此结点的右兄弟

二叉树

1. 定义： 是n个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树构成。

满足两个条件：

1. 本身是有序树
2. 树中包含的各个结点的度不能超过2，只能是0,1,2

二叉树的性质

1. 二叉树中，第i层最多有2^i-1个结点
2. 如果二叉树的深度为k，那么此二叉树最多有2^k-1个结点
3. 二叉树中，终端结点数（叶子结点数）为n0,度为2的结点数为n2,则n0=n2+1
4. 

满二叉树

二叉树中除了叶子结点，每个结点的度都为2，则此二叉树称为满二叉树

• 满二叉树的性质
  1.满二叉树中第 i 层的节点数为 2^(i-1) 个。
  2.深度为 k 的满二叉树必有 2^k-1 个节点 ，叶子数为 2^k-1。
  3.满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
  4.具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树

二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树

• 满二叉树一定是完全二叉树，但完全二叉树不一定是满的

完全二叉树从右向左依次标号，对于任意结点i来说：

1. 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
2. 如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i
3. 如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1

二叉树的存储结构

顺序存储、链式存储

二叉树的顺序存储

使用顺序表(数组)存储二叉树，顺序存储只适用于完全二叉树，如果想顺序存储普通二叉树，则需要提前将普通二叉树转化为完全二叉树

完全二叉树的顺序存储仅需从根结点开始，按照层次依次将树中结点存储到数组即可

若结点i有左右孩子，则其左孩子结点为2i，右孩子结点为2i+1

二叉树的链式存储

顺序存储二叉树，如果是普通二叉树会造成空间浪费的现象。
结点结构：

• 指向左孩子结点的指针（Lchild）
• 结点存储的数据（data）
• 指向右孩子结点的指针（Rchild）
  

typedef struct BiTNode
{
	ElemType data;
	BiTNode* Lchild; //左孩子
	BiTNode* Rchild; //右孩子
}BiTNode,*BiTree;
1
2
3
4
5
6

二叉树的建立

将二叉树的每个结点的空指针引出一个虚结点，它的值是特定值，比如‘#’，称这种处理后的二叉树为原二叉树的扩展二叉树。

 //递归建立
void CreateBiTree(BiTree* T) //AB#D##C##扩展二叉树
{
	ElemType ch;
	cin >> ch;
	if (ch == '#')
		*T = NULL;
	else {
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)
		{
			exit(OVERFLOW);
		}
		(*T)->data = ch;
		CreateBiTree(&(*T)->Lchild);  //构造左子树
		CreateBiTree(&(*T)->Rchild);  //构造右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二叉树的遍历

• 指从根结点出发，按照某种次序以此访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

二叉树前序遍历

• 规则： 若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
  前序遍历结果为：ABDGHCEIF

	void PreOrderTraverse(BiTNode* Root)     //前序遍历 递归实现
	{
		if (Root == NULL) return;
		cout << Root->data << " ";
		PreOrderTraverse(Root->Lchild);    
		PreOrderTraverse(Root->Rchild);
	}	
1
2
3
4
5
6
7

二叉树中序遍历

• 规则： 若树为空，则空操作返回，否则从根结点开始，中序遍历根结点的左子树，然后是访问根节点，最后中序遍历右子树
  中序遍历结果为：GDHBAEICF

	void InOrderTraverse(BiTNode* Root)     //中序遍历 递归实现
	{
		if (Root == NULL) return;
		InOrderTraverse(Root->Lchild);
		cout << Root->data << " ";
		InOrderTraverse(Root->Rchild);
	}

1
2
3
4
5
6
7
8

二叉树后序遍历

• 规则： 若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根节点
  后序遍历结果为：GHDBIEFCA

	void PostOrderTraverse(BiTNode* Root)     //后序遍历 递归实现
	{
		if (Root == NULL) return;
		PostOrderTraverse(Root->Lchild);
		PostOrderTraverse(Root->Rchild);
		cout << Root->data << " ";
	}
1
2
3
4
5
6
7

二叉树层序遍历

• 规则： 若树为空，则空操作返回，否则从树的第一层，根结点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问
  层序遍历结果为：ABCDEFGHI

推导遍历结果

例题： 前序遍历序列为ABCDEF，中序遍历序列CBAEDF，请问后续遍历序列是？

先分析出A是根结点，那么从中序可以看出 B,C是A的左子树上结点，D,E,F是A的右子树上结点，在看B,C前序先输出B，则B是A的左孩子，C是B的结点，从中序可以看出先输出C,在输出B，则C是B的左孩子，同理前序可以看出D是A的右孩子，E,F是D的孩子结点，中序可以看出先输出E,D,F，则E是D的左孩子，F是D的右孩子。
最终二叉树为

• 已知前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
• 已知后序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
• 已知前序和后序遍历，不能唯一确定一颗二叉树

线索二叉树

指向前驱和后继电脑指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树

typedef enum{Link,Thread} PointerTag;
//link==0表示指向左右孩子指针
//thread==1表示指向前驱或后继的线索
typedef struct BiThrNode
{
	ElemType data; //数据
	BiThrNode *Lchild,*Rchild;
	PointerTag Ltag;
	PointerTag Rtag;
};
1
2
3
4
5
6
7
8
9
10

树、二叉树转换

步骤：

1. 加线：所有的兄弟结点之间加一条连线
2. 去线：对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点的连线
3. 层次调整，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。第一个孩子是二叉树结点的左孩子，兄弟转换过来是孩子结点的右孩子