预备知识

树可以用几种方式定义。

定义树的一种自然的方式是递归的方法。

一棵树是一些节点的集合。

这个集合可以是空集；若非空，则一棵树由称作根的节点r以及0个或多个非空的(子)树组成，这些子树中每一棵的根都被来自根r的一条有向边所连接。

每一颗子树的根叫做根r的儿子，而r是每一棵子树的根的父亲。

从递归的定义中可以看出，一棵树是N个节点和N-1条边的集合，其中的一个节点叫做根。

没有儿子的节点称为树叶。

具有相同父亲的节点称为兄弟。

每个节点到它自己有一条长为0的路径。
从一棵树中从根到每个节点恰好存在一条路径。

对任意节点n_i,n_i的深度(depth)为从根到n_i的唯一路径的长。
因此，根的深度为0。

n_i的高(height)是从n_i到一片树叶的最长路径的长。 因此所有的树叶的高都是0. 一棵树的高等于它的根的高。

一个树的深度等于它的最深的树叶的深度；
该深度总是等于这棵树的高。

如果存在从n_i到n_k的一条路径，那么n_i是n_k的一位祖先而n_k是n_i的一个后裔。
如果n_i≠n_k，那么n_i是n_k的一位真祖先而n_k是n_i的一个真后裔。

树的实现

因为每个节点的儿子数可以变化很大并且实现不知道，所以将每个节点的所有儿子都放在树节点的链表中。

typedef struct TreeNode *PtrToNode;

struct TreeNode
{
    ElementType Element;
    PtrToNode   FirstChild;
    PtrToNode   NextSibling;
}

树的遍历及应用

树有很多应用。流行的用法之一是包含许多常用操作系统中的目录结构。

先序遍历

在对节点的处理工作是在他的诸多儿子节点被处理之前进行的。

后序遍历

在一个节点处的工作是在他的诸多儿子节点被计算后进行的。

二叉树

二叉树是一棵树，其中每个节点都不能有多于两个的儿子。

二叉树的一个性质是平均二叉树的深度要比N小得多。

实现

树节点的声明在结构上类似与双链表的声明，一个节点就是由key信息加上两个指向其他节点的指针(Left和Right)组成的结构。

应用于联表上的许多法则也可以应用到树上。

typedef struct TreeNode *PtrToNode;
typedef struct PtrToNode Tree;

struct TreeNode
{
    ElementType Element;
    Tree        Left;
    Tree        Right;
}

二叉树的主要用处之一是在编译器的设计领域。

表达式树

表达式树的树叶是操作数，比如常数或变量，而其他的节点为操作符。

我们可以将通过递归计算左子树和右子树所得到的值应用在根处的算符操作中而算出表达树T的值。这种一般的方法(左，节点，右)称为中序遍历。

如果我们另一个遍历策略是先打印出左子树、右子树、然后打印运算符。那么这是称为后序遍历。

再就是我们先打印出运算符，然后我们递归的打印出左子树和右子树。这种遍历策略称为先序遍历。

查找树ADT-二叉查找树

二叉树的一个重要应用是它们在查找中的使用。

使二叉树成为二叉查找树的性质是，对于树中每个节点X，它的左子树中所有关键字值小于X的关键字值，而他的右子树中所有关键字值大于X的关键字值。

二叉查找树的平均深度是O(logN)，所以我们一般不同担心栈空间被用尽。

MakeEmpty

这个操作主要用于初始化。

SearchTree MakeEmpty(SearchTree T)
{
    if(T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Find

这个操作一般需要返回指向树T中具有关键字X的节点的指针，如果这样的节点不存在则返回NULL。

注意测试的顺序。
关键的问题是我们首先要对是否为空树进行测试，否则就可能在NULL指针上兜圈子。其余的测试应该使得最不可能的情况安排在最后进行。

Position Find(ElementType x, SearchTree T)
{
    if(T == NULL)
        return NULL;
    if(X < T->Element)
        return Find(X, T->Left);
    else if(X > T->Element)
        return Find(X, T->Right);
    else
        return T;
}

FindMin FindMax

返回树中最小元和最大元的位置。
执行FindMin，从根开始并且只要有左儿子就向左执行。终止点是最小的元素。
FindMax类似，不再赘述。

Position FindMin(SearchTree T)
{
    if(T == NULL)
        return NULL
    else if(T->Left == NULL)
        return T;
    else
        return FindMin(T->Left);

Position FindMax(SearchTree T)
{
    if (T!=NULL)
        while(T->Right != NULL)
            T = T->Right;
    return T;

注意语句对程序的改变，如T->Right = T->Right->Right 这样的语句将会产生一些变化。

Insert

为了将X插入到树T中，你可以像用Find那样沿着树查找。如果找到X，则什么也不用做(或做一些更新)。否则将X插入到遍历的路径上的最后一点上。

重复元的插入可以通过在节点记录中保留一个附加域以指示发生的频率来处理。
如果关键字只是一个更大结构的一部分，那么这种方法行不通，此时我们可以把具有相同关键字的所有结构保留在一个辅助数据结构中，如表或是另一棵查找树中。

SearchTree Insert(ElementType X, SearchTree T)
{
    if(T == NULL)
    {
        /* create and return a one-node tree*/
        T = malloc(sizeof(struct TreeNode));
        if(T==NULL)
            FatalError("Out of space!!");
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    }
    else if (X < T->Element)
        T->Left = Insert(X, T->Left);
    else if( X > T->Element )
        T->Right = Insert(X, T->Right);
    /*Else X is in the tree already;we'll do nothing*/
    return T;

Delete

一旦发现要被删除的节点，我们就需要考虑几种可能的情况。
如果节点是一片树叶，那么它可以被立即删除。
如果节点有一个儿子，则该节点可以在其父节点调整指针绕过该节点后被删除。
注意，所删除的节点现在已不可再引用，而该节点只有在指向它的指针已被省去的情况下才能够去掉。

复杂的情况是处理具有两个儿子的节点。
一般的删除策略是用其右子树的最小的数据代替该节点的数据并递归的删除那个节点。因为右子树中的最小的节点不可能有左儿子，所以第二次删除要容易。

如果删除的次数不多，则通常使用的策略是懒惰删除：当一个元素要被删除时，它仍留在树中，而是只做了个被删除的记号。再有如果被删除的关键字是重新插入的，那么分配一个新单元的开销就避免了。

SearchTree Delete(ElementType X, SearchTree T)
{
    Position TmpCell;
    if (T == NULL)
        Error("Element not found");
    else if(X < T->Element)
        T->Left = Delete(X, T->Left);
    else if(X > T->Element)
        T->Right = Delete(X, T->Right);
    else if(T->Left && T->Right)
    {   
        TmpCell = FindMin(T->Right);
        T->Element = TmpCell->Element;
        T->Right = Delete(T->Element, T->Right);
    }
    else
    {
        TmpCell = T;
        if(T->Left == NULL)
            T = T->Right;
        else if(T->Right == NULL)
            T = T->Left;
        free(TmpCell);
    }
    return T;
}