一、什么是树

树是一个与之前学习的所有数据结构完全不一样的这么一种数据结构，树是⼀种⾮线性的数据结构，它是由 n（n>=0） 个有限节点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。

例如：

有以下两个特点：
（1）树的最顶上的节点是它的根节点，根节点没有前驱节点，前驱节点就是例如上图B节点，他的前驱节点就是A节点。
（2）除开根节点之外的节点，其中每⼀个集合⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

有以下三个性质：
（1）子树是不相交的。
（2）除了根结点外，每个结点有且仅有⼀个⽗结点。
（3）一颗有N个节点的树有N-1条边。

不满足上述性质的数据结构就不是树。

二、专用术语

下面是一颗树，用它来介绍其专用术语。

1、⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点； 如上图：A是B的⽗结点。
2、⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如上图：B是A的孩⼦结点。
3、结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0。
4、树的度：⼀棵树中，最⼤的结点的度称为树的度； 如上图：树的度为 6。
5、叶⼦结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I… 等结点为叶结点。
6、分⽀结点：度不为 0 的结点； 如上图： D、E、F、G… 等结点为分⽀结点。
7、兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)； 如上图： B、C 是兄弟结点。
8、结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推。
9、树的⾼度或深度：树中结点的最⼤层次； 如上图：树的⾼度为 4。
10、结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先。
11、路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q。
12、⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙。
13、森林：由 m（m>0） 棵互不相交的树的集合称为森林。

三、特殊的树

前言 - - - 树的表示形式

在将这一点之前，需要知道树的表示形式，树有很多的表示形式，相较于之前的那一些数据结构表示起来就比较复杂了，既要存储数据域，还要表示节点与节点之间的关系，常见的表示形式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。这里我们了解最简单的孩子兄弟表示法：

struct TreeNode
{
	struct Node* child;   // 左边开始的第⼀个孩子结点
	struct Node* brother; // 指向其右边的下⼀个兄弟结点
	int data; // 结点中的数据域
};

更加形象一点就如下面这颗树的表示形式：

上述这颗树的孩子兄弟表示形式：

尽管如此表示确实很简单也通俗易懂，但是对于树而言，我们无法确切知道每一层都有多少个节点，正因如此，树的表示是比较困难的，所以在树的基础上，我们对其加以限制，就有了下面讲的特殊的树：

二叉树

二叉树是一种有限制条件的树，其限制是：
（1）树中没有度超过2的节点。
（2）⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树。
例如：

不过尽管度这一点稍微限制了一下，但是就如上述二叉树的第三层而言，孩子节点并非连续存储，中间空了一个，当叶子节点很多时，中间空得更多，这样一来同样不好表示二叉树，所以在二叉树得基础上我们又加以限制，得到满二叉树和完全二叉树。

满二叉树

满二叉树就是除开叶子节点，其余节点的度均为2，并且每层节点数量达到最大。

例如：

并且每层节点个数都有规律，第一层2^0个，第二层2 ^1个，第三层2 ^2个，第四层2 ^3个，以此类推，第h层2 ^(h-1)个；将第一层到第h层的节点全部加起来就得到了所有节点的个数，这是一个等比数列求和，得出节点总数为：(2 ^h)-1个。

但是满二叉树是一个理想情况，在实际里，多半都是最后一层的节点没有存储满，所以就有下面的完全二叉树。

完全二叉树

完全二叉树才是普遍的一类二叉树，完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 h 的，有 n 个
结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种。

例如：

四、链式二叉树的实现

链式二叉树的实现即底层结构是链表，使用链表实现二叉树最大的特点就是基本上方法的实现都离不开函数递归，因为树这一结构本身就是递归定义的；有链式就有顺序存储，顺序存储二叉树有一个新的结构叫法叫堆，本篇文章已经写出，详情请回看《数据结构 - - -堆》这一篇博客。

4.1定义根节点结构体

我们本身是不能直接定义树的结构体，但是树是由一个一个节点组成，所以我们可以间接构造节点结构体，通过节点来生成一个二叉树。

节点中有三个属性，本身的数据域，以及指向左右子树的指针域。

// 定义根节点结构体
// 一个数据域，两个指针域
typedef char BTNodeType;           // BT =  BinaryTree
typedef struct BinaryTreeNode
{
	BTNodeType data;                      // 数据域
	struct BinaryTreeNode* left;          // 左指针域
	struct BinaryTreeNode* right;         // 右指针域
	
}BTNode;

4.2节点初始化

我们通过动态开辟给每个节点申请内存空间。

// 初始化
BTNode* init(char c)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	// 预防malloc申请失败
	if (node == NULL)
	{
		printf("Error: Memory allocation failed!\n");
		exit(1);
	}
	// malloc申请成功
	node->data = c;
	node->left = NULL;
	node->right = NULL;
	// 最终将此节点返回
	return node;
}

4.3手动构造二叉树

BTNode* Tree()
{
	BTNode* node1 = init('A');
	BTNode* node2 = init('B');
	BTNode* node3 = init('C');
	BTNode* node4 = init('D');
	BTNode* node5 = init('E');
	BTNode* node6 = init('F');
	BTNode* node7 = init('G');

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node3->right = node5;
	node4->left = node6;
	node5->left = node7;

	return node1;
}

构造得到的二叉树如下所示：

4.4前序遍历算法

二叉树的前序遍历顺序是根左右，二叉树中每一个节点相对于其左右子树都是根节点，所以这里遇见根节点直接打印其数据域的值，再去递归它的左子树，右子树，直至递归完毕。
后面的中序，后序遍历道理相同。

// 前序遍历 --- 根左右
void preOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	preOrder(root->left);
	preOrder(root->right);
}

4.5中序遍历算法

二叉树中序遍历顺序是左根右。

// 中序遍历 --- 左根右
void inOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	inOrder(root->left);
	printf("%c ", root->data);
	inOrder(root->right);
}

4.6后序遍历算法

二叉树后序遍历顺序是左右根。

// 后序遍历 --- 左右根
void postOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	postOrder(root->left);
	postOrder(root->right);
	printf("%c ", root->data);
}

4.7二叉树中节点的个数

二叉树中节点的个数 = 根节点个数（1个）+ 左子树节点个数 + 右子树节点个数

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

4.8二叉树中叶子节点的个数

二叉树中叶子节点的个数 = 左子树叶子节点个数 + 右子树叶子节点个数

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)   // 叶子节点必须左右孩子为空
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

4.8二叉树第K层节点的个数

二叉树第K层节点的个数 = 左子树第k层节点的个数 + 右子树第k层节点的个数
代码的层数次序是k至1，和正常中的1到k是一样的

int BinaryTreeLevelK_Size(BTNode* root,int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelK_Size(root->left, k - 1) + BinaryTreeLevelK_Size(root->right, k - 1);
}

4.9二叉树的深度/高度

二叉树的深度/高度 = 根节点高度（为1）+ max(左子树高度, 右子树高度)

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = BinaryTreeDepth(root->left);
	int right = BinaryTreeDepth(root->right);

	return 1 + (left > right ? left : right);
}

4.10二叉树查找指定的x节点

// 二叉树查找指定的x节点
BTNode* BinaryTreeNodeFind(BTNode* root, BTNodeType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)   // 找到了返回这个节点
	{
		return root;
	}
	
	// 左右子树依次递归找
	BTNode* leftFind = BinaryTreeNodeFind(root->left, x);   
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeNodeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;  // 没找到返回空
}

4.4~4.10所有的运行结果如下图所示：
最后一个代码查找的是值为H的节点：

// 查找x节点
if (BinaryTreeNodeFind(node, 'H'))
{
	printf("找到了！！");
}
else
{
	printf("没找到！！");
}

4.11二叉树的销毁

这里需要传入二级指针，需要形参的修改影响实参，并且销毁顺序必须是后序遍历的左右顺序，以保证左右孩子先于根节点销毁。

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	// 按照后序顺序销毁二叉树
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

总结：
链式实现二叉树的绝大多数算法代码中都运用了函数递归的思想，可见递归和树是密切相关的。