本篇主要讲树最基本的知识。
预备知识
一棵树由称做根root的节点r以及0个或者多个非空的(子)树T1，T1，...，Tk组成，这些子树中每一个棵的根都被来自根r的一条有向的边edge链接。
-
儿子、父亲：
每一棵子树的根节点叫做根r的儿子child，而r是每一棵子树根的父亲parent。例如A是E的父亲，E是A的儿子。 -
树叶：
每一个子树也可以有自己的儿子，而没有儿子的子树叫做树叶leaf。例如B、C、P -
兄弟、祖父、孙子
具有相同父亲的节点为兄弟，类似的还有孙子和祖父。例如D、E为兄弟，A是J的祖父、J是A的孙子。 -
深度、高
从根到该节点唯一路径的长。比如根的深度为0。
从该节点到一片树叶的最长路径的长。比如所有的树叶高都是0，一棵树的高等于它根的高。
例如：E的深度为1，而高为2。F的深度是1，而高也是1。
image.png
树的实现
由于每个节点儿子数可以变化很大，并且事先不知道，因此在数据结构中建立到各个儿子节点直接的链接是不可行的，因为这样会浪费太多的空间。（这是书上的说法，我觉得估一个大概的数量，直接把儿子数组的宽度写死也是可以的）
这里的解法是：将每个节点的所有儿子都放在树节点的链表中。
一种典型的声明：
typedef struct TreeNode * PtrToNode;
struct TreeNode
{
ElementType Element;
PtrToNode FirstClild;
PtrToNode NextSibling;
}
在下图的表示方式中，向下的紫色箭头是指向FirstChild（第一个儿子）的指针。从左到右的箭头是指向NextSibling（下一个兄弟）的指针。这里并没有画空指针。
image.png
树的遍历及应用
最流行的用法之一就是操作系统中的目录结构。如下图，有*号的表示一个目录。
image.png
假设我们想要列出目录中所有文件的名字。我们的输出格式将是：深度
di 的文件的名字将被 di 次跳格(tab)缩进后打印出来。
算法如下：
static void ListDir( DirectoryOrFile D, int Depth )
{
if( D is a legitimate entry) //合法入口
{
PrintName(D, Depth);
if( D is a directory )
for each child, C, of D
ListDir( C, Depth + 1 );
}
}
void ListDirectory( DirectoryOfFile D )
{
ListDir( D, 0 );
}
算法的核心为递归过程ListDir。为了显示根时不进行缩进，该例程需要从目录名和深度0开始。
image.png
