对于大量的输入数据，链表的线性访问太慢，不宜使用。所以就有了树这种数据结构。它的大部分操作的运行时间平均为O(logN)。

一些定义

树可以有几种定义。定义树的一种自然的方式是递归的方法。一棵树是一些节点的集合。这个集合可以是空集；若非空，则一棵树有称作根（root）的i节点r以及0个或多个非空的（子）树T1，T2，...，Tk组成，这些子树中每一棵被来自根r的一条有向的边（edge）所连接。

每一棵子树的根叫做根r的儿子（child），而r是每一棵子树的根的父亲（parant）。

从递归定义中我们发现，一棵树是N个节点和N-1条边的集合，其中的一个节点叫做根。存在N-1条边的结论是由下面的事实得出的，每条边都将某个节点连接到它的父亲，而除去根节点外每一个节点都有一个父亲。

没有儿子的节点称为树叶（leaf）。具有相同父亲的节点为兄弟（sibling）；用类似的方法可以定义祖父（grandparent）和孙子（grandchild）关系。

从节点n1到nk的路径（path）定义为节点n1，n2，...，nk的一个序列，使得对于1<=i<k，节点ni是ni+1的父亲。这个路径的长（length）为该路径上的边的条数，即k-1。从每一个节点到它自己有一条长为0的路径。注意，在一棵树中从根到每个节点恰好存在一条路径。

对任意节点ni，ni的深度（depth）为从根到ni的唯一路径的长。因此根的深度为0。ni的高（height）是从ni到一片树叶的最长路径的长。因此所有的树叶的高都是0。一棵树的高等于它的根的高。一棵树的深度等于它的最深的树叶的深度；该深度总是等于这棵树的高。

如果存在从n1到n2的一条路径，那么n1是n2的一位祖先（ancestor）而n2是n1的一个后裔（descendant）。如果n1!=n2，那么n1是n2的一位真祖先（proper ancestor）而n2是n1的一个真后裔（proper descendant）。

先序遍历：对节点的处理工作是在它的诸儿子节点被处理之前（pre）进行的。后序遍历：在一个节点处的工作是在它的诸儿子节点被计算后（post）进行的。树的实现二叉树

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

表达式数expression tree，表达式树的树叶是操作数（operand），比如常数或变量，而其他的节点为操作符（operator）。二叉查找树，使二叉树成为二叉查找树的性质是，对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字。这意味着，该树所有的元素可以用某种统一的方式排序。代码实现

#ifndef TREE_H#define TRRR_Htypedef int ElementType;struct TreeNode;typedef struct TreeNode *Position;typedef struct TreeNode *SearchTree;class tree{public:    void MakeEmpty(SearchTree t);    Position Find(ElementType X, SearchTree t);    Position FindMin(SearchTree t);    Position FindMax(SearchTree t);    SearchTree Insert(ElementType X, SearchTree t);    SearchTree Delete(ElementType X, SearchTree t);    ElementType Retrive(Position P);private:    SearchTree root;};#endif

#include  "tree.h"#include <iostream>struct TreeNode{    ElementType Element;    SearchTree Left;    SearchTree Right;};void tree::MakeEmpty(SearchTree t){    if(t != nullptr){        MakeEmpty(t->Left);        MakeEmpty(t->Right);        delete t;    }}Position tree::Find(ElementType X, SearchTree t){    if(t == nullptr){        return nullptr;    }    if(X < t->Element){        return Find(X, t->Left);    }    else if(X > t->Element){        return Find(X, t->Right);    }    else{        return t;    }}Position tree::FindMin(SearchTree t){    if(t == nullptr){        return nullptr;    }    else {        if(t->Left == nullptr){            return t;        }        else{            return FindMin(t->Left);        }    }}Position tree::FindMax(SearchTree t){    if(t != nullptr){        while (t->Right != nullptr){            t = t->Right;        }    }    return t;}SearchTree tree::Insert(ElementType X, SearchTree t){    if(t == nullptr){        t = new(std::nothrow) TreeNode;        if(t == nullptr){            std::cout << "out of space" << std::endl;            return nullptr;        }        else{            t->Element = X;            t->Left = t->Right = nullptr;        }    }    else{        if(X < t->Element){            t->Left = Insert(X, t->Left);        }        else{            if(X > t->Element){                t->Right = Insert(X, t->Right);            }        }    }    return t;}SearchTree tree::Delete(ElementType X, SearchTree t){    Position tmpCell;    if(t == nullptr){        std::cout << "Element not found" << std::endl;        return nullptr;    }    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 == nullptr){                    t = t->Right;                }                else if(t->Right == nullptr){                    t = t->Left;                }                delete(tmpCell);            }        }    }    return t;}ElementType tree::Retrive(Position P){    return P->Element;}

AVL树，AVL（Adelson-Velskii和Landis）树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持，而且它须保证数的深度是O(logN)。最简单的想法是要求左右子树具有相同的高度。由于平衡条件太苛刻，所以需要放宽条件。一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。（空树的高度定义为-1）。插入一个节点时，可能会破坏平衡，因此我们需要重新平衡这棵树。我们把必须重新平衡的节点叫做a。由于任意节点最多有两个儿子，因此高度不平衡时，a点的两颗子树的高度差2。这样可能出现下面4种情况。对a的左儿子的左子树进行一次插入。对a的左儿子的右子树进行一次插入。对a的右儿子的左子树进行一次插入。对a的右儿子的右子树进行一次插入。

我们把对树的重新调整的方法叫做旋转。上面4种情况分为两种情况。1和4是一种，2和3是一种。第一种通过对数的一次单旋转（single rotation）而完成调整。第二种情况通过稍微复杂些的双旋转（double rotation）来处理。

单旋转：

case1: 代表情形1，旋转前的图在左边，而旋转后的图在右边。

节点k2不满足AVL平衡特性，因为它的左子树比右子树深2层。为使树恢复平衡，我们把X上移一层，并把Z下移一层。注意，此时实际上超出了AVL特性的要求。为此，我们重新安排节点以形成一颗等价的树。抽象地形容就是：把树看成是柔软灵活的，抓住节点k1，闭上你的双眼，使劲摇动它，在重力作用下，k1就变成了新的根。二叉查找树的性质，在原树中k2>k1，于是在新树中k2变成了k1的右儿子，X和Z仍然是分别是k1的左儿子和k2的右儿子。子树Y包含原树中介于k1和k2之间的那些节点，可以将它放在新树中k2的左儿子的位置上。这样，所有对顺序的要求都得到满足。

case4: 代表情形4，指出单旋转如何使用。

case1

插入6破坏了AVL特性，而后进过单旋转有将特性恢复

case4

双旋转

上面描述的算法有一个问题，对于情形2和3上面的做法无效。问题在于子树Y太深，单旋转没有减低它的深度。

如上图所示，子树Y中已经有一项插入其中，这个事实保证它是非空的。因此我们可以假设它有一个根和两棵子树。于是，我们可以把整棵树看成是四棵子树由3个节点连接。如下图所以：

恰好树B或树C中有一棵树比D深两层，但是我们不能肯定是哪一棵。为了重新平衡，我们看到，不能再让k3作为根了，而在k3和k1时间的旋转又解决不了问题，唯一的选择是把k2用作新的根。迫使k1是k2的左儿子，k3是它的右儿子，从而完全确定了这四棵树的最终位置。

代码如下：

#ifndef AVLTREE_H#define AVLTREE_Htypedef int ElementType;struct AvlNode;typedef struct AvlNode *Position;typedef struct AvlNode *AvlTree;AvlTree MakeEmpty(AvlTree T);Position Find(ElementType X, AvlTree T);Position FindMin(AvlTree T);Position FindMax(AvlTree T);AvlTree Insert(ElementType X, AvlTree T);AvlTree Delete(ElementType X, AvlTree T);ElementType Retrieve(Position P);#endif

#include "avltree.h"#include <stdio.h>#include <stdlib.h>struct AvlNode{    ElementType Element;    AvlTree left;    AvlTree right;    int height;};AvlTree MakeEmpty(AvlTree T){    if(T != nullptr){        MakeEmpty(T->left);        MakeEmpty(T->right);        free(T);    }    return nullptr;}Position Find(ElementType X, AvlTree T){    if(T == nullptr){        return nullptr;    }    if(X < T->Element){        return Find(X, T->left);    }    else if(X > T->Element){        return Find(X, T->right);    }    else{        return T;    }}Position FindMin(AvlTree T){    if(T == nullptr){        return nullptr;    }    else if(T->left == nullptr){        return T;    }    else{        return FindMin(T->left);    }}Position FindMax(AvlTree T){    if(T != nullptr){        while(T->right != nullptr){            T = T->right;        }    }    return T;}static int Height(Position P){    if( P == nullptr){        return -1;    }    else{        return P->height;    }}static int Max(int Lhs, int Rhs){    return Lhs>Rhs?Lhs:Rhs;} /* This function can be called only if K2 has a left child */static Position SingleRotateWithLeft(Position K2){    Position K1;    K1 = K2->left;    K1->right = K2;    K2->height = Max(Height(K2->left), Height(K2->right)) + 1;    K1->height = Max(Height(K1->left), K2->height) + 1;    return K1;}/* This function can be called only if K1 has a right child */static Position SingleRotateWithRight(Position K1){    Position K2;    K2 = K1->right;    K1->right = K2->left;    K2->left = K1;    K1->height = Max(Height(K1->left), Height(K1->right)) + 1;    K2->height = Max(Height(K2->right), K1->height) + 1;    return K2;}static Position DoubleRotateWithLeft(Position K3){    K3->left = SingleRotateWithRight(K3->left);    return SingleRotateWithLeft(K3);}static Position DoubleRotateWithRight(Position K1){    K1->right = SingleRotateWithLeft(K1->right);    return SingleRotateWithRight(K1);}AvlTree Insert(ElementType X, AvlTree T){    if(T == nullptr){        T = (AvlTree)malloc(sizeof(struct AvlNode));        if(T == NULL){            printf("out of space\n");            return nullptr;        }        else{            T->Element = X; T->height = 0;            T->left = T->right = nullptr;        }    }    else if(X < T->Element){        T->left = Insert(X, T->left);        if(Height(T->left) - Height(T->right) == 2){            if(X< T->left->Element){                T = SingleRotateWithLeft(T);            }            else{                T = DoubleRotateWithLeft(T);            }        }    }    else if(X > T->Element){        T->right = Insert(X, T->right);        if (Height(T->left)-Height(T->left) == 2){            if(X > T->right->Element){                T = SingleRotateWithRight(T);            }            else            {                T = DoubleRotateWithRight(T);            }        }     }    T->height = Max(Height(T->left), Height(T->right)) + 1;           return T;}AvlTree Delete(ElementType X, AvlTree T){    // To do;}ElementType Retrieve(Position P){    return P->Element;}