数据结构：树、二叉树

一：树的定义：

树（tree）是n个节点的有限集；n = 0;称为空树；

在任意非空树中：

1、有且仅有一个特定的根节点；

2、当n>1时其余结点可分为m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，并且称为根的子树。

 

 

树的定义强调两点：

1、n>0时，根节点唯一

2、m>0时，子树的个数没有限制，但他们一定互不相交

下图就不符合树的定义：

二、结点的分类：

    树的结点包含一个数据元素以及若干指向其子树的分支；

1、结点的度(Degree)：一个结点所拥有的子树数；度为0的结点称为叶子节点或终端结点，度不为0的结点称为非终端结点或分支节点。除根节点外，分支结点也成为内部结点，

2、树的度：树内结点的最大值；

三：结点之间的关系

四、树的其他概念：

                 结点的层次（level）：从根开始定义，根为第一层，根的孩子为第二层，若某结点在第N层，则其子树的根在N+1层，

               树的深度（Depth）：树中结点的最大层次

有序树与无序树：如果将树中各子树看成从左至右是有次序的，不能互换，则称为有序树，否则称为无序树

森林（forest）：M（M>0）颗互不相交的树 的合集

五、线性结构与树结构：

        线性结构：第一个元素无前驱，最后一个元素无后继，中间元素，前驱后继。

        树结构：根节点无双亲；叶子节点无孩子，可以多个，中间节点，一个双亲多个孩子

 

六、二叉树（binary Tree）是n个节点的有限集合，该集合或为空集（空二叉树），或由一个根节点和两棵互不相交的、分别称为根节点的左子树、右子树的二叉树构成。

七：二叉树的特点：

                1、每个节点最多只有两个子树（一个结点可以有一个子树或者没有），二叉树中不存在度大于2的节点；

                 2、左子树与右子树是有顺序的，次序不能颠倒；

                 3、即使某个节点只有一颗子树，也要区分左子树、右子树

                 4、二叉树的五个状态：空二叉树、只有一个根节点、只有左子树、只有右子树、根节点左子树右子树都有。

八 ：特殊的二叉树

1、斜树：左斜树、右斜树

2、满二叉树：所有分支结点都存在左子树与右子树，且叶子节点在同一层；

满二叉树的特点：

【1】叶子只在最下层，

【2】非叶子结点的度只能是2；

【3】在同深度的二叉树中，满二叉树的叶子节点最多，叶子树最多。

九：完全二叉树：对于具有n个节点的二叉树按层序编号，如果编号为i的节点与同样深度的满二叉树中编号为i的结点的位置相同，则成为完全二叉树。

满二叉树 一定是完全二叉树，完全二叉树不一定的满二叉树

 

九：二叉树的性质：

性质1、在二叉树的第i层至多有2^（i-1）（i>1）个节点

性质2、深度为K的二叉树至多有2^K-1个节点（所有节点加起来）

性质3、对于任意一颗二叉树T，如果其叶子（终端）结点N0，度为2的结点数为N2，则N0 = N2+1;

性质4、具有n个结点 的完全二叉树的深度为【log2 n】+1

十、二叉树的遍历方法

1、前序遍历

              若二叉树为空，则返回；否则先访问根节点，然后前序遍历左子树，再前序遍历右子树

2、中序遍历

          若树为空，则空操作返回；否则中序遍历左子树，访问根节点，最后中序遍历右子树

3、后序遍历

若树为空，则空操作返回，否则先访问左子树，在访问右子树，最后访问根节点

4、层序遍历

若树为空，则返回空操作，否则从树的第一层开始，根节点访问，从上而下逐层遍历，同层中，按从左到右遍历，

 

十一、二叉树的存储结构

（1）顺序存储结构： 
顺序存储结构其实就是在一个连续存储单元里，从根结点开始，像对完全二叉树编号的顺序一样，把我们的二叉树的内容存储在一个一维数组中，一般顺序存储结构是拿来存储完全二叉树的，但是也可以拿来存储一般的二叉树，只是要按照完全二叉树的规则来编号，如果没有的就存0，如下图所示： 

（2）链式存储结构（比较常用一种存储结构）

由二叉树的定义可知道，我们链式存储结构至少包含三个部分：数据域和两个指针域，一个指向左孩子，另一个指向右孩子，我们称这种链表为二叉链表，另外一种就是我们还可以添加一个指针域，指向其父亲结点，我们称为三叉链表，如下图所示： 

十二、二叉树的生成

#include<iostream>
#include<stack>
using namespace std;

//结点的结构
struct Tree_Node
{
    //每个结点的数据
    char data;
    //左子树
    Tree_Node * left;
    //右孩子
    Tree_Node * right;
};


//按照先序遍历的方式，构建我们的二叉树,输入的时候，我们要按照完全二叉树的形式输入，结点为空的位置，输入“#”
void createTree(Tree_Node * & t)
{
    char str;
    cin>>str;
    if(str=='#')
    {
        t=NULL;
    }
    else
    {
        t=new Tree_Node; //为t开辟空间
        t->data=str;
        createTree(t->left);
        createTree(t->right);
    }
}

//先序遍历，递归实现
void PreorderTraverse(Tree_Node * T)
{
    if(T){
        if(T->data!='#')
       cout<<T->data<<" ";   //访问根结点
       PreorderTraverse(T->left);  //访问左子树
       PreorderTraverse(T->right);  //访问右子树
    }
}

//非递归实现,思路：
//首先我们的循环条件是：结点不为空或者栈不为空。然后是先把根结点加入桟中，然后，遍历左子树，当左子树遍历完后，栈顶元素为刚刚的根结点，然后，让根结点出栈，遍历右子树
void PreorderTraverse_no_recursive(Tree_Node * T)   
{
    stack<Tree_Node*> s;
    Tree_Node * p=T;
        //栈不为空或者T不为空时，循环继续
    while(p || !s.empty())
    {
        if(p!=NULL)  
        {
            s.push(p); //根结点入栈
            if(p->data!='#')//访问根结点
            cout<<p->data<<' ';
            p=p->left; //先遍历左子树
        }
        else
        {
            p=s.top(); //根结点出栈
            s.pop();   //
            p=p->right;//遍历右子树
        }
    }
}

//递归实现中序遍历
void InorderTraverse(Tree_Node * T)
{
    if(T)
    {
        InorderTraverse(T->left); //中序遍历左孩子     
        if(T->data!='#')
        cout<<T->data<<" ";       //访问根结点
        InorderTraverse(T->right); //中序遍历右孩子
    }
}

//非递归实现中序遍历，思路：
//思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 
//先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 
void InorderTraverse_recursive(Tree_Node * T)
{
    stack<Tree_Node*> s;
    Tree_Node * p=T;
        //栈不为空或者T不为空时，循环继续
    while(p || !s.empty())
    {
        if(p!=NULL)  
        {
            s.push(p); //根结点入栈
            p=p->left; //先遍历左子树
        }
        else
        {
            p=s.top(); //根结点出栈
            s.pop();   //
            if(p->data!='#')//访问根结点
            cout<<p->data<<' ';
            p=p->right;//遍历右子树
        }
    }
}       


//递归实现后序遍历
void PostorderTraverse(Tree_Node * T)
{
    if(T)
    {
        PostorderTraverse(T->left); //访问左子树
        PostorderTraverse(T->right); //访问右子树
        if(T->data!='#')
        cout<<T->data<<" "; //访问根结点
    }
}

//非递归实现后序遍历
//思路：我们要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；
//或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，
//则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。 
void PostorderTraverse_recursive(Tree_Node * T)
{
    Tree_Node * pre; //前一个被访问的结点。
    pre=NULL;
    stack<Tree_Node*> s;
    Tree_Node * cur;  //记录栈顶的结点，
    s.push(T); //先把根结点入栈
    while(!s.empty())
    {
        cur=s.top(); //cur记录的是栈顶的结点
        if((cur->left==NULL && cur->right==NULL) || (pre!=NULL && (pre==cur->left || pre==cur->right)))
        {
            cout<<cur->data<<" "; //满足：不存在左孩子和右孩子；或者存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了
            s.pop();
            pre=cur; //更新pre的值
        }
        else
        {
            if(cur->right!=NULL) //一定是右子树先入栈的，因为这样才可以比左子树后被访问
            s.push(cur->right);
            if(cur->left!=NULL) //左子树入栈
            s.push(cur->left);   
        }
    }
}

int main()
{
    Tree_Node * T;
    createTree(T);
    cout<<"先序遍历--递归实现"<<endl;
    PreorderTraverse(T);
    cout<<endl;
    cout<<"先序遍历--非递归实现"<<endl;
    PreorderTraverse_no_recursive(T);
    cout<<endl;
    cout<<"中序遍历--递归实现"<<endl;
    InorderTraverse(T);
    cout<<endl;
    cout<<"中序遍历--非递归实现"<<endl;
    InorderTraverse_recursive(T);
    cout<<endl;
    cout<<"后序遍历--递归实现"<<endl;
    PostorderTraverse(T);
    cout<<endl;
    cout<<"后序遍历--非递归实现"<<endl;
    PostorderTraverse_recursive(T);
    cout<<endl;
    return 0;

}

 

 

十三、线索二叉树

在之前采用非递归方式进行二叉树的遍历的时候，我们需要声明一个栈来保存我们之后需要访问的结点等信息，然后，我们现在就想通过另外一种方式来代替我们的栈，它就是线索二叉树， 
所谓的线索二叉树就是：即按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列。在该序列中，除第一个结点（某种遍历方式访问的第一个结点）外每个结点有且仅有一个直接前驱结点；除最后一个结点（某种遍历方式访问的最后一个结点）外每一个结点有且仅有一个直接后继结点。这些指向直接前驱结点和指向直接后续结点的指针被称为线索（Thread），加了线索的二叉树称为线索二叉树。

OK，其实线索二叉树用一句话解释就是：我的每个结点都保存了该结点前一个访问的结点和后一个需要访问的结点。那么，我们要怎么记录那些信息了？最简单的方法就是为每个结点结构添加多两个结点域：pre和after，分别保存它的前驱和后继，但是这样必然会让结点的结构的存储密度减低。 
好了，现在有人发现其实我们在之前声明的结构中无论怎么样都会出现一大堆的空链域（指针的值为NULL），因为当我们有n个结点的时候，那么根据之前定义的结构，必有2*n个指针域（left和right）,但是，除了根结点外，其他的每个结点都只有一个父亲结点（一个指针域指向它的意思），所以我们就只使用了(n-1)个指针域，最后一定还会有n+1个指针域为空的，那么其实我们就可以利用这些指针域来记录每个结点的前驱和后继。 

其中我们规定所有空的right都指向结点的后继：

所有空的left都指向结点的前驱：

所以我们提出一个线索链表的结构，如下图所示： 

因为，我们要记录当前的左孩子或者右孩子是否为空，所以需要在结构中添加多两个变量：ltag和rtag，只要左孩子或右孩子存在，就把对应的标志设置为0，否则设置为1.

下面，我们就以中序遍历为基础，建立中序线索二叉树，并且根据中序线索二叉树进行中序遍历。

另外，我们还打算引进一个头指针，这个头指针的lchild域指向根结点，rchild域指向中序遍历的最后一个结点，其中，中序遍历的最后一个结点和第一个结点都指向头结点，这样设置的好处是，我们可以顺前驱进行中序遍历，也可以顺后继往前进行遍历。

具体的代码实现：

#include<iostream>
using namespace std;

//结点的结构
struct Tree_Node
{
    //每个结点的数据
    char data;
    //左子树
    Tree_Node * left;
    //左标志
    int ltag;
    //右孩子
    Tree_Node * right;
    //右标志
    int rtag;
};

//按照先序遍历的方式，构建我们的二叉树,输入的时候，我们要按照完全二叉树的形式输入，结点为空的位置，输入“#”
void createTree(Tree_Node * & t)
{
    char str;
    cin >> str;
    if (str == '#')
    {
        t = NULL;
    }
    else
    {
        t = new Tree_Node; //为t开辟空间
        t->data = str;
        createTree(t->left);
        createTree(t->right);
    }
}

////对刚才创建的二叉树进行中序的线索化，其实就是为ltag和rtag赋值，并且也为那些空指针域赋值
Tree_Node  * pre;     /* 全局变量，始终指向刚刚访问过的结点 */
void InThreading(Tree_Node * p)
{

    if (p)
    {
        InThreading(p->left); //左子树的线索化
        p->ltag = 0; //假设p的左右孩子都不为空
        p->rtag = 0;
        if (!p->left) 
        { 
            p->ltag = 1; 
            p->left = pre;
        }  //如果当前的结点没有左孩子，那么就让我们的左孩子指向pre，
        if (!pre->right) 
        { 
            pre->rtag = 1;
            pre->right = p;
        } //因为pre时p的前驱，那么p就是pre的后继，如果pre的右孩子不为空的话，那么我们就让它的指向p
        pre = p;       //更新pre的值，因为等下就要进行右子树的线索化了
        InThreading(p->right);  //右子树的线索化
    }
}

//同样时线索化的函数，这里主要时处理让头结点的左指针域指向根结点和最后一个结点的右孩子的指针域指向头结点
void InorderThreading(Tree_Node * & T, Tree_Node * & Thead)
{

    Thead = new Tree_Node;  //建立一个头结点
    Thead->ltag = 0;
    Thead->rtag = 1;
    Thead->right = Thead;    //右指针域回指自己，等找到了最后一个结点后，再修改
    if (!T) //当二叉树为空的时候
    {
        Thead->left = Thead;
        return;
    }

    Thead->left = T;  //头结点的左指针指向根结点
    pre = Thead;      //让头结点为pre
    InThreading(T);  /* 中序遍历进行中序线索化，pre指向中序遍历的最后一个结点 */
    pre->right = Thead; /* 最后一个结点的右指针指向头结点 */
    pre->rtag = 1; /* 最后一个结点的右标志为线索 */
    Thead->right = pre; /* 头结点的右指针指向中序遍历的最后一个结点 */
}

void InorderThreading_recurcise(Tree_Node * Thead)
{
    Tree_Node * p = Thead->left; /* p指向根结点 */
    while (p != Thead) /* 空树或遍历结束时，p==T */
    {
        while (p->ltag == 0) /* 由根结点一直找到二叉树的最左结点 */
            p = p->left;

        if (p->data != '#')  /* 访问此结点 */
            cout << p->data << " ";

        while (p->rtag == 1 && p->right != Thead)  /* p->rchild是线索(后继)，且不是遍历的最后一个结点 */
        {
            p = p->right;
            if (p->data != '#')
                cout << p->data << " ";
        }
        p = p->right;   /* 若p->rchild不是线索(是右孩子)，p指向右孩子，返回循环，*/
    }
}


int main()
{
    Tree_Node * T;
    createTree(T);
    Tree_Node * Thead;
    //线索化
    InorderThreading(T, Thead);
    cout << "中序遍历--非递归实现" << endl;
    InorderThreading_recurcise(Thead);
    cout << endl;

    return 0;
}

十四、最优二叉树（哈夫曼树）

（1）叶子结点的路径长度：从根结点到该叶子结点所经过的边的条数 
（2）树的带权路径长度：为树的所有的叶子结点的路径长度乘以该叶子结点之和。通常记作：WPL，具体可以见下图： 

然后，当我们给定每个叶子结点的权值，我们去构造不同的二叉树，当该二叉树的WPL值最小时，我们称该二叉树为最优二叉树或哈夫曼树

那么，我们该如何构造这个最优的二叉树了？哈夫曼最早提出了一个算法用于构造哈夫曼树，我们称之为哈夫曼算法，算法描述如下： 

下面，我们就拿一个具体的例子来说明如上的算法： 

根据刚才的算法描述，我们可以写出

首先是我们要定义每个结点的结构：

struct Tree_Node
{
    char data; //数值 
    int weight; //权重 
    int parent; //父亲结点的下标 
    int left; //左孩子下标 
    int right; //右孩子下标 
};

然后，需要一个函数选出权重最小的两个结点的下标

//在前i-1个结点中，找出最小的两个结点
void select_two_min(Tree_Node * tree,int i, int s1, int s2)
{
    int j = 0;
    int min = INT_MAX;
    int min2 = INT_MAX;
    for (j = 0; j <= i; j++)
    {
        //先找出s1
        if (tree[i].parent == 0 && tree[i].weight < min)
        {
            //更新m2的值为之前的m1，因为m1是之前最小的，现在变第二小了
            min2 = min; 
            //更新min
            min = tree[i].weight;
            //s2也是同样的道理，所以要更新
            s2 = s1;
            //s1也一样
            s1 = i;

        }//
        //如果还有比min2小，但是比min大的，那么只要更新min2和s2
        else if (tree[i].parent == 0 && tree[i].weight < min2) {
            min2 = tree[i].weight;
            s2 = i;
        }
    }

}

最后，就是构造Huffman树的代码：

void Build_Huffman_Tree(Tree_Node * & tree, int * weight, int n, char * data)
{
    if (n <= 1) return; //如果叶子结点只有一个，那么就可以直接返回了 
    int m = 2 * n - 1;
    //开辟2*n-1个空间，用于存放各个结点的信息，
    //因为我们知道如果有n个结点，除了根结点，我们最多需要记录的结点信息为：2*n-1个。 
    tree = new Tree_Node[m];
    int i = 0;
    Tree_Node * p = tree;
    for (i = 0; i < n; ++i, ++p, ++data, ++weight)//先初始化前n个结点，这些结点的基本信息已知
    {
        *p = { *data,*weight,0,0,0 };
    }
    for (; i < m; ++i, ++p)//初始化余下的结点
    {
        *p = { ' ',0,0,0,0 };
    }
    for (i = n; i < m; i++)
    {
        int s1 = 0;
        int s2 = 0;
        select_two_min(tree, i - 1, s1, s2);
        tree[i].left = s1;  //更新当前结点的左右孩子的下标
        tree[i].right = s2;
        tree[s1].parent = tree[s2].parent = i; //更新左右孩子的父亲下标
        tree[i].weight = tree[s1].weight + tree[s2].weight; //更新当前结点的权重为左右孩子的权重之和

    }
}

通过上述的代码，我们就可以构造出一个Huffman树，而且这个Huffman树是用一个顺序结构存储的，各个结点之间使用数组的下标来联系的。

最优二叉树的应用（哈夫曼编码）

哈夫曼树最早就是被应用在编码压缩领域，比如我们现在有一组数据他们分别是：7个a，8个b，2个c，4个e，我们需要对刚才的那组数据进行编码，00代表a，01代表b，10代表c，11代表d，那么我们总用需要：7*2+8*2+2*2+4*2=42位来保存刚才的那组数据，好，如果我们另外一种编码，就是让权重大（数量多）的数据编码长度变小，让权重小的数据编码长度变长，这就是哈夫曼编码的原理。具体操作：

• 根据各个数据的数量，建立一个哈夫曼树
• 根据建立的哈夫曼树，对原始数据进行编码，记录往左孩子去为0，往右孩子去的编码为1，如下图： 
  
• 最后，就是根据哈夫曼树进行解码，0为往左子树遍历，1为往右子树遍历，直到叶子结点，就可以输出数据。

具体的代码实现如下：

#include<iostream>
#include<string>
using namespace std;


struct Tree_Node
{
    char data; //数值 
    int weight; //权重 
    int parent; //父亲结点的下标 
    int left; //左孩子下标 
    int right; //右孩子下标 
};

//在前i-1个结点中，找出最小的两个结点
void select_two_min(Tree_Node * tree,int k, int & s1, int & s2)
{
    int i = 0;
    int min = INT_MAX;
    int min2 = INT_MAX;
    for (i = 0; i <= k; i++)
    {
        //先找出s1
        if (tree[i].parent == 0 && tree[i].weight < min)
        {
            //更新m2的值为之前的m1，因为m1是之前最小的，现在变第二小了
            min2 = min; 
            //更新min
            min = tree[i].weight;
            //s2也是同样的道理，所以要更新
            s2 = s1;
            //s1也一样
            s1 = i;

        }//
        //如果还有比min2小，但是比min大的，那么只要更新min2和s2
        else if (tree[i].parent == 0 && tree[i].weight < min2) {
            min2 = tree[i].weight;
            s2 = i;
        }
    }

}
void Build_Huffman_Tree(Tree_Node * & tree, int * weight, int n, char * data)
{
    if (n <= 1) return; //如果叶子结点只有一个，那么就可以直接返回了 
    int m = 2 * n - 1;
    //开辟2*n-1个空间，用于存放各个结点的信息，
    //因为我们知道如果有n个结点，除了根结点，我们最多需要记录的结点信息为：2*n-1个。 
    tree = new Tree_Node[m];
    int i = 0;
    Tree_Node * p = tree;
    for (i = 0; i < n; ++i)//先初始化前n个结点，这些结点的基本信息已知
    {
        tree[i].data = data[i];
        tree[i].left = tree[i].right = tree[i].parent = 0;
        tree[i].weight = weight[i];
    }
    for (; i < m; ++i)//初始化余下的结点
    {

        tree[i].left = tree[i].right = tree[i].parent = 0;
        tree[i].weight = 0;
    }
    for (i = n; i < m; i++)
    {
        int s1 = 0;
        int s2 = 0;
        select_two_min(tree, i - 1, s1, s2);
        tree[i].left = s1;  //更新当前结点的左右孩子的下标
        tree[i].right = s2;
        tree[s1].parent = tree[s2].parent = i; //更新左右孩子的父亲下标
        tree[i].weight = tree[s1].weight + tree[s2].weight; //更新当前结点的权重为左右孩子的权重之和

    }
}



void code(char * str,int n,int * weight,char ** & huffmancode)
{
    Tree_Node * tree;
    Build_Huffman_Tree(tree, weight, n, str);
    huffmancode = new char*[n+1];
    char * c = new char[n];
    c[n - 1] = '\0';
    int i;
    int start;
    int child;
    int f;
    for (i = 0; i < n; i++)
    {
        start = n - 1;

        for (child = i, f = tree[i].parent; f != 0; child = f, f = tree[f].parent)
        {
            if (tree[f].left == child) {
                c[--start] = '0'; 
            }
            else {
                c[--start] = '1'; 
            }
        }
        huffmancode[i] = new char[n - start-1];
        int p = start;
        for (int k = 0; p < n; k++,p++)
        {
            huffmancode[i][k] = c[p];
        }
    }

}

int main()
{
    char *str;

    int n;
    int * weight;
    char ** huffmancode;
    cout << "输入字符种类：" << endl;
    cin >> n;
    str = new char[n];
    weight = new int[n];
    cout << "输入每个字符和对应的权重" << endl;
    int i;
    for (i = 0; i < n; i++)
    {
        cin >> str[i];
        cin >> weight[i];
    }

    code(str, n, weight, huffmancode);
    cout << "每个字符编码后的值" << endl;
    for (i = 0; i < n; i++)
    {
        cout << str[i]<<" : "<<huffmancode[i] << endl;
    }
    cout << endl;
    return 0;
}

输入： 
7 
D 17 
B 24 
E 34 
G 13 
C 7 
F 5 
A 5 
输出： 

十五、二叉排序树

二叉查找树定义：又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 
1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 
2) 若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； 
3) 它的左、右子树也分别为二叉排序树。 

十六、平衡二叉树（AVL树）

平衡二叉树（Balanced Binary Tree）又被称为AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。（注：平衡二叉树应该是一棵二叉排序树） 

下面给出高级一点的树的数据结构，这些树在面试的时候会被经常提及：

8、B树

B树又称为B-树，是一种平衡的多路查找树。B-树的阶是所有结点的孩子结点树的最大值。一棵m阶B-树，或为空树，或为满足下列特性的m叉树： 
1）树中每个结点至多有m棵子树； 
2）若根节点不是叶子节点，则至少有两棵子树； 
3）除根之外的所有非终端结点至少有[m/2]（）向上取整）棵子树； 
4）所有的非终端结点中包含下列信息数据：（n，A0，K1，A1，K2，A2，…，Kn，An），其中，n为结点中的关键字树，A为指向子树根结点的指针，K为关键字，且Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn； 
5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。下图为一棵4阶B-树： 

9、B+树

B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶B+树和m阶的B-树的差异在于： 
1）有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点； 
2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接； 

10、红黑树

红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。树中每个结点包含5个属性：color、key、left、right和p。如果一个结点没有子节点或父节点，则该结点相应的指针属性值为NIL，我们可以把这些NIL视为指向二叉搜索树的叶节点（外部结点）的指针，而把带关键字的结点视为树的内部结点。 
一棵红黑树是满足下面性质的二叉搜索树： 
1）每个结点或是红色的，或是黑色的； 
2）根结点是黑色的； 
3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的； 
4）如果一个结点是红色的，则它的两个子结点都是黑色的； 
5）对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。 
红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。 

11、键树

如果一个关键字可以表示成字符的序号，即字符串，那么可以用键树（keyword tree），又称数字搜索树或字符树，来表示这样的字符串的集合。键树的结构受启发于一部大型字典的“书边标目”。字典中标出首字母是 A，B，C，…，Z的单词所在页，再对各部分标出第二字母为A，B，C，…，Z的单词所在的页等等。 
键树是一种特殊的查找树，它是一棵度大于等于2的树，树中的每个节点不是包含一个或几个关键字，而是只含有组成关键字的符号。 
比如：如果关键字是数值，则节点中只包含一个数位；如果关键字是单词，则节点中只包含一个字母字符。根结点不代表任何字符，根以下第一层的结点对应于字符串的第一个字符，第二层的结点对应于字符串的第二个字符……每个字符串可由一个特殊的字符如“$”等作为字符串的结束符，用一个叶子结点来表示该特殊字符。把从根到叶子的路径上，所有结点（除根以外）对应的字符连接起来，就得到一个字符串。因此，每个叶子结点对应一个关键字。在叶子结点还可以包含一个指针，指向该关键字所对应的元素。整个字符串集合中的字符串的数目等于叶子结点的数目。如果一个集合中的关键字都具有这样的字符串特性，那么，该关键字集合就可采用这样一棵键树来表示。 
键树的存储通常有两种方式： 
1）用树的孩子兄弟链来表示键树，称为双链树；每个Node有三个域：symbol域：存储关键字的一个字符；son域：存储指向第一棵子树的根的指针；brother域：存储指向右兄弟的指针。 
2）用多重链表来表示键树，称为Trie树或字典树。

12、字典树

如果以树的多重链表来表示键树，则树的每个结点应包含d个（d为关键字符的基，如：字符集由英文大写字母构成时，则d=26）指针域，此时的键树又称为字典树。 
字典树典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。　 
Tire树的三个基本性质： 
1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符； 
2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 
3) 每个节点的所有子节点包含的字符都不相同。 
Tire树的应用： 
1) 串的快速检索 
给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。 
2) “串”排序 
给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。 
3) 最长公共前缀 

13、后缀树

所谓后缀树，就是包含一则字符串所有后缀的压缩了的字典树。先说说后缀的定义。给定一长度为n的字符串S=S1S2..Si..Sn，和整数i，1 <= i <= n，子串SiSi+1…Sn都是字符串S的后缀。以字符串S=XMADAMYX为例，它的长度为8，所以S[1..8],S[2..8], … , S[8..8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i..n]，我们说这项后缀起始于i。 
键树只适合前缀匹配和全字匹配，并不适合后缀和子串匹配，而后缀树在这方面则非常合适。它与键树的最大不同在于，后缀树的单词集合是由指定字符串的后缀子串构成。

14、区间树与线段树

区间树是在红黑树基础上进行扩展得到的支持以区间为元素的动态集合的操作，其中每个节点的关键值是区间的左端点。通过建立这种特定的结构，可是使区间的元素的查找和插入都可以在O(lgn)的时间内完成。相比于基础的红黑树数据结构，增加了一个max[x]，即以x为根的子树中所有区间的端点的最大值。 
线段树是一种平衡二叉查找树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。主要的处理思想是基于分治的思想。 
设根节点的区间为[a,b),区间长度为L = b - a，线段树的性质： 
1）线段树是一个平衡树，树的高度为log(L)； 
2）线段树把区间上的任意长度为L的线段都分成不超过2log(L)线段。

15、败者树与胜者树

胜者树和败者树都是完全二叉树，是树形选择排序的一种变型。在胜者树、败者树中，每个叶子结点相当于一个选手，每个中间结点相当于一场比赛，每一层相当于一轮比赛。不同的是，胜者树中的每个非终端结点均表示其左、右孩子结点中的“胜者”；而在败者树中，父结点中记下刚进行完的这场比赛中的败者，而让胜者去参加更高一层的比赛。下图为一棵实现5路归并排序的败者树：