数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。

它们是做什么用的？

想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）。

特性

链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。

它们是做什么用的？

链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索显示的页面的完美数据结构。

特性

堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循 LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。

堆栈可以使用数组或链表来实现。

它们是做什么用的？

现实生活中最常见的例子是在食堂中将盘子叠放在一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。

堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。

另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。

特性

队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。

它们是做什么用的？

这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。

一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 ）中是必不可少的。它是使用堆实现的。

另一种特殊类型的队列是deque 队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。

特性

Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。

哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。

最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是 6，则键 x 的值是x%6。

理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。

它们是做什么用的？

Maps 最著名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。

通讯录也是一张Map。每个名字都有一个分配给它的电话号码。

另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x小时60+x分钟。

特性

术语：

因为maps 是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。

图是表示一对两个集合的非线性数据结构：G={V, E}，其中 V 是顶点（节点）的集合，而 E 是边（箭头）的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。

图有两种主要类型：有向图和无向图。在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。

它们是做什么用的？

特性

图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：

一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的）。所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。

根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。

一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。

它们是做什么用的？

我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。

树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。

特性

二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。

二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。

它们是做什么用的？

BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。

BST 经常使用，因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。

特性

BST 有三种类型的 DFS 遍历：

所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。

AVL 树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名：Adelson-Velsky 和 Landis。

在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。

在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是 O(log n)。

它们是做什么用的？

AVL 似乎是数据库理论中最好的数据结构。

RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 版本中，HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。

在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。

特性

最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]]

1树的根结点: A

叶子结点: C,I,H,K,M,N,J,E,F

非终端结点: A,B,D,G,L

2树的度是: 4

各个结点的度: A\3,B/2,D/4,G/3,L/1

3树的深度: 5

各个结点的层数: A\1,B\2,D\2,G/3,L/4

对于结点G,他的父亲结点是:

D

祖先结点: A

孩子结点: L/M/K

子孙结点: L/M/K/N

兄弟和堂兄弟 H/I/J/E/F

还有给你一个不太长的资料

1树的定义

树是一种常见的非线性的数据结构。树的递归定义如下：

树是n(n>0)个结点的有限集，这个集合满足以下条件：

⑴有且仅有一个结点没有前件（父亲结点），该结点称为树的根；

⑵除根外，其余的每个结点都有且仅有一个前件；

⑶除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）；

2、结点的分类

在树中，一个结点包含一个元素以及所有指向其子树的分支。结点一般分成三类

⑴根结点：没有前件的结点。在树中有且仅有一个根结点。

⑵分支结点：除根结点外，有后件的结点称为分支结点。分支结点亦是其子树的根；

⑶叶结点：没有后件的结点称为树叶。由树的定义可知，树叶本身也是其父结点的子树。

根结点到每一个分支结点或叶结点的路径是唯一的。

3、有关度的定义

⑴结点的度：一个结点的子树数目称为该结点的度。显

然，所有树叶的度为0。

⑵树的度：所有结点中最大的度称为该树的度。4、树的深度（高度）

树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。

5、有序树和无序树

按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。

6、树的表示方法

树的表示方法一般有两种：

⑴自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。

⑵括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式

（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））

7、树的存储结构一般有两种

⑴静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标

⑵动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成

有序树：树中任意节点的 子结点之间有顺序关系，这种树称为有序树。

无序树：树中任意节点的 子结点之间没有顺序关系，这种树称为无序树,也称为自由树。

二叉树、有序树：左右有序

二叉树与有序树：在只有一棵树的情况下，二叉树有左右之分、有序树无左右之分

另外：二叉树是有序的，可以为空或一个根节点以及两个分别称为左子树和右子树的互不相交的二叉树组成。

树的基本操作：

构造树；清空树；判断树是否为空；获取树的深度；获取根节点；获取第i 个节点的值；改变节点的值；获取节点的父节点；获取节点左/右节点的值；输出树；向树中插入另一棵树；删除子树；遍历树。

#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <mathh>

using namespace std;

typedef struct _Node

{

    string sex;                 //性别 m 男; f 女

    string name;                //此人的姓名

    string spause;              //配偶的姓名

    unsigned short level;       //层次 辈分最高一层为1,下一层为为2,以此类推

    struct _Node l_child;      //指向其第一个孩子的指针 

    struct _Node r_brother;    //指向其某一个兄弟姐妹的指针, 即左孩子为其后代,右孩子为其兄弟姐妹 

    struct _Node btr;          //指向其父亲或者母亲的指针       

    _Node():level(0),l_child(NULL),r_brother(NULL),btr(NULL){cout<<"constructor"<<endl;}

    ~_Node(){cout<<name<<" destructor"<<endl;}

}Node, PNode;

void CreateBiTreePreOrder(PNode &pn, PNode pback, unsigned short depth);//建立二叉家谱树,以先序方式 

void VisitBiTreePreOrder(PNode root);                                   //前序遍历此二叉树 

void TellRelation(PNode root);                                          //判断两人关系 

void DestroyBiTreePostOrder(PNode root);                                //销毁二叉树,释放节点占用的空间 

void FindPersonMiddleOrder(PNode root, string name, PNode &presult);    //返回家谱中指向某人的指针,找不到返回NULL 

Node root=NULL;                                                        //全局变量,二叉树的根节点 

unsigned findPersonFlag = 0;   //标志位,0 没找到; 1 找到,找到后就不再搜索直接返回;利用此flag可避免将整个tree遍历一遍(若该name在tree中存在的话)

int main()

{

    cout<<"请按先序遍历的顺序根据提示输入家谱信息,不存在则输入\"#\""<<endl;

    CreateBiTreePreOrder(root, NULL, 1);//建立二叉家谱树,以先序方式

    VisitBiTreePreOrder(root);          //前序遍历此二叉树

    TellRelation(root);                 //判断两人关系

    DestroyBiTreePostOrder(root);       //销毁二叉树 

    getchar();getchar();getchar();

    return 0;    

} 

/    

    function:建立二叉家谱树,以先序方式

    argument:

            pn: 指向二叉树节点的引用 

          pback: pn这个节点的btr指针的值,即指向其parent的指针 

         depth: 该节点的层次,分最高一层为1,下一层为为2,以此类推            

/

void CreateBiTreePreOrder(PNode &pn, PNode pback, unsigned short depth)

{

    string str;

    cin>>str;                               //输入该人信息,格式是 sex-name-spausename,如不存在则输入# 

    if(str == "#")                          //如: M-tom-marry, 表示此人叫tom, 男性, 配偶名字marry        

    {

        pn = NULL;

        return;

    }

    

    //如果是自定义的struct/class，应该使用构造函数。如果是内建数据类型，

    //比如int，应该memset。 当然，更好的建议是使用vector取代new出来的数组

    pn = new Node;

    

    //处理输入的字符串 

    vector<string> v; 

       for(size_t b=0, e=strfind('-'); ; e=strfind('-', b))

    {

        if(e == string::npos)

        {

            vpush_back(strsubstr(b));          

            break;

        }

        else   

              vpush_back(strsubstr(b, e-b));

        b = e+1;

    }

    

    //初始化该节点

    pn->sex = v[0];

    pn->name = v[1];

    pn->spause = v[2];

    pn->btr = pback;

    pn->level = depth;

    

    //递归建立左右子树的节点 

    CreateBiTreePreOrder(pn->l_child, pn, depth+1);        //注意后两个参数的值 

    CreateBiTreePreOrder(pn->r_brother, pback, depth);    //注意后两个参数的值 

}

/    

    function: 前序遍历此二叉树        

/

void VisitBiTreePreOrder(PNode pn)             

{

    if(!pn)    

        return;

    

    cout<<endl<<"sex:"<<pn->sex<<endl;

    cout<<"name:"<<pn->name<<endl;    

    cout<<"spause:"<<pn->spause<<endl;

    cout<<"level:"<<pn->level<<endl;

    cout<<"father's name:"<<((pn->btr == NULL)"NULL":pn->btr->name)<<endl;

    cout<<"======================"<<endl;

    VisitBiTreePreOrder(pn->l_child);

    VisitBiTreePreOrder(pn->r_brother); 

}

/    

    function: 中序遍历找到家谱中的一个人,返回其指针,若找不到,返回NULL

            isSpause 1表示是找到的节点的配偶 0表示不是所找到的节点的配偶        

/ 

void FindPersonMiddleOrder(PNode pn, string name, PNode &presult)

{

    if(!pn)                      

        return;

    

    FindPersonMiddleOrder(pn->l_child, name, presult);

    if(findPersonFlag) return;

    if(name == pn->name || name == pn->spause)

    {

        presult = pn;

        findPersonFlag = 1;    //全局标志位,0 没找到; 1 找到,找到后就不再搜索直接返回;利用此全局flag可避免将整个tree遍历一遍(若该name在tree中存在的话)

        return;                   //下次使用前不要忘记置为0 

    }

    FindPersonMiddleOrder(pn->r_brother, name, presult);  

}

/    

    function: 判断两人关系,若两人中至少一人不在树中,则两人无关系

              若两人在树中,先判断两人是否同层次,若同层,判断是否是亲兄弟姐妹;

              若不同层,设辈分大的人为A,辈分小的人为B,判断A和B是亲的还是表的,

              比如,A为男性,且比B大一倍,判断A是否为B的爸爸,或亲叔叔(舅舅),或表叔叔(舅舅)

              简单起见,此处没有区分是叔叔还是舅舅

              比如,A为男性,且比B大两倍,判断A是否为B的亲爷爷(姥爷),或亲爷爷(姥爷)的亲兄弟

              ,或亲爷爷(姥爷)的表兄弟 

              简单起见,此处没有区分是叔叔和舅舅等做进一步区分

              简单起见,查询时只输入节点中的name,不查询spause,否则处理起来太麻烦 

/ 

void TellRelation(PNode pn)

{

    string name1, name2; 

    //p1指向name1, p2指向name2, pbig指向辈分大的,psmall指向辈分小的 

    PNode p1 = NULL, p2 = NULL, pbig = NULL, psmall = NULL;

    int differ = 0;     //两人辈分数的差别 

    string title;

    Label: 

    cout<<endl<<"输入想查询关系的两个人的名字,不想查则将两人名字输成#:"<<endl;

    while(cin>>name1 && cin>>name2)

    {

        if(name1=="#" && name2=="#")    return;

        p1 = NULL; p2 = NULL;    //因为程序是循环执行的,需要将上次遗留的值清掉 

        findPersonFlag = 0;

        FindPersonMiddleOrder(root, name1, p1);

        findPersonFlag = 0;

        FindPersonMiddleOrder(root, name2, p2);

        if(!p1 || !p2)  //若有一个为空或都为空,说明至少有一个人不在家谱中,故两人无亲缘关系 

        {

            cout<<name1<<((!p1)" 不在":" 在")<<" 家谱树中"<<endl;

            cout<<name2<<((!p2)" 不在":" 在")<<" 家谱树中"<<endl;

            cout<<name1<<" 和 "<<name2<<" 间没有关系"<<endl<<endl;

            goto Label;

        } 

        differ = (int)abs(p1->level - p2->level);

        if(!differ)     //辈分一样大 

        {

            if(p1->sex == p2->sex)

            {

                if(p1->sex == "M")  title = "兄弟关系";

                else    title = "姐妹关系";

            }

            else    title = "兄妹(姐弟)关系";

            if(p1->btr == p2->btr)  //parent相同 

                cout<<name1<<" 和 "<<name2<<" 间是 "<<" 亲 "<<title<<endl;

            else

                cout<<name1<<" 和 "<<name2<<" 间是 "<<" 表 "<<title<<endl;

        }

        else    //辈分不一样大 

        {

            if(p1->level < p2->level)   {pbig = p1; psmall = p2;}

            else {pbig = p2; psmall = p1;}

            switch(differ)

            {

                case 1:

                    if(psmall->btr == pbig)

                        title = ((pbig->sex == "M")"爸爸":"妈妈");

                    else

                    {

                        if(psmall->btr->btr == pbig->btr)

                            title = ((pbig->sex == "M")"亲叔(舅)":"亲姑(姨)");

                        else    

                            title = ((pbig->sex == "M")"表叔(舅)":"表姑(姨)");

                    }

                    break;

                case 2:

                    if(psmall->btr->btr == pbig)

                        title = ((pbig->sex == "M")"爷爷(姥爷)":"奶奶(姥姥)");

                    else

                    {

                        string tmp = ((pbig->sex == "M")"兄弟":"姐妹");

                        if(psmall->btr->btr->btr == pbig->btr)

                            title = ((psmall->btr->btr->sex == "M")"爷爷(姥爷)的亲":"奶奶(姥姥)的亲") + tmp; 

                        else    

                            title = ((psmall->btr->btr->sex == "M")"爷爷(姥爷)的表":"奶奶(姥姥)的表") + tmp; 

                    }

                    break;

                default:

                    string tmp2;

                    PNode pt = psmall;

                    int n = differ-2; //计算"老"字 (即grand这个字) 出现的个数 

                    for(int i=0; i<n; ++i)

                         tmp2 += "老";

                    

                    for(int i=0; i<differ; ++i)

                        pt =  pt->btr;  

                    if(pt == pbig)

                        title =  tmp2 + ((pbig->sex == "M")"爷爷(姥爷)":"奶奶(姥姥)");

                    else

                    {

                        string tmp3 = ((pbig->sex == "M")"兄弟":"姐妹");

                        if(pt->btr == pbig->btr)

                            {title = tmp2 + ((pt->sex == "M")"爷爷(姥爷)的亲":"奶奶(姥姥)的亲"); title+=tmp3;}

                        else

                            {title = tmp2 + ((pt->sex == "M")"爷爷(姥爷)的表":"奶奶(姥姥)的表"); title+=tmp3;}

                    }

                    break;

            } 

            cout<<pbig->name<<" 是 "<<psmall->name<<" 的 "<<title<<endl;  

        }

        goto Label;

    }

}                 

/    

    function: 后序遍历销毁此二叉树,释放节点占用的内存空间     

/ 

void DestroyBiTreePostOrder(PNode pn)

{

    if(!pn) return;

    DestroyBiTreePostOrder(pn->l_child);

    DestroyBiTreePostOrder(pn->r_brother);

    delete pn;  

}

家族树是家族网团队研发的一项应用，它就好比是一个树状的数字家谱，用户在树上可以进行沟通互动娱乐等。

具体来说呢，

家族树，是指利用互联网技术，依据血缘关系或亲祖关系把人联系起来，再按照辈份排序构成树的模型。 在树中的成员可以清楚的知道自己的家族起源、家族关系以及其他成员的基础信息，并且享有记录、分享等沟通娱乐服务。

作用和功效有几个：

追祖溯源

汇聚亲情

沟通分享

传承家族文化

家族树的树状特征和原理可以让树无限延伸和扩大，添加家庭成员，是目前用于家庭沟通比较好的网络工具之一。

你去自己亲自建立一颗家族树会更清楚！

满二叉树：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

节点：

就是一个图中的0、1、2~~14，这些就叫节点。

叶子节点：

就是没有子节点的节点，比如图中的7、8、9~~14这些，0、1、2、3这些就不是叶子节点。

拓展：二叉树相关术语

树的结点（node）：包含一个数据元素及若干指向子树的分支；

孩子结点（child node）：结点的子树的根称为该结点的孩子；

双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；

兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；

祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的深度：树中最大的结点层

结点的度：结点子树的个数

树的度： 树中最大的结点度。

叶子结点：也叫终端结点，是度为 0 的结点；

分枝结点：度不为0的结点；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；

很难吗？树结构哦。看你数据结构学的怎么样呗。呵呵，我先想到的数据结构是双亲孩子表示法，当然查找关系的时候就要进行一些条件设置，比如祖孙的关系数大于父子的关系数2，兄弟拥有相同的双亲，堂兄弟的双亲是兄弟，回溯到相同的祖先结点则有共同的祖先咯。