数据结构-树与二叉树

树与二叉树

1. 什么是树

顾名思义，第一想到的就是路边的树，有树干、树根、树叶，数据结构中的树也是这样延伸过来的，只不过专用名词不一样，如图
关于树的一些专有名词：A 是 B 的父节点，B 是 A 的子节点，D 是 B 的兄弟节点，C 和 D 称为叶子节点，A 为根节点。
树的高度：根节点到叶子节点的最长路径
节点的高度：节点到叶子节点的高度
节点的深度：该节点到根节点的路径，也就是边的数量
树的深度：树从根结点开始往下数，叶子结点所在的最大层数
层：根节点为第一层，依次往下递增。

2. 什么是二叉树

二叉树，就是给树做了一个条件限制，除了叶子结点，其余每个节点有且只有两个子节点（也就是只有两个叉）。
二叉树有两个很重要的形态就是满二叉树和完全二叉树。
满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。
完全二叉树：叶子节点都在最底下两层 ，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。

3. 二叉树的存储方式

链式存储法：基于指针的链式存储，每个树的节点都是由数据域和两个指针域组成的。数据域用来存储数据，指针域用来存储左右两个子节点。
顺序存储法：顺序存储就是用数组来存储的，虽然不如指针域那么直观，但是存储的方法挺好理解的。根节点存储在下标 i= 1 的位置；左子节点存储在下标i * 2 = 2的位置，右子节点存储在i * 2 + 1 =3的位置。
数组的方式存储不需要开辟额外的指针空间，但是数组需要的内存空间是连续的，如果连续的内存空间不足，就无法进行存储。

4. 二叉树的遍历

有四种遍历的方式，分别为前序遍历、中序遍历、后序遍历、按层遍历。
前序遍历：先遍历根节点、然后遍历左子节点、最后遍历右子节点

中序遍历：先遍历左子节点，然后是根节点，最后是右子节点
后序遍历：先遍历左子结点，然后遍历右子节点，最后遍历根节点
层次遍历：从二叉树的第1层开始，按照从上层到下层，同一层中按照从左到右的顺序对每个结点访问一次且仅一次。
基本思想是：先访问根结点，再依次访问根的左孩子和右孩子，左孩子的左孩子和右孩子，以及右孩子的左孩子和右孩子。这样一层一层进行，直到遍历二叉树中的所有结点。

遍历顺序：A-B-C-D-E-H-F

5. 代码（C语言）

前序遍历

void PreOrderTraverse (BTree root)
{//先序遍历二叉树，root为二叉树的根结点
if (root != NULL)	//如果root不为空，则执行如下操作
{
visit (root);					//访问根结点
PreOrderTraverse (root -> lchild, Visit ());	//先序遍历左子树
PreOrderTraverse (root -> rchild, Visit ());	//先序遍历右子树
}
}

中序遍历

void InOrderTraverse (BTree root)
{//中序遍历二叉树，root为二叉树的根结点
if (root != NULL)		//如果root不为空，则执行如下操作
{
InOrderTraverse (root -> lchild, Visit ());	//中序遍历左子树
visit (root);					//访问根结点
InOrderTraverse (root -> rchild, Visit ());	//中序遍历右子树
} }

后序遍历

void PostOrderTraverse (BTree root)
{//后序遍历二叉树，root为二叉树的根结点
if (root != NULL)		//如果root不为空，则执行如下操作
{
PostOrderTraverse (root -> lchild, Visit ());	//后序遍历左子树
PostOrderTraverse (root -> rchild, Visit ());	//后序遍历右子树
visit (root); } 					//访问根结点
}

层次遍历

void LevelOrderTraverse (BTree root)
{Queue Q;			//声明队列Q
BTree p = root;			//p指向根结点
InitQueue (&Q);		//初始化队列
if (root)				//如果root不为空
	EnQueue (&Q, root);	//根结点进队
while (Q.front)			//队列不为空，执行循环
{DeQueue (&Q, &p);	//队头元素出队并赋予p
visit (p -> data);	//访问结点p
if (p -> lchild)		//如果结点有左孩子
	EnQueue (&Q, p -> lchild);	//左孩子进队
if (p -> rchild)				//如果结点有右孩子
	EnQueue (&Q, p -> rchild); } } 	//右孩子进队