极客教程树是很有用的数据结构，它的名字源于元素之间的关系。通常，子节点连接到父节点，从整体上看就像一颗倒过来的树，根节点表示这种数据结构的开始元素。
树可以有任意数量的子节点，不过，二叉树比较常见，它的每个节点能有0个、1个或是2个子节点。子节点要么是左子节点，要么是右子节点。没有子节点的节点称为叶子节点，就跟树叶一样。本节中的示例会阐明二叉树。
指针提供了一种维护三个节点之间关系的直观、动态的方式。我们可以动态分配节点，将其按需插入树中。这里使用下面的结构体作为节点，借助void指针可以处理我们需要的任意类型的数据：
按照特定顺序向树中插入节点是有意义的，这样可以让很多操作（比如搜索）变得容易。下面的顺序很常见：插入新节点后，这个节点的所有左子节点的值都比父节点小，所有右子节点的值都比父节点的值大，这样的树称为二叉查找树。
下面这个insertNode函数会把一个节点插入二叉查找树，不过，要插入节点，首先需要在新节点和已有节点之间做比较。我们用COMPARE函数指针来传递比较函数的地址，函数的第一部分为新节点分配内存并把数据赋给节点。因为新节点插入树后总是叶子节点，所以将左子节点和右子节点置为NULL：
首先，检查根节点来判断树是否为空。如果为空，那么就把新节点赋给根节点，函数返回。根节点是以TreeNode指针的指针的形式传递的，这是必要的，因为我们需要修改传入函数的指针，而不是指针指向的对象。
如果树非空，程序就进入一个无限循环，直到将新节点插入树中结束。每次循环迭代都会比较新节点和当前节点，根据比较结果，将局部root指针置为左子节点或者右子节点，这个root指针总是指向树的当前节点。如果左子节点或右子节点为空，那么就将新节点添加为当前节点的子节点，循环结束。
为了说明insertNode函数，我们会重用6.4节中创建的雇员实例。下面的代码片段初始化一个空的TreeNode，然后插入三个雇员结构体，程序栈的结果和堆的状态如下图所示。为了简化这个图，我们省略了某些指向雇员结构体的线，并调整了节点在堆中的位置，以反映树结构的顺序：
下说明了这棵树的逻辑结构。
二叉树可以满足多种需求，遍历二叉树的方式有三种：前序、中序和后序。三种技术步骤相同，但顺序不同。三个步骤如下：
- 访问节点
处理节点 - 往左
转移到左子节点 - 往右
转移到右子节点
对我们来说，访问节点的目的是打印其内容。访问节点的三种顺序如下所示。
- 中序
先往左，访问节点，再往右。 - 前序
访问节点，往左，再往右。 - 后序
先往左，再往右，最后访问节点。
函数的实现如下，所有的函数的参数都是树根和作为打印函数的一个函数指针，它们都是递归的。只要传入的根节点非空就会调用自身，不同点只在于执行三步操作的顺序：
下面的代码片段调用这些函数：
下表显示的是基于前面初始化的树每次函数调用的输出。
| 前序 | Samuel 32 Sally 28 Susan 45 |
|---|---|
| 中序 | Sally 28 Samuel 32 Susan 45 |
| 后序 | Sally 28 Susan 45 Samuel 32 |
中序遍历会返回树成员的排序列表，前序和后序遍历跟栈和队列配合使用可以计算算术表达式。