通过树可以用来描述层级结构数据，基本上有序列的地方就可以应用树，因为树结构即是一种序列索引结构。

这里简单介绍常见的树结构。

简介 #

Tree 通常可以用来描述层次结构，在一些回溯算法中也有应用。

如上的树，一般会通过指针维护各个节点之间的上下级关系，包括了节点 (Node/Vertex) 以及边 (Edge)，常用的概念如下。

• Degree 度，也就是一个 Node 的子树的个数，例如 A 为 2 。
• Root 根节点，其父节点为 NULL ，如上图中的 A 节点。
• Leaf 叶子节点，没有子节点或者子树的节点，例如 H、I、J、K、L、M、N、O 节点。
• Siblings 兄弟节点，拥有相同的父节点，例如 B、C 节点。
• Level 层级，通常是从根节点开始计算，例如 A 为 1 。
• Depth 深度，从根节点到该节点的最长简单路径的边数，例如 B 为 1，F 为 2 。
• Height 高度，从该节点到叶子节点的最长简单路径的边数，例如 B 为 2，F 为 1 。

另外，将最深的叶子节点深度作为树的深度，根的高度就是树的高度，也就是说，树的高度和深度是相同的，通常使用的是高度。

二叉树 Binary Tree #

二叉树每个节点最多只有两个分支的树结构，对应的节点通常被称为 “左子树” 和 “右子树” ，两者的顺序不能颠倒，如上就是一个二叉树。

特殊二叉树 #

有两类特殊的二叉树。

满二叉树 (Full Binary Tree) #

也称 Perfect Binary Tree，满足 A) 所有内部节点都有两个子节点；B) 所有叶子节点 level 相同。

这样，当节点的层数为 n 时，总共有 2^n - 1 个节点。

完全二叉树 (Complete Binary Tree) #

对于 n 层的二叉树，除了第 n 层外，其它层的节点数都达到了最大，而且第 n 层的叶子节点从左到右排布。

区别 #

如下的树是满但非完全二叉树，满足满树的概念，但是不满足完全二叉树的概念，当增加了虚拟节点后，就是完全二叉树了。

如下则是完全但非满二叉树。

遍历方式 #

对于二叉树可以通过递归的方式进行访问，递归时的嵌套深度一般为树的高度。

所谓的顺序，其实就是在访问时，当前节点所处的位置，例如前序 V 在最开始，顺序 V 在中间，后序 V 在最后，在实现时可以使用递归 (Recursive) 或者迭代 (Iterative) 实现。

以如上的树为例。

Pre-Order #

递归实现的 C 代码如下。

void PreOrder(struct TreeNode *curr)
{
	if (curr == NULL)
		return;
	printf("%d", curr->value);  // V
	PreOrder(curr->left);       // L
	PreOrder(curr->right);      // R
}

也就是 Root->Left->Right ，那么上述的顺序就是 1 2 4 5 7 8 3 6 。

In-Order #

递归实现的 C 代码如下。

void InOrder(struct TreeNode *curr)
{
	if (curr == NULL)
		return;
	InOrder(curr->left);        // L
	printf("%d", curr->value);  // V
	InOrder(curr->right);       // R
}

也就是 Left->Root->Right，那么上述的顺序就是 4 2 7 5 8 1 3 6 。

Post-Order #

递归实现的 C 代码如下。

void PostOrder(struct TreeNode *curr)
{
	if (curr == NULL)
		return;
	PostOrder(curr->left);      // L
	PostOrder(curr->right);     // R
	printf("%d", curr->value);  // V
}

也就是 Left->Right->Root，那么上述的顺序就是 4 7 8 5 2 6 3 1 。

Level-Order #

水平遍历就是每层以此由左到右遍历，那么上述就是 1 2 3 4 5 6 7 8，这与广度优先搜索相同 。